Leetcodes Solution 37 Sudoku Solver

zhuanlan.zhihu.com

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character ..

You may assume that there will be only one unique solution.

思路1

「先放置，再判斷」

首先判斷當前位置是否為空，如果為空，那麼放置一個元素，檢查它是否正確。如果正確，就繼續進行下面的遞歸。當函數返回錯誤之後，將剛剛的數值變為空，再進行下一次嘗試即可。

class Solution{ bool check(vector<vector<char>> &board, int i, int j, char val){ int row = i - i%3, column = j - j%3; for(int x = 0; x < 9; x++) if(board[x][j] == val) return false; for(int y = 0; y < 9; y++) if(board[i][y] == val) return false; for(int x = 0; x < 3; x++) for(int y = 0; y < 3; y++) if(board[row + x][column + y] == val) return false; return true; } bool solveSudoku(vector<vector<char>>& board, int i, int j){ if(i == 9) return true; if(j == 9) return solveSudoku(board, i + 1, 0); if(board[i][j] != .) return solveSudoku(board, i, j+1); for(char c = 1; c <= 9; c++){ if(check(board, i, j, c)){ board[i][j] = c; if(solveSudoku(board, i, j+1)) return true; board[i][j] = .; } } return false; }public: void solveSudoku(vector<vector<char>>& board){ solveSudoku(board, 0, 0); }};

推薦閱讀：