[LeetCode] 37. Sudoku Solver

轉自LeetCode

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.

A sudoku puzzle...

...and its solution numbers marked in red.

<Solution>

這題是的 valid sudoku 衍生題，這次就真的要求解了

這邊有個神解，先記錄下來，還沒理解怎麼做的

這邊的想法是，要求一個解，但過程可能需要回溯，這時候就用 DFS

• 在空格處從 1 填到 9，看看哪一個數字可以解

• 填入數字後，檢查是否符合規則

• 若是符合規則，就 DFS 繼續解下去

• row == 9 的時候，就代表解完了

code 如下

	class Solution {
	public:
	Solution() {
	mBoardLen = 9;
	}
	void solveSudoku(vector<vector<char>>& board) {
	solveByDFS(0, 0, board);
	}
	bool solveByDFS(const int &row, const int &col, vector<vector<char>>& board) {
	//> ending criteria
	if(row == mBoardLen) {
	return true;
	}
	else if(col == mBoardLen) {
	return solveByDFS(row+1, 0, board);
	}
	//> solve sudoku
	if(board[row][col] == '.') {
	for(int i = 0; i < 9; i++) {
	char ch = static_cast<char>('1' + i);
	board[row][col] = ch;
	if(isValid(row, col, board)) {
	if(solveByDFS(row, col+1, board)) {
	return true;
	}
	}
	//> current number is either non-valid
	//> or non-solvable
	board[row][col] = '.';
	}
	}
	else {
	return solveByDFS(row, col+1, board);
	}
	return false;
	}
	bool isValid(const int &row, const int &col, vector<vector<char>>& board) {
	//> check row
	for(int c = 0; c < mBoardLen; c++) {
	if(c != col && board[row][c] == board[row][col]) {
	return false;
	}
	}
	//> check col
	for(int r = 0; r < mBoardLen; r++) {
	if(r != row && board[r][col] == board[row][col]) {
	return false;
	}
	}
	//> check cube
	int rStart = 3 * (row / 3);
	int cStart = 3 * (col / 3);
	for(int r = rStart; r < rStart + 3; r++) {
	for(int c = cStart; c < cStart + 3; c++) {
	if(r != row && c != col && board[r][c] == board[row][col]) {
	return false;
	}
	}
	}
	return true;
	}
	private:
	int mBoardLen;
	};

view raw sudokuSolver.cpp hosted with ❤ by GitHub