LeetCode Sudoku Solver 数独C++程序

Sudoku Solver

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.

本题使用回溯法来解题，思路：

1 使用两个循环，逐个检查所有的方格

2 每到一个方格，检查到位空，以‘.'字符代表，就循环使用’1‘<=a<=9字符测试是否合法。

3 如果a合法，那么就继续填写下一个

4 如果不合法那么就回溯到上一个空格。

这里最巧妙和最难的地方就是在第2步中，逐个循环检查'1'<=a<='9'循环中使用了递归，就是如果当前字符合法，然后递归检查下个空格。这样程序就变得非常简洁。

还有难点就是判断什么时候需要返回真或者假。有两个地方：

1 当前测试'1'到'9'个数字都不合法，那么返回假

2 棋盘中所有空格都填满，那么就返回真

判断和Leetcode另外一个题目判断Sudoku是否合法的题目不同的就是，这里只需要判断当前格，一个循环就可以了，不需要判断所有的格。

	const static int SQUNUM = 9;
	const static int NUM = 3;

	bool isValid(vector
  
    > &board, int row, int col)
	{
		int sRow = row / NUM;
		int sCol = col / NUM;
		for (int i = 0; i < SQUNUM; i++)
		{
			if (i != col && board[row][col] == board[row][i])
				return false;
			if (i != row && board[row][col] == board[i][col])
				return false;
			int r = sRow*NUM + i/NUM, c = sCol*NUM + i%NUM;
			if (!(r == row && c == col) && board[row][col] == board[r][c])
				return false;
		}
		return true;
	}

	bool solveSudoku(vector
   
     > &board) { for (int i = 0; i < SQUNUM; i++) { for (int j = 0; j < SQUNUM; j++) { if (board[i][j] == '.') { //本程序精华：主要的回溯思想就是这个循环和递归体现出来 //1. 逐个可行答案'1'->'9'去填写试一试是否可行 for (char a = '1'; a <= '9'; a++) { //填写 board[i][j] = a; //测试是否可行 if (isValid(board, i, j) && solveSudoku(board)) //可行返回真 return true; //不可行，回溯，即回到本次回溯前的状态 board[i][j] = '.'; } //本格不符合规则，那么就可以马上返回了，所以不用到所有循环外。 //就是不用等到之后的循环完了。 return false; } } } //别忘记了最后，i==9&&j==9的时候跳出循环，这个时候就是成功了，要返回true return true; }