1 #include "stdafx.h"
 2 #include<stdio.h>
 3 #include"stdlib.h"
 4 #include<iostream>
 5 #include<ctype.h>
 6 #include<vector>
 7 #include<algorithm>
 8 using namespace std;
 9 vector<vector<vector<char> > >sum;
10 bool check(vector<vector<char> > &board,int k)
11 {
12     int x = k / 9;
13     int y = k % 9;
14     for (int i = 0; i < 9; i++)
15     {
16         if (i != x&&board[x][y] == board[i][y])
17             return false;
18     }
19     for (int j = 0; j < 9; j++)
20     {
21         if (j != y&&board[x][y] == board[x][j])
22             return false;
23     }
24     for (int i = 3 * (x / 3); i < 3 * (x / 3 + 1); i++)
25         for (int j = 3 * (y/3); j < 3 * (y / 3 + 1); j++)
26             if (i != x&&j != y&&board[i][j] == board[x][y])
27                 return false;
28     return true;
29 }
30 void dfs(int num, vector<vector<char> >& board)
31 {
32     if (num == 81)
33     {
34         sum.push_back(board);
35         return;
36     }
37     else {
38         int x = num / 9;
39         int y = num % 9;
40         if (board[x][y] == \'.\')
41         {
42             for (int i = 1; i < 10; i++)
43             {
44                 board[x][y] = i + \'0\';
45                 if (check(board, num))
46                 {
47                     dfs(num + 1, board);
48                 }
49 
50             }
51             board[x][y] = \'.\';//如果没有满足条件的数值，则恢复原来点值，向上回溯，改变父节点的值，重新往下计算，直到根节点第一个位置的值遍历到9为止。
52         }
53         else
54         {
55             dfs(num + 1, board);
56         }
57     }
58 }
59 void solveSudoku(vector<vector<char> >& board)
60 {
61     dfs(0,board);
62 }
63 int main()
64 {
65     vector<string> myboard({ "...748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.." });
66     vector<char> temp(9, \'.\');
67     vector<vector<char> > board(9, temp);
68     for (int i = 0; i<myboard.size(); i++) {
69         for (int j = 0; j<myboard[i].length(); j++) {
70             board[i][j] = myboard[i][j];
71         }
72     }
73     solveSudoku(board);
74     for (int k = 0; k<sum.size(); k++) {
75         for (int i = 0; i<sum[k].size(); i++) {
76             for (int j = 0; j<sum[k][i].size(); j++) {
77                 cout << sum[k][i][j] << " ";
78             }
79             cout << endl;
80         }
81         cout << "######" << endl;
82     }
83     cout << "sum is " << sum.size() << endl;
84     cout << "Hello world!" << endl;
85     system("pause");
86     return 0;
87 }