#include stdafx.h #include #include #include #include using namespace std; bool isValidSudoku(vector > &board) { map 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 1&&board[i][j]!='.') { return false; } } } } } return true; } set exceptValueSet(vector > &board,int m,int n) { //cout<< in exceptValueSet < 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 > &board,int row,char ch) { //cout<< in testRowUnique < > &board,int column,char ch) { //cout<< in testColumnUnique < > &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 > &board,int m,int n,char ch) { //cout<< in testUnique < > &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 > &board) { set 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 < > &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 > &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 > &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 > board; vector 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.
