LeetCode Sudoku Solver

早就见过数独的题了，一看就头疼，也没认真看过，这里遇见了，好似久违的敌人和朋友，终于可以切磋一下了。想到了回溯法，没想用，看了几个例子在这上面的http://www.sudokuhints.com/，这里的例子确实特别好，而且易懂，想看看有没有什么规律，果然找到了规律（简单说来就是：寻找那些独一无二的点，即某些点只能有一个唯一的值才满足横约束、竖约束和3*3小格子约束，一个一个点判断，寻找这样的点先填入，然后判断是否所有点都填完了，所有点都填完了就完成了数独），一晚上的时间实现了，测了几个例子都好使，提交上去了却不行了。调试了一下，问题是：有些题目（可能是由于给的点少了一点）会出现死循环，就是不存在任何唯一的点（这样的题目应该是有超出一个解的），所以程序没法执行了，可能程序已经填了好多点，只是生一小部分的点有不唯一。比如例子["..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."]

这是题目给的。用我的程序处理后只能到这里：此时程序找不到唯一的点了。我倒没想到更好地解决这问题（其实解决这问题就是对那些可能的点进行测试了，这其实就是回溯了，估计也只能回溯了）。但由于我的程序没有递归速度应该更快。于是就做了个实验，把题目的数独先用我的程序跑一遍，再用回溯法，果然结果如下：

是快了不少，所有程序和例子如下：

// LeetCode_ValidSudoku.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;

bool isValidSudoku(vector<vector<char> > &board) {
	map<char,int> mp;
	for (int i=0;i<9;i++)
	{
		mp.clear();
		for (int j=0;j<9;j++)
		{
			mp[board[i][j]]++;
			if (mp[board[i][j]]>1&&board[i][j]!='.')
			{
				return false;
			}
		}
	}
	for (int j=0;j<9;j++)
	{
		mp.clear();
		for (int i=0;i<9;i++)
		{
			mp[board[i][j]]++;
			if (mp[board[i][j]]>1&&board[i][j]!='.')
			{
				return false;
			}
		}
	}
	for (int m=0;m<9;m+=3)
	{
		for (int n=0;n<9;n+=3)
		{
			mp.clear();
			for (int i=m;i<m+3;i++)
			{
				for (int j=n;j<n+3;j++)
				{
					mp[board[i][j]]++;
					if (mp[board[i][j]]>1&&board[i][j]!='.')
					{
						return false;
					}
				}
			}
		}
	}
	return true;
}

set<char> exceptValueSet(vector<vector<char> > &board,int m,int n)
{
	//cout<<" in exceptValueSet "<<endl;
	set<char> ret;
	for (int i=0;i<9;i++)
	{
		if (board[m][i]!='.')// m row
		{
			ret.insert(board[m][i]);
		}
	}
	for (int i=0;i<9;i++)
	{
		if (board[i][n]!='.')//n column
		{
			ret.insert(board[i][n]);
		}
	}
	int p=0,q=0;
	while(p<=m) p+=3;
	while(q<=n) q+=3;
	p -= 3;
	q -= 3;
	for (int i=p;i<p+3;i++)
	{
		for (int j=q;j<q+3;j++)
		{
			if (board[i][j]!='.')//3*3 grid
			{
				ret.insert(board[i][j]);
			}
		}
	}
	return ret;
}
bool testRowUnique(vector<vector<char> > &board,int row,char ch)
{
	//cout<<" in testRowUnique "<<endl;
	for(int i=0;i<9;i++)
	{
		if (board[row][i]==ch)
		{
			return true;
		}
	}
	return false;
}
bool testColumnUnique(vector<vector<char> > &board,int column,char ch)
{
	//cout<<" in testColumnUnique "<<endl;
	for(int i=0;i<9;i++)
	{
		if (board[i][column]==ch)
		{
			return true;
		}
	}
	return false;
}
bool testGridUnique(vector<vector<char> > &board,int m,int n,char ch)//test row and column,once conflict return false;
{
	for (int i=0;i<9;i++)
	{
		if (board[m][i]==ch)
		{
			return false;
		}
	}
	for (int i=0;i<9;i++)
	{
		if (board[i][n]==ch)
		{
			return false;
		}
	}
	return true;
}
bool testUnique(vector<vector<char> > &board,int m,int n,char ch)
{
	//cout<<" in testUnique "<<endl;
	int p=0,q=0;
	while(p<=m) p+=3;
	while(q<=n) q+=3;
	p -= 3;
	q -= 3;
	for (int i=p;i<p+3;i++)//row testunique
	{
		if (i!=m&&board[i][n]=='.')//3*3 grid
		{
			if (!testRowUnique(board,i,ch))
			{
				return false;
			}
		}
	}
	for (int j=q;j<q+3;j++)
	{
		if (j!=n&&board[m][j]=='.')//colun testunique
		{
			if (!testColumnUnique(board,j,ch))
			{
				return false;
			}
		}
	}
	for (int i=p;i<p+3;i++)
	{
		for (int j=q;j<q+3;j++)
		{
			if (i==m&&j==n)
			{
				continue;
			}
			if (board[i][j]=='.')//3*3 grid means that each ij should be invalid except for mn
			{
				if (testGridUnique(board,i,j,ch))//if there is one can be placed in the i j position then not unique
				{
					return false;
				}
			}
		}
	}
	return true;
}
bool isFinished(vector<vector<char> > &board)
{
	for (int i=0;i<9;i++)
	{
		for (int j=0;j<9;j++)
		{
			if (board[i][j]=='.')
			{
				return false;
			}
		}
	}
	return true;
}
void solveSudoku1(vector<vector<char> > &board) {
	set<char> expValueSet;
	bool flag = true;
	while(!isFinished(board)&&flag)
	{
		flag = false;
		for (int i=0;i<9;i++)
		{
			for (int j=0;j<9;j++)
			{
				if (board[i][j]=='.')
				{
					expValueSet.clear();
					expValueSet = exceptValueSet(board,i,j);
					for (char c='1';c<='9';c++)//possible char
					{
						//cout<<" i is "<<i<<" j is "<<j<<" char is "<<c<<endl;
						if(expValueSet.find(c)==expValueSet.end())
						{
							if (testUnique(board,i,j,c))
							{
								//cout<<" in  test Unique "<<endl;
								board[i][j] = c;
								flag = true;
							}
						}
					}
				}
			}
		}
	}
}

