题解 | #Sudoku#

#include <iostream>
using namespace std;
#include <vector>

// 填入新数有效性检查
bool isValid(const vector<vector<int>>& board, int i, int j, int num) {
    for (int a = 0; a < 9; a++) {
        if (board[a][j] == num) {
            return false;
        }
    }
    for (int a = 0; a < 9; a++) {
        if (board[i][a] == num) {
            return false;
        }
    }

    int r = (i / 3) * 3;
    int c = (j / 3) * 3;
    for (int a = r; a < r + 3; a++) {
        for (int b = c; b < c + 3; b++) {
            if (board[a][b] == num) {
                return false;
            }
        }
    }
    return true;
}

bool backtracking(vector<vector<int>>& board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == 0) {
                for (int k = 1; k <= 9; k++) {
                    if (isValid(board, i, j, k)) {
                        board[i][j] = k;
                        bool result = backtracking(board);
                        if (result) {
                            return true;
                        }
                        board[i][j] = 0;
                    }
                }
                return false;
            }
        }
    }
    return true;
}

int main() {
    vector<vector<int>> board(9, vector<int>(9, 0));
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> board[i][j];
        }
    }
    backtracking(board);
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
}

代码其实不难~

附上数独问题的笔记

2 解数独

2.1 数独概念

• 一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。求填满空格的一个方案(只找到一个符合的叶子节点即刻返回，用bool作返回值)
• 比N皇后问题多一个维度

2.2 2维递归（2 for 循环）

bool backtracking(board){for (int i = 0; i < board.size(); i++)
{
    for (int i = 0; i < board.size(); i++)
	{
    	for (int j = 0; j < board[0].size(); j++)
    	{
        	if (board[i][j] == 0) // 为空时
        	{
            	for (char k = '1'; k <= '9'; k++)
            	{
                	if (isValid(i, j, k, board))
                	{ // 检查合法性
                    	board[i][j] = k;
                    	bool result = backtracking(board); 
                    	if (result)
                    	{
                        	return true;
                    	}
                    // 回溯
                    	board[i][j] = 0;
                	}
            	}
            // 9数都不合法，返回错
            return false;
        	}
    	}
	}
	return true;
}