链接37. 解数独 - 力扣LeetCode题解1.把没有数字的位置使用vector记录下来2.每个数字现在已经存在的行rows列cols3X3九宫格boxes都记录下来3.dfs回溯每一个数字到vector的size结束class Solution { private: bool line[9][9]; bool column[9][9]; bool block[3][3][9]; vectorpairint, int spaces; public: bool dfs(vectorvectorchar board, int pos) { if (pos spaces.size()) { return true; } auto [i, j] spaces[pos]; for (int digit 0; digit 9; digit) { if (!line[i][digit] !column[j][digit] !block[i / 3][j / 3][digit]) { line[i][digit] column[j][digit] block[i / 3][j / 3][digit] true; board[i][j] digit 0 1; if(dfs(board, pos 1)) { return true; } line[i][digit] column[j][digit] block[i / 3][j / 3][digit] false; } } return false; } void solveSudoku(vectorvectorchar board) { memset(line, false, sizeof(line)); memset(column, false, sizeof(column)); memset(block, false, sizeof(block)); for (int i 0; i 9; i) { for (int j 0; j 9; j) { if (board[i][j] .) { spaces.emplace_back(i, j); } else { int digit board[i][j] - 0 - 1; line[i][digit] column[j][digit] block[i / 3][j / 3][digit] true; } } } dfs(board, 0); } };