Recursion return difficulties

closed account (9hX8C542)
Test_1
Last edited on
Using a backtracking algorithm:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>

bool validity_check(int sudoku[9][9], int n, int p, int q)
{
   for (int i { }; i < 9; i++)
   {
      if (sudoku[p][i] == n && q != i) { return false; }
   }

   for (int i { }; i < 9; i++)
   {
      if (sudoku[i][q] == n && p != i) { return false; }
   }

   int bx { q / 3 };
   int by { p / 3 };

   for (int i { by * 3 }; i < by * 3 + 3; i++)
   {
      for (int j { bx * 3 }; j < bx * 3 + 3; j++)
      {
         if (sudoku[i][j] == n && i != p && j != q) { return false; }
      }
   }
   return true;
}

int blank(int sudoku[9][9], int* r, int* c)
{
   for (*r = 0; *r < 9; (*r)++)
   {
      for (*c = 0; *c < 9; (*c)++)
      {
         if (sudoku[*r][*c] == 0) { return 1; }
      }
   }
   return 0;
}

bool solver(int sudoku[9][9])
{
   int row { };
   int col { };
   int x   { -1 };
   int y   { -1 };

   if (!blank(sudoku, &row, &col)) { return 1; }

   for (int i { 1 }; i <= 9; i++)
   {
      if (validity_check(sudoku, i, row, col))
      {
         sudoku[row][col] = i;

         if (solver(sudoku)) { return true; }

         sudoku[row][col] = 0;
      }
   }
   return false;
}

void print_sudoku(int sudoku[9][9])
{
   for (int i { }; i < 9; i++)
   {
      for (int j { }; j < 9; j++)
      {
         std::cout << sudoku[i][j] << "  ";
      }
      std::cout << "\n\n";
   }
}

int main()
{
   int sudoku[9][9] = { {3, 0, 6, 5, 0, 8, 4, 0, 0},
                        {5, 2, 0, 0, 0, 0, 0, 0, 0},
                        {0, 8, 7, 0, 0, 0, 0, 3, 1},
                        {0, 0, 3, 0, 1, 0, 0, 8, 0},
                        {9, 0, 0, 8, 6, 3, 0, 0, 5},
                        {0, 5, 0, 0, 9, 0, 6, 0, 0},
                        {1, 3, 0, 0, 0, 0, 2, 5, 0},
                        {0, 0, 0, 0, 0, 0, 0, 7, 4},
                        {0, 0, 5, 2, 0, 6, 3, 0, 0} };

   std::cout << "-------------------------\n";

   if (solver(sudoku) == true)
   {
      std::cout << "         SOLVED!         \n";
      std::cout << "-------------------------\n";
      print_sudoku(sudoku);
   }
   else
   {
      std::cout << "Solution Does Not Exist!\n";
   }
}

https://obnoxiousblueshift.wordpress.com/2019/06/10/sudoku-solver-in-c/
If array[x][y] is not zero, solve() returns an undefined value to the caller, which completely screws up the backtracking logic. You forgot to specify what the function should do if the current cell is part of the original problem. Also, the function should clear the value it wrote into array[x][y] before returning false, or its leftover data could again mess with the backtracking from the upper recursive levels.

http://www.cplusplus.com/forum/lounge/29126/#msg157845
Topic archived. No new replies allowed.