37. 解数独

编写一个程序,通过填充空格来解决数独问题。

数独的解法需 遵循如下规则:

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
数独部分空格内已填入了数字,空白格用 '.' 表示。

 

示例:


输入:board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出:[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

解释:输入的数独如上图所示,唯一有效的解决方案如下所示:

37. 解数独

 

 

提示:

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据 保证 输入数独仅有一个解

 

 

#include<iostream>
#include<stack>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
/*
对于每个需要填数字的格子带入1到9,每代入一个数字都判定其是否合法,
如果合法就继续下一次递归,结束时把数字设回 '.',
判断新加入的数字是否合法时,只需要判定当前数字是否合法,
不需要判定这个数组是否为数独数组,因为之前加进的数字都是合法的,
这样可以使程序更加高效一些,整体思路是这样的,
但是实现起来可以有不同的形式。
一种实现形式是递归带上横纵坐标,由于是一行一行的填数字,
且是从0行开始的,所以当i到达9的时候,
说明所有的数字都成功的填入了,直接返回 ture。
当j大于等于9时,当前行填完了,需要换到下一行继续填,则继续调用递归函数,
横坐标带入 i+1。否则看若当前数字不为点,
说明当前位置不需要填数字,则对右边的位置调用递归。
若当前位置需要填数字,则应该尝试填入1到9内的所有数字,
让c从1遍历到9,每当试着填入一个数字,
都需要检验是否有冲突,使用另一个子函数 isValid 来检验是否合法,
假如不合法,则跳过当前数字。若合法,则将当前位置赋值为这个数字,
并对右边位置调用递归,若递归函数返回 true,
则说明可以成功填充,直接返回 true。不行的话,需要重置状态,
将当前位置恢复为点。若所有数字都尝试了,还是不行,则最终返回 false。
*/

class Solution {
public:
	void solveSudoku(vector<vector<char>>& board) 
	{
		helper(board);
	}
	bool helper(vector<vector<char>>& board) 
	{
		for (int i = 0; i < 9; ++i) 
		{
			for (int j = 0; j < 9; ++j) 
			{
				if (board[i][j] != '.')
				{
					continue;
				}
				for (char c = '1'; c <= '9'; ++c) 
				{
					if (!isValid(board, i, j, c))
					{
						continue;
					}
					board[i][j] = c;
					if (helper(board))
					{
						return true;
					}
					board[i][j] = '.';
				}
				return false;
			}
		}
		return true;
	}
	bool isValid(vector<vector<char>>& board, int i, int j, char val) 
	{
		for (int k = 0; k < 9; ++k) 
		{
			if (board[k][j] != '.' && board[k][j] == val)
			{
				return false;
			}
			if (board[i][k] != '.' && board[i][k] == val)
			{
				return false;
			}
			int row = i / 3 * 3 + k / 3, col = j / 3 * 3 + k % 3;
			if (board[row][col] != '.' && board[row][col] == val)
			{
				return false;
			}
		}
		return true;
	}
};

  







上一篇:37岁找工作无果,*创业的程序员记录创业史


下一篇:OCP 071【中文】考试题库(cuug整理)第37题