C++

Forum

 
C++ Sudoku Solver - why is it that slow?

sirprize3 (1)
Hey,

I am new to C++ and I am trying to code a sudoku solver that makes use of recursive function calls.

It seems like it would work with pretty simple sudokus, but as soon as it gets a bit more complex, it takes infinitely.
The idea behind it should work however, as Computerphile showed in his sudoku solver video.

Can you please have a look at my code and give me hints on what I have done wrong?

Because of the length, I have uploaded it to pastebin:
Main: https://pastebin.com/UZpsezGm
"Grid" class .cpp: https://pastebin.com/c19AC467
"Grid" class .h: https://pastebin.com/xu4T7jcL

Thanks in advance!
ne555 (10692)
you are kind of trying every possibility, there are a lot of possibilities, it's going to take a lot of time
anup30 (968)
can it solve now the 'easiest' sudoku? where is the recursive function call in your code?
anup30 (968)
here is your code in one page:
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
100
101
102
103
104
105
106
 
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class Grid /////////////////////////////////
{
public:
	bool checkPossible(unsigned int digit, unsigned int columnNr, unsigned int lineNr);
	bool checkFinished();
	void print();
	bool solve();

private:
	unsigned int _grid[9][9] = {
			{5, 3, 10, 10, 7, 10, 10, 10, 10},
			{6, 10, 10, 1, 9, 5, 10, 10, 10},
			{10, 9, 8, 10, 10, 10, 10, 6, 10},
			{8, 10, 10, 10, 6, 10, 10, 10, 3},
			{4, 10, 10, 8, 10, 3, 10, 10, 1},
			{7, 10, 10, 10, 2, 10, 10, 10, 6},
			{10, 6, 10, 10, 10, 10, 2, 8, 10},
			{10, 10, 10, 4, 1, 9, 10, 10, 10}
	};
};

bool Grid::checkPossible(unsigned int digit, unsigned int columnNr, unsigned int lineNr) { ////////////
 
	for (int i = 0; i < 9; ++i) {
		if(_grid[lineNr][i] == digit)
			 return false;
	}
	for (int i = 0; i < 9; ++i) {
		if(_grid[i][columnNr] == digit)
			return false;
	}
	unsigned int columnNr0 = (std::floor(columnNr/3))*3;
	unsigned int lineNr0 = (std::floor(lineNr/3))*3;
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			if(_grid[columnNr0+i][lineNr0+j] == digit)
				return false;
		}
	}
	return true;
}
 
bool Grid::checkFinished() { /////////////////////
	for (unsigned int i = 0; i < 9; i++)
	{
		for (unsigned int j = 0; j < 9; j++)
		{
			if (_grid[j][i] == 10) {
				return false;
			}
		}
    }
	return true;
}
 
void Grid::print() { ///////////////////////////
	std::cout << "-------" << std::endl;
	for (unsigned x = 0; x < 9; x++)
	{
		for (unsigned int y = 0; y < 9; y++)
		{
			std::cout << _grid[x][y] << " ";
		}
		std::cout << std::endl;
	}
	std::cout << std::endl << "------" << std::endl;
}
 
bool Grid::solve() { ///////////////////////////
	for (unsigned int x = 0; x < 9 ; x++)
	{
		for (unsigned int y = 0; y < 9; y++)
		{
			if (checkFinished())
			{
				Grid::print();
				return true;
			}
 
			if (_grid[y][x] == 10) {
				for (unsigned int i = 1; i < 10; i++)
				{
					if (checkPossible(i, x, y)) {
						_grid[y][x] = i;
						if (Grid::solve())
							return true;
						_grid[y][x] = 10;
					}
				}
			}
		}
	}
	return false;
}

int main() ////////////////////////////////////////////////////////////////////
{
	Grid g;
	g.print();
	g.solve();
}

seeplus (6599)
Unless you are using recursion as an exercise, you don't need recursion to solve Sudoku - an iterative solution is available, although more complicated code but faster execution.
dhayden (5798)
There are 9 possibilities for each empty square. Your sample has 46 empty squares. That's 946 = 78,551,672,112,789,411,833,022,577,315,290,546,060,373,041 possibilities. It'll take a while to test them all. Assuming that it can do 1 check in 1ns, figure out how many years that will take.
anup30 (968)
>
Unless you are using recursion as an exercise, you don't need recursion to solve Sudoku - an iterative solution is available, although more complicated code but faster execution.

i agree. i prefer loops to recursion when possible, they are easier to understand, also previously i have coded a program where loop version was faster. imo it was wrong for the problem provider to advise to do by recursion. instead he could've hinted to solve by 'backtracking' method.

>
There are 9 possibilities for each empty square. Your sample has 46 empty squares. That's 946 = 78,551,672,112,789,411,833,022,577,315,290,546,060,373,041 possibilities. It'll take a while to test them all. Assuming that it can do 1 check in 1ns, figure out how many years that will take.

yes so many numbers. many numbers can be eliminated by row checking, column checking, and 3x3 sub-grid checking. then probably it becomes solvable in reasonable time by 'backtracking' method.
dutch (2548)
Your algorithm isn't quite right. You keep checking for possible digits in further positions even when there is no possible digit in the first position.

Also, your input grid is missing the last row (unless you mean it to be all zeroes).

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
 
#include <iostream>
using namespace std;

bool checkPossible(int grid[][9], int digit, int col, int line) {
    for (int i = 0; i < 9; ++i)
        if (grid[line][i] == digit)
             return false;
    for (int i = 0; i < 9; ++i)
        if (grid[i][col] == digit)
            return false;
    int x = col / 3 * 3, y = line / 3 * 3;
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            if (grid[y + i][x + j] == digit)
                return false;
    return true;
}

