36/37-数独

LeetCode 36. Valid Sudoku

LeetCode-36

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

• Each row must contain the digits 1-9 without repetition.
• Each column must contain the digits 1-9 without repetition.
• Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

method: 模拟

每个数字对应一个27位的数组，前9位代表是否在某行出现，中间9位代表是否在某列出现，后9位代表是否在某个方框中出现

通过整体的(i,j)获取方框的下标：i / 3 * 3 + j / 3，

i负责0 3 6，所以要再乘以3，j负责0 1 2，就不用乘3

bool used[9][27];
bool isValidSudoku(vector<vector<char>>& board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') continue;
            int k = i / 3 * 3 + j / 3;  // 属于哪个方框
            int num = board[i][j] - '1';
            if (used[num][i] || used[num][j + 9] || used[num][k + 18])
                return false;
            used[num][i] = true;
            used[num][j + 9] = true;
            used[num][k + 18] = true;
        }
    }
    return true;
}

---

可以只用长度为9的数组记录，用时间换空间，每次用之前都要先清空
同样也是注意方框的遍历的写法

int used[9];
bool check(char ch) {
    if (ch == '.') return true;
    int num = ch - '1';
    if (used[num]) return false;
    return used[num] = true;
}
bool isValidSudoku(vector<vector<char>>& board) {
    for (int i = 0; i < 9; i++) {       // 遍历0-8
        fill(used, used + 9, false);    // 清空
        for (int j = 0; j < 9; j++) {   // 判断行
            if (!check(board[i][j])) return false;
        }
        fill(used, used + 9, false);
        for (int j = 0; j < 9; j++) {   // 判断列，注意是[j][i]
            if (!check(board[j][i])) return false;
        }
    }
    // 判断每个方框
    for (int r = 0; r < 3; r++) {       // 行3个框
        for (int c = 0; c < 3; c++) {   // 列3个框
            fill(used, used + 9, false);
            for (int i = r * 3; i < r * 3 + 3; i++) {
                for (int j = c * 3; j < c * 3 + 3; j++) {
                    if (!check(board[i][j])) return false;
                }
            }
        }
    }
    return true;
}

---

LeetCode 37. Sudoku Solver

LeetCode-37

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The . character indicates empty cells.

Example 1:

method: 回溯

先处理used数组，再回溯填数

递归需要返回，但又不需要对返回值进行处理，就设置为bool，如果最后返回true，那就一路返回true，不再回溯处理了

bool used[9][27];
bool traversal(vector<vector<char>>& board, int index) {
    if (index > 80) return true;    // 到末尾说明前面都没问题了
    int m = index / 9;          // 对应行
    int n = index % 9;          // 对应列
    int k = m / 3 * 3 + n / 3;  // 对应块
    if (board[m][n] == '.') {
        for (int i = 0; i < 9; i++) {   // 这里是0-8
            if (used[i][m] || used[i][n + 9] || used[i][k + 18]) continue;
            board[m][n] = i + '1';
            used[i][m] = 1;
            used[i][n + 9] = 1;
            used[i][k + 18] = 1;
            if (traversal(board, index + 1)) return true;   // 如果下一层是true，就直接返回
            board[m][n] = '.';
            used[i][m] = 0;
            used[i][n + 9] = 0;
            used[i][k + 18] = 0;
        }
    }
    else if (traversal(board, index + 1)) return true;  // 不需要处理直接递归到下一层
    return false;
}

void solveSudoku(vector<vector<char>>& board) {
    for (int i = 0; i < 9; i++) {   // 先处理used数组
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') continue;
            int k = i / 3 * 3 + j / 3;
            int num = board[i][j] - '1';
            used[num][i] = 1;       // 行
            used[num][j + 9] = 1;   // 列
            used[num][k + 18] = 1;  // 块
        }
    }
    traversal(board, 0);
}