### Sudoku CP

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!

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113`` `````` 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; } } } } } ``````
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```
Last edited on
Topic archived. No new replies allowed.