Sudoku Complexities

[Colin Fiat]

My current passing interest is Sudoku (for a second time) and have failed at the
reasonably simple task of indexing all possible starting configurations for a 17 opening
clue puzzle. The main problem is that I to not have 1.76x10¹⁸ years.

Given that there are 81 positions in a board and each of the 17 starting clues can range
from 1 to 9, that's 0 to 80 cells with 0 to 8 values: 80x9+8=728 as a max value for the
last cell on the board.

Creating a 17 element array of ascending values from 0 (cell 0 value 0 zero aligned) to
728 (728/9=cell 80 and 728 mod 9 = value 8) seems like the best method of encoding
position and value.

728 uniquely ascending ordered values taken 17 at a time is C(728,17) = 1.055x10³⁴
combinations. Hmmm...?

To index each combination in a table requires iterating until one of the array elements
expires and recording the current index. A rough calculation suggests I need a 128bit
number for this. So the entire table will have the dimensions 729x17x16 = 198288
bytes. That's very reasonable. When the table is complete, any 17 clue puzzle can have
its lexicographical index calculated simply by adding values from the table according to
each clue's position and value as an offset within the table.

However, the best I can accomplish, without attempting to account for every instruction
cycle to the nth degree, is 193,000,000 iterations per second.

1.05539x10³⁴ combinations at 193,000,000 per second will take 5.4683x10²⁵ seconds.

5.4683x10²⁵ / 60 secs / 60 mins / 24 hours / 365 days = 1.734x10¹⁸ years.

I'm going to go sulk now and play a few games of nethack...

Code Select Expand

; *** Create a lexicograpical chart
; *** chart: counter:16 bytes odom:34 bytes lexichart:198288 bytes (729*17*16)
; *** procCntr=number of iterations before returning to caller for event handling
makechart proc STDCALL chart:DWORD,procCntr:DWORD

push edi ;
push esi ;
mov esi,chart ; address of 128bit counter
bts dword ptr [esi],31 ; temp flag to show index in chart
lea esi,[esi+16] ; address of odometer values

jmp jp00 ; jump to end of loop

lp00: mov edx,ebx ; pointer to curent digit
dec dx ; previous digit to left
mov eax,729 ; highest digit number+1
mul dx ; chart column start offset
add ax,[esi+ebx*2-2] ; value of next highest digit is row
shl eax,7 ; multiply by 128 for address offset
lea edi,[esi+eax+34] ; address of chart table entry
sub edx,edx ; zero
cmp edx,[edi] ; is there a chart value already?
jne jp01 ; do not overwrite previous values
lp03: mov eax,[esi+edx*4-16] ; get one part of the counter
mov [edi+edx*4],eax ; store in chart
inc dx ; next dword counter
cmp dx,4 ; have 4 dwords been moved?
jne lp03 ; loop till odom counter copied
jp01: mov eax,-1 ; return with expire flag
dec ecx ; max value for this element
dec ebx ; next element to the left
js finish ; exit if counter expired
inc word ptr [esi+ebx*2] ; increment the digit
cmp cx,[esi+ebx*2] ; compare value to its max+1
jc lp00 ; loop if element expired
mov ax,[esi+ebx*2] ; get the last incremented element
lp01: mov [esi+ebx*2],ax ; store the value in odometer
mov cx,9 ; divisor
sub edx,edx ; zero for remainder
div cx ; ax=0 to 80 positions dx=0 to 8 values
inc ax ; next position
mul cl ; convert back to pos|val with 0 as value
inc ebx ; next element to the right
cmp bx,17 ; is this outside the array
jne lp01 ; loop until end of array found
mov eax,4 ; least significant dword +1 of counter
mov edi,chart ; address of odometer index counter
clp00: dec ax ; decrement counter offset
inc dword ptr [edi+eax*4] ; increment the total iteration counter
je clp00 ; loop if least sig digit expired
jp00: mov ecx,729 ; highest number +1 (range)
mov ebx,17 ; number of digits in the odometer (quantity)
dec dword ptr procCntr ; decrement the progress counter
jne jp01 ; loop and increment the odometer if not done enough
sub eax,eax ; zero return code

finish: pop esi
pop edi
ret

makechart endp

[daydreamer]

first couldnt you start with a sudoku solver that is narrowed down to the reduced number of combinations that is made because of the starting numbers?
make use of SSE2, that can make use of two 64bit integers as High and low with little tricks in Xmm 128bit registers, can that help?

[qWord]

Wikipedia: Sudoku algorithms

[Colin Fiat]

Thanks for the suggestion daydreamer. The above lexicographical indexer does not need
a full grid solution; that's not the point of the exercise. And being an indexer, every
combination must be accounted for from the first illogical pattern of 17 1's in the top
two rows down to 17 9's at the bottom. Starting with the first and lowest valid 17 clue
puzzle could have an index of 1, in much the same way that aardvark would be indexed
as 1 in a lexicographical dictionary, but given a different word or a different 17 clue
puzzle, it is impossible to simply calculate the lexicographical index.

I've yet to find a really beneficial need for SSE2 and as such have nothing more than a
cursory understanding of it from a short wiki page. In this case there is zero benefit. The
largest number which needs to be managed is 728. The 128bit number need only be
incremented by one as seen at line CLP00: above.

The primary problem is that any computer would need to count 3.3466x10²⁵
combinations per seconds to get it done in 10 years. I've managed 193000000/s.
Fujitsu's K-Computer can process at 8.162x10¹⁵ (8 petaflops) but is still 10 orders of
magnitude short.



Thanks for the link qWord but this one would be of more benefit.