#include #include #include #include #include using namespace std; int Visited = 0; struct Coord { int iVal; int jVal; }; vector> newBoard; int FindBox(int i, int j) { if ((i == 0 or i == 1 or i == 2) and (j == 0 or j == 1 or j == 2)) return 1; else if ((i == 0 or i == 1 or i == 2) and (j== 3 or j == 4 or j ==5)) return 2; else if ((i == 0 or i == 1 or i == 2) and (j== 6 or j == 7 or j ==8)) return 3; else if ((i == 3 or i == 4 or i == 5) and (j == 0 or j == 1 or j == 2)) return 4; else if ((i == 3 or i == 4 or i == 5) and (j== 3 or j == 4 or j ==5)) return 5; else if ((i == 3 or i == 4 or i == 5) and (j== 6 or j == 7 or j ==8)) return 6; else if ((i == 6 or i == 7 or i == 8) and (j == 0 or j == 1 or j == 2)) return 7; else if ((i == 6 or i ==7 or i == 8) and (j== 3 or j == 4 or j ==5)) return 8; else if ((i == 6 or i == 7 or i == 8) and (j== 6 or j == 7 or j ==8)) return 9; } vector difference(vector v1, vector v2){ vector result; set s1(v1.begin(), v1.end()); set s2(v2.begin(), v2.end()); set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(result)); return result; } vector Candidates(vector> Board, int i, int j) { vector result; vector OneToNine; OneToNine.push_back(1); OneToNine.push_back(2); OneToNine.push_back(3); OneToNine.push_back(4); OneToNine.push_back(5); OneToNine.push_back(6); OneToNine.push_back(7); OneToNine.push_back(8); OneToNine.push_back(9); int p = i; int o = j; for (p; p >=0; p--){ if (Board[p][j] != 0) result.push_back(Board[p][j]); } p = i; for (p; p <= 8; p++){ if (Board[p][j] != 0) result.push_back(Board[p][j]); } for (o; o >= 0; o--) { if (Board[i][o] != 0) result.push_back(Board[i][o]); } o = j; for(o; o <= 8; o++) { if (Board[i][o] != 0) result.push_back(Board[i][o]); } int Region = FindBox(i,j); if (Region == 1) { result.push_back(Board[0][0]); result.push_back(Board[0][1]); result.push_back(Board[0][2]); result.push_back(Board[1][0]); result.push_back(Board[1][1]); result.push_back(Board[1][2]); result.push_back(Board[2][0]); result.push_back(Board[2][1]); result.push_back(Board[2][2]); } else if (Region == 2) { result.push_back(Board[0][3]); result.push_back(Board[0][4]); result.push_back(Board[0][5]); result.push_back(Board[1][3]); result.push_back(Board[1][4]); result.push_back(Board[1][5]); result.push_back(Board[2][3]); result.push_back(Board[2][4]); result.push_back(Board[2][5]); } else if (Region == 3) { result.push_back(Board[0][6]); result.push_back(Board[0][7]); result.push_back(Board[0][8]); result.push_back(Board[1][6]); result.push_back(Board[1][7]); result.push_back(Board[1][8]); result.push_back(Board[2][6]); result.push_back(Board[2][7]); result.push_back(Board[2][8]); } else if (Region == 4) { result.push_back(Board[3][0]); result.push_back(Board[3][1]); result.push_back(Board[3][2]); result.push_back(Board[4][0]); result.push_back(Board[4][1]); result.push_back(Board[4][2]); result.push_back(Board[5][0]); result.push_back(Board[5][1]); result.push_back(Board[5][2]); } else if (Region == 5) { result.push_back(Board[3][3]); result.push_back(Board[3][4]); result.push_back(Board[3][5]); result.push_back(Board[4][3]); result.push_back(Board[4][4]); result.push_back(Board[4][5]); result.push_back(Board[5][3]); result.push_back(Board[5][4]); result.push_back(Board[5][5]); } else if (Region == 6) { result.push_back(Board[3][6]); result.push_back(Board[3][7]); result.push_back(Board[3][8]); result.push_back(Board[4][6]); result.push_back(Board[4][7]); result.push_back(Board[4][8]); result.push_back(Board[5][6]); result.push_back(Board[5][7]); result.push_back(Board[5][8]); } else if (Region == 7) { result.push_back(Board[6][0]); result.push_back(Board[6][1]); result.push_back(Board[6][2]); result.push_back(Board[7][0]); result.push_back(Board[7][1]); result.push_back(Board[7][2]); result.push_back(Board[8][0]); result.push_back(Board[8][1]); result.push_back(Board[8][2]); } else if (Region == 8) { result.push_back(Board[6][3]); result.push_back(Board[6][4]); result.push_back(Board[6][5]); result.push_back(Board[7][3]); result.push_back(Board[7][4]); result.push_back(Board[7][5]); result.push_back(Board[8][3]); result.push_back(Board[8][4]); result.push_back(Board[8][5]); } else if (Region == 9) { result.push_back(Board[6][6]); result.push_back(Board[6][7]); result.push_back(Board[6][8]); result.push_back(Board[7][6]); result.push_back(Board[7][7]); result.push_back(Board[7][8]); result.push_back(Board[8][6]); result.push_back(Board[8][7]); result.push_back(Board[8][8]); } result = difference(OneToNine, result); return result; } Coord FirstZero(vector> Board){ for (int i = 0; i < Board.size(); i++) { for (int j = 0; j < Board.size(); j++){ if (Board[i][j] == 0) { Coord FZ; FZ.iVal = i; FZ.jVal = j; return FZ; } } } Coord FAIL; FAIL.iVal = -1; FAIL.jVal = -1; return FAIL; } vector> GenerateBoard(){ vector> B; vector row; for (int p = 1; p <=9; p++){ for (int i = 1; i <= 9; i++){ row.push_back(0); } B.push_back(row); row.clear(); } return B; } bool DFS_Solve(vector> T){ vector cands; Coord BaseCase; BaseCase = FirstZero(T); Visited++; if (BaseCase.iVal == -1 && BaseCase.jVal == -1){ for (int i = 0; i < T.size(); i++){ for (int j = 0; j < T[i].size(); j++) { cout << T[i][j] << " "; } cout << endl; } return true; } else cands = Candidates(T, BaseCase.iVal, BaseCase.jVal); for (int j = 0; j < cands.size(); j++) { T[BaseCase.iVal][BaseCase.jVal] = cands[j]; if (DFS_Solve(T)){ return true; } } return false; } int main(){ vector cand; vector> Board; Board = GenerateBoard(); Board[0][0] = 8; Board[0][1] = 5; Board[0][5] = 2; Board[0][6] = 4; Board[1][0] = 7; Board[1][1] = 2; Board[1][8] = 9; Board[2][2] = 4; Board[3][3] = 1; Board[3][5] = 7; Board[3][8] = 2; Board[4][0] = 3; Board[4][2] = 5; Board[4][6] = 9; Board[5][1] = 4; Board[6][4] = 8; Board[6][7] = 7; Board[7][1] = 1; Board[7][2] = 7; Board[8][4] = 3; Board[8][5] = 6; Board[8][7] = 4; /* Board[0][0] = 6; Board[0][1] = 8; Board[0][2] = 4; Board[0][3] = 9; Board[0][4] = 7; Board[0][5] = 3; Board[0][6] = 2; Board[0][7] = 1; Board[0][8] = 5; Board[1][3] = 5; Board[1][4] = 1; Board[2][1] = 5; Board[2][2] = 2; Board[2][7] = 9; Board[3][0] = 1; Board[3][3] = 6; Board[3][6] = 4; Board[3][7] = 3; Board[4][1] = 9; Board[4][7] = 8; Board[5][1] = 7; Board[5][2] = 6; Board[5][5] = 8; Board[5][8] = 9; Board[6][1] = 4; Board[6][6] = 1; Board[6][7] = 2; Board[7][4] = 9; Board[7][5] = 1; Board[8][2] = 1; Board[8][3] = 2; Board[8][4] = 8; Board[8][8] = 3;*/ Coord FZ = FirstZero(Board); for (int i = 0; i < Board.size(); i++){ for (int j = 0; j < Board[i].size(); j++) { cout << Board[i][j] << " "; } cout << endl; } cout << endl; cand = Candidates(Board, 1, 5); bool solve; solve = DFS_Solve(Board); cout << endl << "SOLVE... 1 FOR COMPLETE 0 FOR INCOMPLETE: " << solve << endl; cout << "Nodes visited: " << Visited << endl; return 0; }