bool isValid(vector<vector<char> > &board, int a, int b) {
	int i,j;
	for(i = 0; i < 9; i++)
		if(i != a && board[i][b] == board[a][b])
			return false;

	for(j = 0; j < 9; j++)
		if(j != b && board[a][j] == board[a][b])
			return false;

	int x = a/3*3;
	int y = b/3*3;
	for(i = 0; i < 3; i++)
		for(j = 0; j< 3; j++)
			if(x+i != a && y+j != b && board[x+i][y+j] == board[a][b])
				return false;
	return true;
}

bool solveSudokudfs(vector<vector<char> > &board)
{
	for(int i = 0; i < 9; i++)
		for(int j = 0; j < 9; j++)
		{
			if(board[i][j] == '.')
			{
				for(int k = 1; k <= 9; k++)
				{
					board[i][j] = '0' + k;
					if(isValid(board,i,j) && solveSudokudfs(board))
						return true;
					board[i][j] = '.';//this is necessary to recovery the board to the last recursive 
				}
				return false;
			}
		}
		return true;
}


void solveSudoku2(vector<vector<char> > &board) {
	// Note: The Solution object is instantiated only once.
	solveSudokudfs(board);
}

int _tmain(int argc, _TCHAR* argv[])//test case from http://www.sudokuhints.com/
{
	vector<vector<char> > board;
	vector<char> vec;
	/*vec.push_back('4');vec.push_back('6');vec.push_back('3');vec.push_back('7');vec.push_back('2');vec.push_back('8');vec.push_back('9');vec.push_back('5');vec.push_back('1');
	board.push_back(vec);
	vec.clear();
	vec.push_back('2');vec.push_back('5');vec.push_back('9');vec.push_back('4');vec.push_back('6');vec.push_back('1');vec.push_back('7');vec.push_back('3');vec.push_back('8');
	board.push_back(vec);
	vec.clear();
	vec.push_back('7');vec.push_back('8');vec.push_back('1');vec.push_back('3');vec.push_back('5');vec.push_back('9');vec.push_back('6');vec.push_back('4');vec.push_back('2');
	board.push_back(vec);
	vec.clear();
	vec.push_back('5');vec.push_back('3');vec.push_back('2');vec.push_back('1');vec.push_back('9');vec.push_back('7');vec.push_back('4');vec.push_back('8');vec.push_back('6');
	board.push_back(vec);
	vec.clear();
	vec.push_back('9');vec.push_back('1');vec.push_back('4');vec.push_back('6');vec.push_back('8');vec.push_back('2');vec.push_back('5');vec.push_back('7');vec.push_back('3');
	board.push_back(vec);
	vec.clear();
	vec.push_back('6');vec.push_back('7');vec.push_back('8');vec.push_back('5');vec.push_back('4');vec.push_back('3');vec.push_back('1');vec.push_back('2');vec.push_back('9');
	board.push_back(vec);
	vec.clear();
	vec.push_back('8');vec.push_back('2');vec.push_back('6');vec.push_back('9');vec.push_back('7');vec.push_back('5');vec.push_back('3');vec.push_back('1');vec.push_back('4');
	board.push_back(vec);
	vec.clear();
	vec.push_back('1');vec.push_back('4');vec.push_back('7');vec.push_back('2');vec.push_back('3');vec.push_back('6');vec.push_back('8');vec.push_back('9');vec.push_back('5');
	board.push_back(vec);
	vec.clear();
	vec.push_back('3');vec.push_back('9');vec.push_back('5');vec.push_back('8');vec.push_back('1');vec.push_back('4');vec.push_back('2');vec.push_back('6');vec.push_back('7');
	board.push_back(vec);
	vec.clear();*/
	//////////////////////////////////////////////////////////////////////////
	
	/*vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('6');vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('.');
	board.push_back(vec);
	vec.clear();
	vec.push_back('.');vec.push_back('8');vec.push_back('.');vec.push_back('3');vec.push_back('.');vec.push_back('2');vec.push_back('.');vec.push_back('4');vec.push_back('.');
	board.push_back(vec);
	vec.clear();
	vec.push_back('.');vec.push_back('.');vec.push_back('5');vec.push_back('.');vec.push_back('4');vec.push_back('.');vec.push_back('9');vec.push_back('.');vec.push_back('.');
	board.push_back(vec);
	vec.clear();
	vec.push_back('.');vec.push_back('7');vec.push_back('.');vec.push_back('4');vec.push_back('.');vec.push_back('5');vec.push_back('.');vec.push_back('8');vec.push_back('.');
	board.push_back(vec);
	vec.clear();
	vec.push_back('8');vec.push_back('.');vec.push_back('4');vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('7');vec.push_back('.');vec.push_back('1');
	board.push_back(vec);
	vec.clear();
	vec.push_back('.');vec.push_back('1');vec.push_back('.');vec.push_back('8');vec.push_back('.');vec.push_back('6');vec.push_back('.');vec.push_back('3');vec.push_back('.');
	board.push_back(vec);
	vec.clear();
	vec.push_back('.');vec.push_back('.');vec.push_back('7');vec.push_back('.');vec.push_back('3');vec.push_back('.');vec.push_back('6');vec.push_back('.');vec.push_back('.');
	board.push_back(vec);
	vec.clear();
	vec.push_back('.');vec.push_back('5');vec.push_back('.');vec.push_back('1');vec.push_back('.');vec.push_back('9');vec.push_back('.');vec.push_back('7');vec.push_back('.');
	board.push_back(vec);
	vec.clear();
	vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('8');vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('.');
	board.push_back(vec);
	vec.clear();*/

	vec.push_back('.');vec.push_back('.');vec.push_back('9');vec.push_back('7');vec.push_back('4');vec.push_back('8');vec.push_back('.');vec.push_back('.');vec.push_back('.');
	board.push_back(vec);
	vec.clear();
	vec.push_back('7');vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('.');
	board.push_back(vec);
	vec.clear();
	vec.push_back('.');vec.push_back('2');vec.push_back('.');vec.push_back('1');vec.push_back('.');vec.push_back('9');vec.push_back('.');vec.push_back('.');vec.push_back('.');
	board.push_back(vec);
	vec.clear();
	vec.push_back('.');vec.push_back('.');vec.push_back('7');vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('2');vec.push_back('4');vec.push_back('.');
	board.push_back(vec);
	vec.clear();
	vec.push_back('.');vec.push_back('6');vec.push_back('4');vec.push_back('.');vec.push_back('1');vec.push_back('.');vec.push_back('5');vec.push_back('9');vec.push_back('.');
	board.push_back(vec);
	vec.clear();
	vec.push_back('.');vec.push_back('9');vec.push_back('8');vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('3');vec.push_back('.');vec.push_back('.');
	board.push_back(vec);
	vec.clear();
	vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('8');vec.push_back('.');vec.push_back('3');vec.push_back('.');vec.push_back('2');vec.push_back('.');
	board.push_back(vec);
	vec.clear();
	vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('6');
	board.push_back(vec);
	vec.clear();
	vec.push_back('.');vec.push_back('.');vec.push_back('.');vec.push_back('2');vec.push_back('7');vec.push_back('5');vec.push_back('9');vec.push_back('.');vec.push_back('.');
	board.push_back(vec);
	vec.clear();


	//["..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."]
	//////////////////////////////////////////////////////////////////////////
	cout<<isValidSudoku(board)<<endl;
	for (int i=0;i<9;i++)
	{
		for (int j=0;j<9;j++)
		{
			cout<<board[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<"after solveSudoku1"<<endl;
	solveSudoku1(board);
	for (int i=0;i<9;i++)
	{
		for (int j=0;j<9;j++)
		{
			cout<<board[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<"after solveSudoku2"<<endl;
	solveSudoku2(board);
	for (int i=0;i<9;i++)
	{
		for (int j=0;j<9;j++)
		{
			cout<<board[i][j]<<" ";
		}
		cout<<endl;
	}
	system("pause");
	return 0;
}