directory

    • The title
    • Continuous refinement of core ideas
      • 1. Core framework
      • 2. Consider the work of each position
      • 3. Take into account that the number at the last column has already been preset
      • 4. Determine whether the function conforms to the rule
      • 5. Determine the recursive termination condition + determine the return value of the function
    • AC code

The title

Write a program to solve a sudoku problem by filling in the blanks. A sudoku solution must follow the following rules:

1. The numbers 1-9 May appear only once in each line. 2. The numbers 1-9 May appear only once in each column. 3. The numbers 1-9 can only occur once in each 3×3 palace separated by a thick solid line.

Blank Spaces are represented by a ‘. ‘.

A Sudoku. The answers are marked in red.

Tip:

A given sudoku sequence contains only the numbers 1-9 and the character ‘. ‘. You can assume that a given sudoku has only one solution. Sudoku is always 9×9.

Continuous refinement of core ideas

The core idea of the algorithm is to enumerate 1 to 9 for each empty cell. If it finds an illegal number (the same number in the same row or column or in the same 3×3 area), it will skip. If it finds a valid number, it will continue to enumerate the next space. Write the core framework:

1. Core framework

void solveSudoku(vector<vector<char>>& board) {
    backtrack(board, 0.0);
}

void backtrack(vector<vector<char>>& board, int hang, int lie) {
    // Perform an exhaustive selection of each position on the board
    for (int i = hang; i < 9; i++) {
        for (int j = lie; j < 9; j++) {
            / / to make a choice
            backtrack(board, i, j);
            // Undo the selection}}}Copy the code

2. Consider the work of each position

There are 1 to 9 options for each position, making it a triple re-nesting loop.

void backtrack(vector<vector<char>>& board, int hang, int lie) {
    // Perform an exhaustive search for each position
    for (int i = hang; i < 9; i++) {
        for (int j = lie; j < 9; j++) {
            for (char ch = '1'; ch <= '9'; ch++) {
                / / to make a choice
                board[i][j] = ch;
                // Proceed to the next column,
                backtrack(board, i, j + 1);
                // Undo the selection
                board[i][j] = '. '; }}}}Copy the code

3. Take into account that the number at the last column has already been preset

1. When lie reaches past the last index, add hang and start to exhaust the next row. 2. If the current element is not “. , so skip it. 3. If the number meets the rule, fill it in, otherwise skip it.

void backtrack(vector<vector<char>>& board, int hang, int lie) {
	if(lie==9)
	{
		backtrack(board, hang+1.0);
	}
    // Perform an exhaustive search for each position
    for (int i = hang; i < 9; i++) {
        for (int j = lie; j < 9; j++) {
        	// If this position is a preset number, don't worry about it
            if(board[i][j] ! ='. ') {
                backtrack(board, i, j + 1);
                return;
            } 
            // If it is not a preset number
            for (char ch = '1'; ch <= '9'; ch++) {
            	// If you see a number that matches the rule, fill it in
                if (isValid(board, i, j, ch)){
	                / / to make a choice
	                board[i][j] = ch;
	                // Proceed to the next column,
	                backtrack(board, i, j + 1);
	                // Undo the selection
	                board[i][j] = '. ';
                }
            }
        }
    }
}
Copy the code

4. Determine whether the function conforms to the rule

Here are the rules:

1. The numbers 1-9 May appear only once in each line. 2. The numbers 1-9 May appear only once in each column. 3. The numbers 1-9 can only occur once in each 3×3 palace separated by a thick solid line.

Notice how rule 3 is described here:

// check whether board[I][j] can fill in n
bool isValid(vector<vector<char>>& board, int hang, int lie, char n) {
    for (int i = 0; i < 9; i++) {
        // Determine if there is a duplicate row
        if (board[hang][i] == n) return false;
        // Determine if there is a duplicate column
        if (board[i][lie] == n) return false;
        // Check whether the 3 x 3 box is duplicated
        if (board[(hang/3) *3 + i/3][(lie/3) *3 + i%3] == n)
            return false;
    }
    return true;
}
Copy the code

Here is what this means, and I =0~8 is simulated:

5. Determine the recursive termination condition + determine the return value of the function

If we recurse the last row, then we can return our result. If we find one solution, we’re done, but we’re not asking for all of them. If a position does not match all digits, the path is blocked and false should be returned immediately. If every position has been traversed and the result does not return true, the sudoku board has no solution and returns false. So use a bool as the return value:

if(hang == 9) return true;
Copy the code

The full code for the traceback function should look like this:

bool backtrack(vector<vector<char>>& board, int hang, int lie) {
	// Walk through the last column of the row, then walk through the next row
	if(lie==9)
	{
		return backtrack(board, hang+1.0);
	}
	// Find a solution, return
	if(hang == 9) return true;
    // Perform an exhaustive search for each position
    for (int i = hang; i < 9; i++) {
        for (int j = lie; j < 9; j++) {
        	// If this position is a preset number, don't worry about it
            if(board[i][j] ! ='. ') {
                return backtrack(board, i, j + 1);
            } 
            // If it is not a preset number
            for (char ch = '1'; ch <= '9'; ch++) {
            	// If you see a number that matches the rule, fill it in
                if (isValid(board, i, j, ch)){
	                / / to make a choice
	                board[i][j] = ch;
	                // Continue enumerating the next column. If a solution is found, terminate immediately
	                if(backtrack(board, i, j + 1) = =true) return true;
	                // Undo the selection
	                board[i][j] = '. '; }}// There is no feasible solution to this problem
            return false; }}return false;
}
Copy the code

AC code

class Solution {
public:
    // check whether board[I][j] can fill in n
    bool isValid(vector<vector<char>>& board, int hang, int lie, char n) {
        for (int i = 0; i < 9; i++) {
            // Determine if there is a duplicate row
            if (board[hang][i] == n) return false;
            // Determine if there is a duplicate column
            if (board[i][lie] == n) return false;
            // Check whether the 3 x 3 box is duplicated
            if (board[(hang/3) *3 + i/3][(lie/3) *3 + i%3] == n)
                return false;
        }
        return true;
    }
    bool backtrack(vector<vector<char>>& board, int hang, int lie) {
        // Walk through the last column of the row, then walk through the next row
        if(lie==9)
        {
            return backtrack(board, hang+1.0);
        }
        // Find a solution, return
        if(hang == 9) return true;
        // Perform an exhaustive search for each position
        for (int i = hang; i < 9; i++) {
            for (int j = lie; j < 9; j++) {
                // If this position is a preset number, don't worry about it
                if(board[i][j] ! ='. ') {
                   return backtrack(board, i, j + 1);
                } 
                // If it is not a preset number
                for (char ch = '1'; ch <= '9'; ch++) {
                    // If you see a number that matches the rule, fill it in
                    if (isValid(board, i, j, ch)){
                        / / to make a choice
                        board[i][j] = ch;
                        // Continue enumerating the next column. If a solution is found, terminate immediately
                        if(backtrack(board, i, j + 1) = =true) return true;
                        // Undo the selection
                        board[i][j] = '. '; }}// There is no feasible solution to this problem
                return false; }}return false;
    }
    void solveSudoku(vector<vector<char>>& board) {
        backtrack(board, 0.0);
        return; }};Copy the code