Sudoku_Solver [help!]

[clive]

Most puzzles have unambiguous solutions, and a simple solver can either solve, or fill a significant number of boxes. Some of the more complex ones have ambiguous solutions, but even then an analysis of surrounding rows, columns, cells can significantly reduce the search space. Brute-forcing some fraction of the 9^81 combinations (i know it's less but I don't have the time to do the math in my head), doesn't seem a very appealing solution.

Try to devise an algorithm for solving, and implement it in a language/environment you can debug/test.

My simple x86 solver doesn't work quite as effectively as the more complex one I wrote in C. I posted a workable method earlier in the thread.

[dedndave]

aren't you just solving simultaneous equations ?

[clive]

Here is the simple variant, assembled.

[jenxin]

I think I got a method on doing this. I'll upload it later on tonight, and hope you can help me improve it. Thanks

[jenxin]

clive, your compiled program doesn't work for certain sudoku.

http://upload.wikimedia.org/wikipedia/en/1/17/Sudoku_puzzle_hard_for_brute_force.jpg

this is what I have so far..

Code Select Expand

Solve_Sudoku_Matrix PROC USES ebx ecx edx

mov ecx, OFFSET Sudoku_Matrix
mov bl,[ecx]

A0: .if bl==0
A1: inc bl

.if bl==10
mov eax,0
mov bl,0
mov [ecx],bl
ret
.endif

mov [ecx],bl

.else

jmp A2

.endif

A2: mov edx,OFFSET Sudoku_Matrix
call Test_Sudoku
.if eax==0
jmp A0
.else
push [ecx]
call Solve_Sudoku_Matrix
pop [ecx]
.if eax==0
jmp A1
.else
ret
.endif
.endif


Solve_Sudoku_Matrix ENDP

[clive]

clive, your compiled program doesn't work for certain sudoku.

I know. The C version is stronger, but again can get stopped if there are more than one unknown.

A complex solver doesn't brute force the solution, or do a simple "is this valid" check on the matrix. It goes through the matrix and eliminates all non-viable candidates for each location, and significantly reduces the search space. Chances are that a single additional location would drop a solution, you need to sort the locations with unknowns and start with those with the least. Iterate through that list and you will find the solution.

Implementing this first as an assembler solution is a coding/debugging nightmare. Thoroughly designing and testing the algorithm in something like C or Java is recommended. The homework question presupposes you have an algorithm to solve the problem.

[jenxin]

Yeah, this must be done with recursion. basically to bruteforce all possible combinations.

CAn you help me figure out whats wrong with my code?

Thanks.

[jenxin]

Our professor basically provided the solution+method to do this program.. My program assembles but doesnt do anything when s is pressed.

[clive]

I don't think you have the stack space to solve it via recursion. You understand the magnitude of the search space, right?

This is the last pass from my iterative solver. The next step is to identify the weakest locations and probe them.

Code Select Expand

*23 *23 **3|*** *** ***|*23 *23
4*6 456 *56|**6 *56 456|4*6 4*6  1
789 78* 789|789 789 *89|7*9 **9
           |           |
*2* *2* ***|    ***    |*2*
4*6 4*6 **6| 1  **6  3 |4*6  8   5
7*9 7** 7*9|    7*9    |7*9
           |           |
**3 **3    |***     ***|**3 **3 ***
4*6 456  1 |**6  2  456|4*6 4*6 4*6
789 78*    |789     *89|7*9 **9 7**
-----------+-----------+-----------
    *23 **3|    **3    |*23 *23 *2*
.1  **6 **6| 5  **6  7 |4*6 4*6 4*6
    *8* *8*|    *89    |*89 **9 *8*
           |           |
*23 *23    |*23 **3 *2*|    *23 *2*
**6 *56  4 |**6 **6 **6| 1  *56 **6
78* 78*    |*89 *89 *89|    **9 78*
           |           |
*23     **3|    **3    |*23 *23 *2*
**6  9  *56| 4  **6  1 |*56 *56 **6
78*     78*|    *8*    |78* *** 78*
-----------+-----------+-----------
        ***|*2* *** *2*|*2*
.5   1  **6|**6 **6 **6|4*6  7   3
        *89|*89 *89 *89|*8*
           |           |
**3 **3    |**3     ***|*** *** ***
4*6 4*6  2 |**6  1  *56|456 456 4*6
789 78*    |789     *89|*8* *** *8*
           |           |
**3 **3 **3|*23     *2*|*2*
**6 **6 **6|**6  4  *56|*56  1   9
78* 78* 78*|78*     *8*|*8*


Pass(es) 6

[jenxin]

My professor got it working, somehow. I've seen a demonstration of his program, and it works.

Unfortunately on the program specifications.. I must complete this using recursion. :[

And yeah, it's going to be pushing a lot of pointers.

Oh, and where it says push [ecx] and pop [ecx], i should have that changed to only, push ecx, and pop ecx, right?

[clive]

Iteration to catch low hanging fruit, follow by recursive brute force on the lowest weight combinations.

Code Select Expand

Unsolved
  7   7   6   4   5   5   6   5   1 (weights)
  5   4   3   1   3   1   5   1   1
  6   6   1   4   1   5   5   4   3
  1   4   3   1   4   1   6   5   4
  5   6   1   5   4   4   1   5   4
  5   1   5   1   3   1   6   4   4
  1   1   3   4   3   4   4   1   1
  6   5   1   5   1   4   4   3   3
  4   4   4   5   1   4   4   1   1
Failed to solve
Failed to solve
Failed to solve
           |           |
9   8   7 | 6   5   4 | 3   2   1
           |           |
           |           |
           |           |
2   4   6 | 1   7   3 | 9   8   5
           |           |
           |           |
           |           |
3   5   1 | 9   2   8 | 7   4   6
           |           |
-----------+-----------+-----------
           |           |
1   2   8 | 5   3   7 | 6   9   4
           |           |
           |           |
           |           |
6   3   4 | 8   9   2 | 1   5   7
           |           |
           |           |
           |           |
7   9   5 | 4   6   1 | 8   3   2
           |           |
-----------+-----------+-----------
           |           |
5   1   9 | 2   8   6 | 4   7   3
           |           |
           |           |
           |           |
4   7   2 | 3   1   9 | 5   6   8
           |           |
           |           |
           |           |
8   6   3 | 7   4   5 | 2   1   9
           |           |


Solved

Edit: Fixed incorrect result

[jenxin]

So it's not possible to do it solely on recursion?

[clive]

Oh, and where it says push [ecx] and pop [ecx], i should have that changed to only, push ecx, and pop ecx, right?

Actually I think [ecx] is appropriate, but you want to do the push [ecx] before you modify the location.

But, honestly I don't think your algorithm will work.

[jenxin]

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?

[clive]

So it's not possible to do it solely on recursion?

Recursion has it's place, if you can control the depth to a reasonable level, descending 10's of thousands, or 10's of millions is not appropriate. Searching a space approaching 9^81 is not a good one.

My recursion picks candidates that might work to the exclusion of ones which will never work.

Code Select Expand

solverecursive(x)
{
 while(solveiteratively(x));

 if (!solved(x))
 {
   while(pincandidates(x))
     solverecursive(x);
 }
}