The optimization games continue with TableSalt. Last time I managed to get down to a cool 222ms/puzzle, but of course I'm gonna keep trying for that 100ms! This time the optimizations came from the forward checking algorithm and some of the code used in determining which variable has the smallest domain.

Background

TableSalt uses forward checking during backtracking using a minium remaining value (MRV) heuristic - this means it runs through all unassigned variables and finds the one with the smallest domain.

Finding MRV for Cell 05:

4 1 ? | 3 ? ? | 8 ? 5        01 02 03 | 04 05 06 | 07 08 09  
? 3 ? | 1 ? ? | ? ? ?        10 11 12 | 13 14 15 | 16 17 18
? 5 ? | 7 ? ? | ? ? ?        19 20 21 | 22 23 24 | 25 26 27
------+-------+------        ---------+----------+---------
8 2 5 | 4 3 7 | 1 6 9        28 29 30 | 31 32 33 | 34 35 36  
? 9 ? | 5 8 ? | 4 ? ?        37 38 39 | 40 41 42 | 43 44 45
? 4 ? | 9 1 ? | ? ? ?        46 47 48 | 49 50 51 | 52 53 54
------+-------+------        ---------+----------+---------
2 8 9 | 6 4 3 | 5 7 1        55 56 57 | 58 59 60 | 61 62 63  
5 7 3 | 2 9 1 | 6 ? ?        64 65 66 | 67 68 69 | 70 71 72  
1 6 4 | 8 7 5 | ? ? ?        73 74 75 | 76 77 78 | 79 80 81  

Look at the value in Cell 05 (in the upper right). At this state, the only values it could be are 2 and 6 (this is the domain). The MRV for that cell is 2.

Degree Heuristic

If multiple values have the smallest domain, it resorts to a degree heuristic. The degree heuristic looks at how many other variables would be affected if the current value was assigned and tries to maximize this.

Degree Heuristic when two cells have the same domain size:

4 1 ? | 3 ? ? | 8 ? 5        01 02 03 | 04 05 06 | 07 08 09  
? 3 ? | 1 ? ? | ? ? ?        10 11 12 | 13 14 15 | 16 17 18
? 5 ? | 7 ? ? | ? ? ?        19 20 21 | 22 23 24 | 25 26 27
------+-------+------        ---------+----------+---------
8 2 5 | 4 3 7 | 1 6 9        28 29 30 | 31 32 33 | 34 35 36  
? 9 ? | 5 8 ? | 4 ? ?        37 38 39 | 40 41 42 | 43 44 45
? 4 ? | 9 1 ? | ? ? ?        46 47 48 | 49 50 51 | 52 53 54
------+-------+------        ---------+----------+---------
2 8 9 | 6 4 3 | 5 7 1        55 56 57 | 58 59 60 | 61 62 63  
5 7 3 | 2 9 1 | 6 ? ?        64 65 66 | 67 68 69 | 70 71 72  
1 6 4 | 8 7 5 | ? ? ?        73 74 75 | 76 77 78 | 79 80 81  

The function proceeds along and now is looking at Cell 08 - where the value can only be 2 or 6. This MRV here is also 2, which means TableSalt resorts to the degree heuristic. The degree heuristic deals with the number of unknowns associated with a cell. For sudoku, that is the number of cells that aren't known in the column, row, or section of the cell in question. For Cell 08, this is 18 (4 for the row + 7 for the column + 7 for the section, and yes it overlaps and includes itself) and for Cell 05 it is 13 (4 for the row + 3 for the column + 6 for the section). As such TableSalt will use Cell 08 moving forward as it affects more values.

The Problem...

I messed up - like really messed up on this one. I initially misread my AI notes and was using the number of constraints the cells were involved in for the degree heuristic.

This seems worthless for sudoku. They all have the same number of constraints...

That should've been the red flag. Whoops... The values were all 3 as each cell has AllDiff applied in the column, row, and section. Not good - I was counting up the wrong things... So I wrote a little for loop that actually got the number of affected cells and some more code that updated the values accordingly!! Major bug fixed (and a boat-load of time savings)!

Interestingly enough, I found this bug after questioning this one itty bit of code: what should be done if the degree heuristics are the same?

meh

That's right, I did nothing. Little did I know this was another mistake. I was writing the previous post on TableSalt and had linked the Look-ahead article form Wikipedia, where this one little sentence caught my eye:

Randomization is also sometimes used for choosing a variable or value. For example, if two variables are equally preferred according to some measure, the choice can be done randomly.

RANDOM YOU SAY!

and that was that! So I added a little check to see if degree values were the same and to choose randomly between them if they were:

if currentDegree > smallestDegree then  
    index_count = 1
    indices[index_count] = 
elseif currentDegree == smallestDegree then  
    index_count = index_count + 1
    indices[index_count] = i
end  

simple enough!

Results!

MAN OH MAN! So much time savings! Gotta fix them bugs and add some features!

Adding Random

This was the first thing that was addressed. A dramatic decrease in times! Also, now there is a bit of variation in how long it takes to solve the problem. Regardless, it took my 222ms down to 150-180ms/puzzle range! A cool 40-70ms faster! and a few ms closer to the elusive 100ms!

Fixing up my degree heuristic

This brought me down into the 90-100ms/puzzle range. An additional 50-90ms!!!! OH YES! THAT WONDROUS SUB 100MS TIME IS MINE! and I probably wouldn't even have gotten there if I hadn't started writing this blog - I likely would've wasted some time trying to get some functions written in C or something...

I ran my (self-asserting!) tests, and was good to go! As such the code is up on GitHub! Let me know if you have any other optimization tips! Otherwise I think I may be done working on TableSalt for a while!