Understanding the retrospective algorithm (as an example of several games, use C ++ implementation)

Algorithm thought:

Rules of Sudoku game:

Every line uses 1, 2, 3, 4, 5 , 6, 7, 8, 9 positions are not limited;

Each column uses 1, 2, 3, 4, 5, 6, 7, 8, 9 positions are not limited;

< p>Every 3×3 grid (a total of nine such grids) uses 1, 2, 3, 4, 5, 6, 7, 8, and 9 positions.

The process of the game is to fill in the blanks with 1, 2, 3, 4, 5, 6, 7, 8, 9, and require that each row, each column, and each nine-square grid use 1, 2 , 3, 4, 5, 6, 7, 8, 9.
How to implement:

Since Sudoku is 9 *9, so the solution space has 81 layers, and each layer has 9 branches. What we do is to traverse this solution space. If you find all the solutions, you can save them when they appear:

 1 #include < span style="color: #800000;">"stdafx.h" span>

 2 #include

 3 #include"stdlib.h"

 4 #include

 5 #include

 6 #include

 7 #include

 8 using  namespace std;

 9 vectorchar>> >sum;

10 bool check(vectorchar>> &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, vectorchar> >& 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] == '.'< /span>)

41  {

42 for (int i = 1; i <10; i++)

43  {

44 board[x][y] = i + ' span>0';

45 if (check(board, num))

46  {

47 dfs(num + 1, board);

48 }

49

50 }

51 board[x][y] = ' .';//if If there is no value that meets the condition, restore the original point value, go back up, change the value of the parent node, and recalculate until the value of the first position of the root node traverses to 9.

52 }

53 else

54  {

55 dfs(num + 1, board);

56 }

57 }

58 }

59 void solveSudoku(vectorchar> >& 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, '.< span style="color: #800000;">');

67 vectorchar>> board( 9, temp);

68 for (int i = 0; i) {

69 for (int j = 0; j) {

70 board[i][j] = myboard[i][ j];

71 }

72 }

73  solveSudoku(board);

74 for (int k = 0; k) {

75 for (int i = 0; i) {

76 for (int j = 0; 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 }

 1 #include "stdafx.h"

 2 #include

 3 #include"stdlib.h"

 4 #include

 5 #include

 6 #include

 7 #include

 8 using  namespace std;

 9 vectorchar>> >sum;

10 bool check(vectorchar>> &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, vectorchar> >& 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] == '.'< /span>)

41  {

42 for (int i = 1; i <10; i++)

43  {

44 board[x][y] = i + ' span>0';

45 if (check(board, num))

46  {

47 dfs(num + 1, board);

48 }

49

50 }

51 board[x][y] = ' .';//if If there is no value that meets the condition, restore the original point value, go back up, change the value of the parent node, and recalculate until the value of the first position of the root node traverses to 9.

52 }

53 else

54  {

55 dfs(num + 1, board);

56 }

57 }

58 }

59 void solveSudoku(vectorchar> >& 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, '.< span style="color: #800000;">');

67 vectorchar>> board( 9, temp);

68 for (int i = 0; i) {

69 for (int j = 0; j) {

70 board[i][j] = myboard[i][ j];

71 }

72 }

73  solveSudoku(board);

74 for (int k = 0; k) {

75 for (int i = 0; i) {

76 for (int j = 0; 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 }