题解 | #Sudoku#dfs简洁版
Sudoku
https://www.nowcoder.com/practice/78a1a4ebe8a34c93aac006c44f6bf8a1
#include <iostream> #include <vector> using namespace std; //标记数的使用情况 bool hash1[10][10]; //行 bool hash2[10][10]; //列 bool hash3[3][3][10]; //小方格 bool valid = false; //棋盘能否有解 int board[10][10]; vector<pair<int,int>> pos; //记录0所在位置 void dfs(int idx) { if(idx == pos.size()) { valid = true; return; } auto [i, j] = pos[idx]; for(int k = 1; k <= 9 && !valid; k++) //!valid是保证棋盘搜索到一个有效解就停止 { if(!hash1[i][k] && !hash2[j][k] && !hash3[i/3][j/3][k]) { hash1[i][k] = true; hash2[j][k] = true; hash3[i/3][j/3][k] = true; board[i][j] = k; dfs(idx + 1); hash1[i][k] = false; hash2[j][k] = false; hash3[i/3][j/3][k] = false; } } } int main() { for(int i = 0; i < 9; i++) for(int j = 0; j < 9; j++) { int num; cin >> num; board[i][j] = num; if(num) { hash1[i][num] = true; hash2[j][num] = true; hash3[i/3][j/3][num] = true; } else pos.push_back({i,j}); //记录空位置 } dfs(0); for(int i = 0; i < 9; i++) { for(int j = 0; j < 9; j++) cout << board[i][j] << " "; puts(""); } return 0; }