Sudoku_Solver [help!]

[clive]

This was what the professor came up with.. I thought so too, but he got it working somehow, lets say there was enough stack memory. Wouldn't it work?

I guess if you can pull it off in a reasonably efficient manner you could keep the descent depth to say around 70, assuming you start with 11 initial values. But the time to process would be quite significant.

[clive]

ZIP and post your entire source (ie don't cut-n-paste into code quotes)

I can't make sense of your code, what you need is something like this :

Code Select Expand

Solve_Sudoku_Matrix PROC USES ebx ecx edx

        mov ecx, OFFSET Sudoku_Matrix
        mov edx, OFFSET Sudoku_Matrix + 81 ; end of matrix

; Find First Non-Zero Location

XX1:
        mov     bl,[ecx]
        or      bl,bl
        jz      XX2     ; Zero

        inc     ecx
        cmp     ecx,edx ; Limit, array full and valid
        jnz     XX1

        mov     eax,1 ; Solved
        ret

XX2:
        mov     bl, 1 ; Test 1 .. 9 at this empty location

XX3:
        mov     [ecx],bl

        pushad ; push all because not sure if it preserves registers
        mov     edx,OFFSET Sudoku_Matrix
        call    Test_Sudoku
        cmp     eax,1 ; Legal
        popad  ; restore, flags not touched

        jnz     XX4 ; not legal, please sir try another

        call    Solve_Sudoku_Matrix ; solve next one down

        cmp     eax,1 ; Reached maximal, thus solved
        jz      XX5     ; leave

XX4:
        inc     bl      ; try next value at this location
        cmp     bl,10
        jnz     XX3

        mov     byte ptr [ecx], 0 ; return to empty, all is lost

        mov     eax,0 ; Failed

XX5:
        ret

Solve_Sudoku_Matrix ENDP

Although the performance will suck pretty bad.

[jenxin]

Here's my revision.. The code performs pretty fast actually. My only problem is that it's only solving the 1st square. I wrote in some comments on where I'm having trouble.

Code Select Expand

Solve_Sudoku_Matrix PROC USES ebx ecx edx

mov ecx, OFFSET Sudoku_Matrix
A0: mov bl,BYTE PTR [ecx]
.if (bl!=0)
inc ecx
mov esi,ecx
mov edi, OFFSET Sudoku_Matrix
sub esi,edi
.if esi>80     ;this is supposed to be .if esi<80
jmp A0
.elseif esi<80 ;this is supposed to be .elseif esi>80 but when i make these two changes, the program crashes on me.
mov eax,1
ret
.endif
.elseif (bl==0)
A1: inc BYTE PTR [ecx]
.if (BYTE PTR [ecx]==10)
mov eax, 0
mov BYTE PTR [ecx],0
ret
.else
mov edx, OFFSET Sudoku_Matrix
call Test_Sudoku
.if eax==0
jmp A1
.elseif eax!=0
push ecx
call Solve_Sudoku_Matrix
pop ecx
.if eax==0
jmp A1
.elseif eax!=0
ret
.endif
.endif
.endif
.endif


Solve_Sudoku_Matrix ENDP

[clive]

Please post the entire code as an attachment.

The partial Test_Sudoku I have does not fully test the array, and also stomps on registers.

[jenxin]

Here it is. It's all the way at the bottom.

[jenxin]

Code Select Expand

.if esi>80     ;this is supposed to be .if esi<80
jmp A0
.elseif esi<80 ;this is supposed to be .elseif esi>80 but when i make these two changes, the program crashes on me.
mov eax,1
ret
.endif

forget about my previous comments. It is supposed to be .if esi > 80.

ERM Nevermind

Friend said it's supposed to be < 80. I'm clueless.

[jenxin]

I figured it out.

Here's the final version

Code Select Expand

Solve_Sudoku_Matrix PROC USES ebx ecx edx

mov ecx, OFFSET Sudoku_Matrix
A0: mov bl,BYTE PTR [ecx]
.if (bl!=0)
inc ecx
mov esi,ecx
mov edi, OFFSET Sudoku_Matrix
sub esi,edi
.if (esi>80)
mov eax,1
ret
.else
jmp A0
.endif
.elseif (bl==0)
A1: inc BYTE PTR [ecx]
.if (BYTE PTR [ecx]==10)
mov eax, 0
mov BYTE PTR [ecx],0
ret
.else
mov edx, OFFSET Sudoku_Matrix
call Test_Sudoku
.if eax==0
jmp A1
.elseif eax!=0
push ecx
call Solve_Sudoku_Matrix
pop ecx
.if eax==0
jmp A1
.elseif eax!=0
ret
.endif
.endif
.endif
.endif


Solve_Sudoku_Matrix ENDP

It was because of my, .elseif eax part. I got rid of it, and it works.

[jenxin]

I'm trying it out on the sudoku puzzle I posted earlier, and it's very slow..

[jenxin]

Sorry, here's the full thing.

It solves some very hard sudokus. Worst case scenario sudoku's like the one earlier.. It's still hogging my CPU. Might take some time.

Okay It solved it, in about 6 minutes.

erm actually *2:49.1*

using a virtual machine.

Thanks a bunch Clive, you've been a big help.

[jj2007]

Hi jenxin,

Congrats, that looks like a nice project :U

If the solving time is too high for your taste: there is still room for optimising. Some of your high level constructs could be replaced by faster code.
For example:

Code Select Expand

call Test_Sudoku
better=1
if better
test eax, eax ; .if eax==0
je A1
push ecx
call Solve_Sudoku_Matrix
pop ecx
test eax, eax ; .if eax==0
je A1
ret
else
.if eax==0
jmp A1
.elseif eax!=0
push ecx
call Solve_Sudoku_Matrix
pop ecx
.if eax==0
jmp A1
.elseif eax!=0
ret
.endif
.endif
endif

better is a switch for conditional assembly - a convenient way to compare two alternatives.

I couldn't test it because I don't have the Irvine libs, and it's also not in an innermost loop, so it won't speed up much. Test_Sudoku is another candidate for optimising, of course.

[clive]

If you want to be clever, reverse the search....

Code Select Expand

Solve_Sudoku_Matrix PROC USES ebx ecx edx

        mov ecx, OFFSET Sudoku_Matrix
        mov edx, OFFSET Sudoku_Matrix + 81 ; end of matrix

; Find First Non-Zero Location

XX1:
        mov     bl,[ecx]
        or      bl,bl
        jz      XX2     ; Zero

        inc     ecx
        cmp     ecx,edx ; Limit, array full and valid
        jnz     XX1

        mov     eax,1 ; Solved
        ret

XX2:
        mov     bl, 9 ; Test 9 .. 1 at this empty location

XX3:
        mov     [ecx],bl

        mov     edx,OFFSET Sudoku_Matrix
        call    Test_Sudoku
        cmp     eax,1 ; Legal
        jnz     XX4 ; not legal, please sir try another

        call    Solve_Sudoku_Matrix ; solve next one down

        cmp     eax,1 ; Reached maximal, thus solved
        jz      XX5     ; leave

XX4:
        dec     bl      ; try next value at this location
        jnz     XX3

        mov     byte ptr [ecx], 0 ; return to empty, all is lost

        mov     eax,0 ; Failed

XX5:
        ret

Solve_Sudoku_Matrix ENDP

It works really well with the hard test case you have been using <G>

[clive]

JJ Irvine is here, the EXE is a self-extracting ZIP
http://kipirvine.com/asm/articles/updating_irvine_library.htm
http://kipirvine.com/asm/examples/IrvineExamplesVS2010.exe

Code Select Expand

; Check Row @ edx

CheckRow PROC
        push    ebx
        push    ecx
        push    edx
        mov     ebx,9
        xor     eax,eax
CheckRowLoop:
        movzx   ecx,byte ptr [edx]
        bts     eax,ecx
        jc      CheckFail
        add     edx,1 ;
        and     eax,03FEh ; clear bit 0, could have multiple undefined
        dec     ebx
        jnz     CheckRowLoop
        ; carry implicitly clear
        ;  eax = 3FE if row solved
CheckFail:
        pop     edx
        pop     ecx
        pop     ebx
        ret
CheckRow ENDP

; Check Column @ edx

CheckCol PROC
        push    ebx
        push    ecx
        push    edx
        mov     ebx,9
        xor     eax,eax
CheckColLoop:
        movzx   ecx,byte ptr [edx]
        bts     eax,ecx
        jc      CheckFail
        add     edx,9 ; step row
        and     eax,03FEh ; clear bit 0
        dec     ebx
        jnz     CheckColLoop
        ; carry implicitly clear
        ;  eax = 3FE if row solved
CheckFail:
        pop     edx
        pop     ecx
        pop     ebx
        ret
CheckCol ENDP

; Check 3x3 cell @ edx
CheckCell  PROC
        push    ecx
        xor     eax,eax

        movzx   ecx,byte ptr [edx]
        bts     eax,ecx
        jc      CheckFail
        and     eax,03FEh ; clear bit 0
        movzx   ecx,byte ptr [edx+1]
        bts     eax,ecx
        jc      CheckFail
        and     eax,03FEh ; clear bit 0
        movzx   ecx,byte ptr [edx+2]
        bts     eax,ecx
        jc      CheckFail
        and     eax,03FEh ; clear bit 0

        movzx   ecx,byte ptr [edx+9]
        bts     eax,ecx
        jc      CheckFail
        and     eax,03FEh ; clear bit 0
        movzx   ecx,byte ptr [edx+10]
        bts     eax,ecx
        jc      CheckFail
        and     eax,03FEh ; clear bit 0
        movzx   ecx,byte ptr [edx+11]
        bts     eax,ecx
        jc      CheckFail
        and     eax,03FEh ; clear bit 0

        movzx   ecx,byte ptr [edx+18]
        bts     eax,ecx
        jc      CheckFail
        and     eax,03FEh ; clear bit 0
        movzx   ecx,byte ptr [edx+19]
        bts     eax,ecx
        jc      CheckFail
        and     eax,03FEh ; clear bit 0
        movzx   ecx,byte ptr [edx+20]
        bts     eax,ecx
        jc      CheckFail
        and     eax,03FEh ; clear bit 0
CheckFail:
        pop     ecx
        ret
CheckCell  ENDP

Test_Sudoku PROC

    ; Solution to Program 2
    ;
    ; EDX passes the address to the Sudoku matrix.
    ; EAX returns 1 if the matrix is legal, or 0 if the matrix is not legal.

    ; edx+0
        call    CheckRow ; Check Row 0
        jc      Illegal_Matrix_Detected
        add     edx,9
    ; edx+9
        call    CheckRow ; Check Row 1
        jc      Illegal_Matrix_Detected
        add     edx,9
    ; edx+18
        call    CheckRow ; Check Row 2
        jc      Illegal_Matrix_Detected
        add     edx,9
    ; edx+27
        call    CheckRow ; Check Row 3
        jc      Illegal_Matrix_Detected
        add     edx,9
    ; edx+36
        call    CheckRow ; Check Row 4
        jc      Illegal_Matrix_Detected
        add     edx,9
    ; edx+45
        call    CheckRow ; Check Row 5
        jc      Illegal_Matrix_Detected
        add     edx,9
    ; edx+54
        call    CheckRow ; Check Row 6
        jc      Illegal_Matrix_Detected
        add     edx,9
    ; edx+63
        call    CheckRow ; Check Row 7
        jc      Illegal_Matrix_Detected
        add     edx,9
    ; edx+72
        call    CheckRow ; Check Row 8
        jc      Illegal_Matrix_Detected

        sub     edx,8*9 ; 72 backtrack to [0,0]

    ; edx+0
        call    CheckCol ; Check Col 0
        jc      Illegal_Matrix_Detected
        add     edx,1
    ; edx+1
        call    CheckCol ; Check Col 1
        jc      Illegal_Matrix_Detected
        add     edx,1
    ; edx+2
        call    CheckCol ; Check Col 2
        jc      Illegal_Matrix_Detected
        add     edx,1
    ; edx+3
        call    CheckCol ; Check Col 3
        jc      Illegal_Matrix_Detected
        add     edx,1
    ; edx+4
        call    CheckCol ; Check Col 4
        jc      Illegal_Matrix_Detected
        add     edx,1
    ; edx+5
        call    CheckCol ; Check Col 5
        jc      Illegal_Matrix_Detected
        add     edx,1
    ; edx+6
        call    CheckCol ; Check Col 6
        jc      Illegal_Matrix_Detected
        add     edx,1
    ; edx+7
        call    CheckCol ; Check Col 7
        jc      Illegal_Matrix_Detected
        add     edx,1
    ; edx+8
        call    CheckCol ; Check Col 8
        jc      Illegal_Matrix_Detected

        sub     edx,8 ; backtrack to [0,0]

    ; edx+0
        call    CheckCell ; Check Cell 0
        jc      Illegal_Matrix_Detected
        add     edx,3
    ; edx+3
        call    CheckCell ; Check Cell 1
        jc      Illegal_Matrix_Detected
        add     edx,3
    ; edx+6
        call    CheckCell ; Check Cell 2
        jc      Illegal_Matrix_Detected
        add     edx,21 ; (27-6)
    ; edx+27
        call    CheckCell ; Check Cell 3
        jc      Illegal_Matrix_Detected
        add     edx,3
    ; edx+30
        call    CheckCell ; Check Cell 4
        jc      Illegal_Matrix_Detected
        add     edx,3
    ; edx+33
        call    CheckCell ; Check Cell 5
        jc      Illegal_Matrix_Detected
        add     edx,21
    ; edx+54
        call    CheckCell ; Check Cell 6
        jc      Illegal_Matrix_Detected
        add     edx,3
    ; edx+57
        call    CheckCell ; Check Cell 7
        jc      Illegal_Matrix_Detected
        add     edx,3
    ; edx+60
        call    CheckCell ; Check Cell 8
        jc      Illegal_Matrix_Detected

        sub     edx,60 ; backtrack to [0,0]

; Valid

        mov     eax,1
        ret

Illegal_Matrix_Detected:
        mov     eax,0
        ret
Test_Sudoku ENDP


[jj2007]

JJ Irvine is here, the EXE is a self-extracting ZIP

Thanks, Clive - I always thought you had to buy it...

[jenxin]

Oh wow. I only if I hadn't slept early yesterday(8:45PM) :(

Yes I agree his code could have been simplified, but this was for a intro class. I'll play with your code a bit Clive. Thanks!

[jenxin]

Clive:
I've never even heard about bts.. haha, and we weren't introduced the movzx.. is jc, jump carry?

and reversing the search is sorta clever, but then again, what if the sudoku starts off with 1...9 haha. I guess we have to compromise.

Hey Clive, What a you using to write your code? I'm using notepad. >_> are you using a ide?

JJ:
and thanks a bunch jj, you've just introduced to me a bunch of new commands.


this actually solves some of the hardest sudoku's in fractions of a second. im surprised.