Backtracking sudoku solver



This works by backtracking. I've ran it a few times and it just gets stuck.


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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233

#include <iostream>
#include <algorithm>

void print (int [][9]);

bool checkvalidity (int [][9]);
bool checkline (int [9]);


int main ()
{


	//int sudoku_arr [9][9];
	int sudoku_arr_copy [9][9];
	
	//initialise all values to 0
	//for (int a =0;a < 9; a++)
	//	for (int b=0; b < 9; b++)
		//	sudoku_arr [a][b] = 0;
	
	
	//entry of values
	
	int sudoku_arr [9][9] =				{{0,0,2, 1,4,0 ,8,6,0},
							 {4,0,8, 2,5,0 ,0,0,0},
							 {1,7,0, 3,0,0 ,0,0,4},
					   
							 {0,1,0, 0,0,0 ,0,7,6},
							 {6,0,5, 7,0,2 ,3,4,1},
							 {0,9,0, 0,0,0 ,0,2,8},
					   
							 {5,2,0, 9,0,0 ,0,0,7},
							 {8,0,6, 5,7,0 ,0,0,0},
							 {0,0,7, 8,2,0 ,6,3,0}};
					   
	//copy sudoku box to copy
	
	for (int a =0;a < 9; a++)
		for (int b=0; b < 9; b++)
			sudoku_arr_copy [a][b] = sudoku_arr[a][b];
	
	
					   
	
	
	
	//BRUTE FORCE
	
	for (int pos =0; pos < 81; pos++ )
	{
	

		if (sudoku_arr_copy [pos/9][pos%9] != 0)
			continue;
		
		
		bool deadend = false;
		
		while (!deadend)
		{
			if (sudoku_arr[pos/9][pos%9]  == 9)
			{
				deadend = true;
				break;
			}
		
			sudoku_arr[pos/9][pos%9]++;
			
			if (!checkvalidity (sudoku_arr))
				continue;
				
			if (checkvalidity (sudoku_arr))
				break;
				
		}
		
		if (deadend)
		{
			//set value to zero
			
			sudoku_arr [pos/9][pos%9] = 0;
			
			//find immediately previous FILLABLE entry
			
			for (int backpos = pos - 1; backpos >=0 ; backpos--)
			{
				if ( sudoku_arr_copy [backpos/9][backpos%9] ==0)
				{
					pos = backpos;
					break;
				}
				
				
			
			}
		
		}
			
		
		
		
		
	}
	
	print (sudoku_arr);
}




//CHECK VALIDITY

bool checkvalidity (int sudoku_arr[][9])
{
	int temp_arr [9];
	
	//rows
	
	for (int a=0;a <9;a++)
	{
		for (int b=0;b <9; b++)
			temp_arr[b] = sudoku_arr[a][b];
			
			if (!checkline (temp_arr))
				return false;
	
	}
	
	//columns
	
	for (int a=0;a< 9;a++)
	{
		for (int b=0;b<9;b++)
			temp_arr [b] = sudoku_arr [b][a];

		if (!checkline (temp_arr))
				return false;
	}
	
	//mini_boxes
	
	 
	int count =0;
	
	for (int d=0;d <9;d = d+3)
	{
	
		for (int a=0;a<9; a= a+3)
		{
			for (int c = d; c < (d+3);c++)
			
			{
				for (int b=a; b < (a +3);b++)
				{
					temp_arr [count] = sudoku_arr [c][b];
					count++;
				}
			
			}
			
			//box gathered
			count =0;
			
			if (! checkline (temp_arr))
				return false;
			
			
		}
	
	}
	
	
	//otherwise valid
	
	return true;
	


}
// 
bool checkline (int linearr_copy[9])
{
	std::sort (linearr_copy, linearr_copy + 9);
	
	for (int a=0; a<8;a++)
	{
		if (linearr_copy [a] == 0)
			continue;
			
		if (linearr_copy [a] == linearr_copy [a+1])
			return false;
		
	}
	
	return true;

}





//PRINT

void print (int sudoku_arr [][9])
{

	for (int a =0;a < 9; a++)
	{ 
		for (int b=0; b < 9; b++)
		{
			std::cout << sudoku_arr [a][b];
			
			if (b ==2 || b== 5)
				std::cout << " ";
		}
		
		if (a ==2 || a== 5)
				std::cout <<std::endl;
			
		std::cout << std::endl;

	}

}





Last edited on
It might not be that it's getting stuck... it might just be that it's taking forever to finish.

You have 42 empty spaces. That's ~942 permutations or ~10e39 permutations (that's a 1 with 39 zeros).

Even if you calculate 10 million permutations per millisecond (which you won't)... that means in a worst case scenario it will take 10e29 seconds or 3162315320758266140457 years to solve.

So yeah. Brute force isn't going to work.



EDIT:

My math isn't perfect here, you obviously will be short cutting a lot of permutations out by looking for early outs... but the point is it will take a long time.
Last edited on
Lol. I was reading wikipedia (http://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Brute-force_algorithm) and it said this was a 'practical method' of solving it.
I suppose I just wanted to know if it works in theory.
Well my math might be way off. =P

My numbers do assume a "dumb" brute force which will actually go through and plug all possible permutations into the puzzle (even those which will not solve it). Since you are only placing legal values I'm sure it'd be significantly faster... though I'd still imagine it'd be very slow.
I'm 99% sure it is genuinely getting stuck on the 2nd number as the value isn't changing. Can you see why?
Not immediately. But the easiest way to figure out where it's getting stuck is to step through with a debugger. Have you tried that yet?

I go over debugger basics here:

http://www.cplusplus.com/forum/beginner/75304/#msg403990
What you could do is modify your code so it can work with 2x2 of 2x2 squares of values in [1..4], instead of 3x3 of 3x3 squares of values in [1..9]. This should be easy enough to do if you replace your literals with constants

You will also need to tweak your output code to work with the modulus opertor rather than values.

That will make it easier to follow what's going on with the loop logic.

Andy
Last edited on
You could also give your code an almost completed puzzle (just one number left to find, two number, ...) and see it it can finish it off.

Or even a completed puzzle, to check the termination condition.

Andy
Last edited on
PS You should look at what happens after you set pos = backpos; on line 91

Either using a debugger, or by adding a bit of logging where the decisions are made.

Andy
Ah I hate debuggers!
rozick1 wrote:
Ah I hate debuggers debugging!


Fixed that for you.
Well, logging should be enough here.

But you need to get to know debuggers really well if you want to get into serious development!

Andy

PS

352 147 869
468 259 713
179 368 254

213 485 976
685 792 341
794 613 528

521 936 487
836 574 192
947 821 635

try count = 241
backtrack count = 3

cf

try count = 37652
backtrack count = 4157

for example here:

Sudoku
http://en.wikipedia.org/wiki/Sudoku

534 678 912
672 195 348
198 342 567

859 761 423
426 853 791
713 924 856

961 537 284
287 419 635
345 286 179



Last edited on
Topic archived. No new replies allowed.