早就见过数独的题了，一看就头疼，也没认真看过，这里遇见了，好似久违的敌人和朋友，终于可以切磋一下了。想到了回溯法，没想用，看了几个例子在这上面的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;
}
转载于:https://www.cnblogs.com/riasky/p/3481907.html