bool solve(int grid[][9], int col = 0, int line = 0) {
    while (grid[line][col] != 0) {
        if (++col > 8) {
            col = 0;
            if (++line > 8)
                return true;
        }
    }
    for (int digit = 1; digit <= 9; digit++)
        if (checkPossible(grid, digit, col, line)) {
            grid[line][col] = digit;
            if (solve(grid, col, line)) return true;
            grid[line][col] = 0;
        }
    return false;
}

void print(int grid[][9]) {
    for (int x = 0; x < 9; x++) {
        for (int y = 0; y < 9; y++)
            cout << grid[x][y] << ' ';
        cout << '\n';
    }
}

int main() {
    int grid[9][9] = {
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
    };
    print(grid);
    cout << "------\n";
    if (solve(grid))
        print(grid);
    else
        cout << "Unsolvable\n";
}

Last edited on
dutch (2548)
anup30 wrote:
i agree. i prefer loops to recursion when possible, they are easier to understand

In appropriate situations, recursion is always easier to understand. That's pretty much the point of recursion, to simplify the algorithm.

anup30 wrote:
imo it was wrong for the problem provider to advise to do by recursion. instead he could've hinted to solve by 'backtracking' method.

The recursion is what handles the backtracking in this case.

anup30 wrote:
yes so many numbers. many numbers can be eliminated by row checking, column checking, and 3x3 sub-grid checking. then probably it becomes solvable in reasonable time by 'backtracking' method.

You're completely missing the point. Even if there was only on average 2 values to test for each of the 51 empty positions above, checking a billion values per second could still take many hours.

The main problem with the OP's program is that it keeps checking further positions even after the current position has proved hopeless.
anup30 (968)
dutch wrote
The recursion is what handles the backtracking in this case.

yes in your program. but how will op know that he will(likely if not by any other method) need
backtracking?

dutch wrote
You're completely missing the point. Even if there was only on average 2 values to test for each of the 51 empty positions above, checking a billion values per second could still take many hours.

i am not getting what you mean. how do they solve by backtracking then?
dhayden (5798)
FWIW, here is the original code modified with Dutch's suggestion to work. I also added the final row (again using Dutch's numbers) and fixed a bug in the checkPossible() method:
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
100
101
102
103
104
105
106
107
108
 
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class Grid /////////////////////////////////
{
public:
	bool checkPossible(unsigned int digit, unsigned int columnNr, unsigned int lineNr);
	bool checkFinished();
	void print();
	bool solve();

private:
	unsigned int _grid[9][9] = {
			{5, 3, 10, 10, 7, 10, 10, 10, 10},
			{6, 10, 10, 1, 9, 5, 10, 10, 10},
			{10, 9, 8, 10, 10, 10, 10, 6, 10},
			{8, 10, 10, 10, 6, 10, 10, 10, 3},
			{4, 10, 10, 8, 10, 3, 10, 10, 1},
			{7, 10, 10, 10, 2, 10, 10, 10, 6},
			{10, 6, 10, 10, 10, 10, 2, 8, 10},
			{10, 10, 10, 4, 1, 9, 10, 10, 10},
			{10, 10, 10, 10, 8, 10, 10, 7, 9}
	};
};

bool Grid::checkPossible(unsigned int digit, unsigned int columnNr, unsigned int lineNr) { ////////////
 
	for (int i = 0; i < 9; ++i) {
		if(_grid[lineNr][i] == digit)
			 return false;
	}
	for (int i = 0; i < 9; ++i) {
		if(_grid[i][columnNr] == digit)
			return false;
	}
	unsigned int columnNr0 = (std::floor(columnNr/3))*3;
	unsigned int lineNr0 = (std::floor(lineNr/3))*3;
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
		    if(_grid[lineNr0+i][columnNr0+j] == digit)
				return false;
		}
	}
	return true;
}
 
bool Grid::checkFinished() { /////////////////////
	for (unsigned int i = 0; i < 9; i++)
	{
		for (unsigned int j = 0; j < 9; j++)
		{
			if (_grid[j][i] == 10) {
				return false;
			}
		}
    }
	return true;
}
 
void Grid::print() { ///////////////////////////
	std::cout << "-------" << std::endl;
	for (unsigned x = 0; x < 9; x++)
	{
		for (unsigned int y = 0; y < 9; y++)
		{
			std::cout << _grid[x][y] << " ";
		}
		std::cout << std::endl;
	}
	std::cout << std::endl << "------" << std::endl;
}
 
bool Grid::solve() { ///////////////////////////
	for (unsigned int x = 0; x < 9 ; x++)
	{
		for (unsigned int y = 0; y < 9; y++)
		{
			if (checkFinished())
			{
				Grid::print();
				return true;
			}
 
			if (_grid[y][x] == 10) {
				for (unsigned int i = 1; i < 10; i++)
				{
					if (checkPossible(i, x, y)) {
						_grid[y][x] = i;
						if (Grid::solve())
							return true;
						_grid[y][x] = 10;
					}
				}
				return false;
			}
		}
	}
	return false;
}

int main() ////////////////////////////////////////////////////////////////////
{
	Grid g;
	g.print();
	g.solve();
}

$ time ./foo
-------
5 3 10 10 7 10 10 10 10
6 10 10 1 9 5 10 10 10
10 9 8 10 10 10 10 6 10
8 10 10 10 6 10 10 10 3
4 10 10 8 10 3 10 10 1
7 10 10 10 2 10 10 10 6
10 6 10 10 10 10 2 8 10
10 10 10 4 1 9 10 10 10
10 10 10 10 8 10 10 7 9

------
-------
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

------

real    0m0.051s
user    0m0.000s
sys     0m0.030s

Topic archived. No new replies allowed.