Leetcode | Valid Sudoku & Sudoku Solver

validを判断するには、より良い方法はなく、brute forceしかありません.

 1 class Solution {

 2 public:

 3     bool isValidSudoku(vector<vector<char> > &board) {

 4         

 5         int n;

 6         for (int i = 0; i < 9; ++i) {

 7             vector<bool> contained(9, false);

 8             for (int j = 0; j < 9; ++j) {

 9                 if (board[i][j] == '.') continue;

10                 n = board[i][j] - '0' - 1;

11                 if (contained[n]) return false;

12                 contained[n] = true;

13             }

14         }

15         

16         for (int i = 0; i < 9; ++i) {

17             vector<bool> contained(9, false);

18             for (int j = 0; j < 9; ++j) {

19                 if (board[j][i] == '.') continue;

20                 n = board[j][i] - '0' - 1;

21                 if (contained[n]) return false;

22                 contained[n] = true;

23             }

24         }

25         

26         for (int i = 0; i < 3; ++i) {

27             for (int j = 0; j < 3; ++j) {

28                 vector<bool> contained(9, false);

29                 for (int k = 0; k < 3; ++k) {

30                     for (int m = 0; m < 3; ++m) {

31                         if (board[i*3+k][j*3+m] == '.') continue;

32                         n = board[i*3+k][j*3+m] - '0' - 1;

33                         if (contained[n]) return false;

34                         contained[n] = true;

35                     }

36                 }

37             }

38         }

39         return true;

40     }

41 };

解決策を求めるのもbacktrackだけです.

 1 class Solution {

 2 public:

 3     void solveSudoku(vector<vector<char> > &board) {

 4         list<int> unsolved;

 5         getUnsolved(board, unsolved);

 6         recursive(board, unsolved);

 7     }

 8     

 9     bool recursive(vector<vector<char> > &board, list<int> &unsolved) {

10         if (unsolved.empty()) return true;

11         int loc = unsolved.front();

12         int row = loc / 9;

13         int col = loc % 9;

14         

15         vector<bool> contained(9, false);

16         int n;

17         for (int i = 0; i < 9; ++i) {

18             if (board[row][i] != '.') {

19                 contained[board[row][i] - '0' - 1] = true;

20             }

21             if (board[i][col] != '.') {

22                 contained[board[i][col] - '0' - 1] = true;

23             }

24         }

25         

26         row = row / 3; col = col / 3;

27         for (int i = 0; i < 3; ++i) {

28             for (int j = 0; j < 3; ++j) {

29                 if (board[row * 3 + i][col * 3 + j] != '.') {

30                     contained[board[row * 3 + i][col * 3 + j] - '0' - 1] = true;

31                 }

32             }

33         }

34         

35         row = loc / 9; col = loc % 9;

36         for (int i = 0; i < 9; ++i) {

37             if (!contained[i]) {

38                 board[row][col] = i + 1 + '0'; 

39                 unsolved.pop_front();

40                 if (recursive(board, unsolved)) return true;

41                 board[row][col] = '.';

42                 unsolved.push_front(loc);

43             }

44         }

45         

46         return false;

47     }

48     

49     void getUnsolved(vector<vector<char> > &board, list<int> &unsolved) {

50         for (int i = 0; i < 9; i++) {

51             for (int j = 0; j < 9; ++j) {

52                 if (board[i][j] == '.') {

53                     unsolved.push_back(i * 9 + j);

54                 }

55             }

56         }

57     }

58 };

unsolved配列を使用すると、毎回次の要素を最初から最後までスキャンする必要があることを回避できます.
contained配列では,この行のこの格のこの九宮格にすでに存在する数字を先に保存した.これにより、挿入した値が合法かどうかを毎回再検査する必要がなく、残りの数字を直接試験することができます.
backtrackは戻り値が必要です.そうしないと、backtrackが終わり、解決策が見つかったかどうか分かりません.