Backtracking sudoku solver

[rozick1]

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

#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;

	}

}

[Disch]

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 ~9⁴² 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.

[rozick1]

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.

[rozick1]

I suppose I just wanted to know if it works in theory.

[Disch]

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.

[rozick1]

I'm 99% sure it is genuinely getting stuck on the 2nd number as the value isn't changing. Can you see why?

[Disch]

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

[andywestken]

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

[andywestken]

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

[andywestken]

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

[rozick1]

Ah I hate debuggers!

[Disch]

rozick1 wrote:

Ah I hate debuggers debugging!

Fixed that for you.

[andywestken]

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