Sudoku CP

[rozick1]

I originally wrote a simple backtracking algorithm but it proved too slow in some cases. I therefore read about constraint propagation. I think the idea is that when inserting a possible value then check (using the constraints such as there only being one candidate in a cell) that this doesn't result in a contradiction. If it does then backtrack. This should be quicker by 'pruning the search tree earlier'.

I've tried this as below but it seems to be much slower than simple backtracking. Can anyone see if my logic is right?

Thanks!

 bool constraint_prop (Cell temp[9][9])
{
	generateCandidates(temp);                   
	hidden_single (temp);                           //CONSTRAINT
	
	
	//is there a contradiction?
	
	for (int row=0;row <9;row++)
	{
		for (int col =0; col <9;col++)
		{
			if (!temp[row][col].getValue() == UNASSIGNED)
				continue;
				
			if (temp[row][col].getCandidates().size() == 0)             //CONTRADICTION AS UNASSIGNED CELL SHOULD ALWAYS HAVE AT LEAST ONE CANDIDATE
				return true;
			
		}
	}

	//else no contradiction
	
	return false;                                                       //NO APPARENT CONTRADICTION

}

bool backtrack (Cell cell_arr [9][9])
{
	Cell temp[9][9];
	
	
	
	for (int pos =0; pos < 81; pos++ )
	{
	
	
		int row_val = pos/9;
		int col_val = pos%9;
		

		
		if (cell_arr[row_val][col_val].isClue())                             //SKIP IF FIXED VALUE
			continue;
		

			
		bool deadend = false;
		int stat_val = cell_arr[row_val][col_val].getValue() ;             //VALUE OF CELL
		
		while (!deadend)                               
		{
			stat_val++;

			if (stat_val  == 10)                                          //DEADEND
			{
				
				deadend = true;
				break;
			}
			if (isValidPlacement (cell_arr,row_val,col_val,stat_val))     //NO IMMEDIATE PROBLEMS
			{
				//constraint prop
				
				
				for (int a=0;a<9;a++)
				{
					for (int b=0;b<9;b++)
					{
						temp[a][b].setValue( cell_arr[a][b].getValue());  //MAKE COPY OF SUDOKU
						
					}
				}
				temp[row_val][col_val].setValue (stat_val);               //SET POSSIBLE VALUE OF TEMP
				
				if (!constraint_prop(temp))                               //RETURNS TRUE IF CONTRADICTION ELSE FALSE
				{	
					cell_arr[row_val][col_val].setValue (stat_val);       //AS NO CONTRADICTION THEN USE VALUE
					break;
				}
				
																		  //ELSE INCREASE STAT-VAL AND TRY AGAIN
			}

				
		}
		
		
		
		if (deadend) //backtrack
		{
			cell_arr [row_val][col_val].setValue(UNASSIGNED);
			count++;
			
			for (int backpos = pos - 1; backpos >=0 ; backpos--)
			{
 				if (!cell_arr[backpos/9][backpos%9].isClue())
				{
					pos = backpos - 1;
					
					break;
				}
				
			
			}
		
		}
		
	}
		
	
}

[Mats]

I wonder if this is a good way to write a fast sudoku solver? I made one that worked very quickly which used first of all human style technique for trying to solve the puzzle (before trying brute force).

I set up 9 bit grids for each of the nine numbers and searched for places in which only one possible number could go. Here's a quick drawing to explain:

Puzzle: 
200 000 060
000 075 030
048 090 100

000 300 000
300 010 009
000 008 000

001 020 570
080 730 000
090 000 004

And here is what the 1s bit grid (bool bg1[9][9]) would look like (0 = empty cell, 1 = a 1 can't go here):

101 010 111
001 011 111
111 111 111

001 111 100
111 111 111
001 111 100

111 111 111
111 110 100
111 010 101

Then you check for any 9 horizontal, vertical or 3x3 box with only one gap on each of the 9 bit grids. If you find a horizontal, vertical or 3x3 with just one gap, then that number must go in there. This method is very very fast for solving human solvable grids.

Also, when it comes to brute force, you can use the bit grid to substantially reduce candidate numbers for a cell. For example in cell no.2 on the top row, you would only need to try 3,5,7,9 as the others would be marked as unable to be occupied by the other numbers on the bit grids.

In fact, on the 8s bit grid, you can see an example of this:

111 001 010
111 011 010
111 011 100

011 111 000 
111 111 001
111 111 111

111 011 110
111 111 111
111 001 001

An eight must belong in the 1st column, 4th row down. Updated 8s bit grid:

111 001 010
111 011 010
111 011 100

111 111 111 
111 111 001
111 111 111

111 011 110
111 111 111
111 001 001