flat assembler
Message board for the users of flat assembler.

Index > Projects and Ideas > Sudoku solver [DONE]

Author
Thread Post new topic Reply to topic
ATV



Joined: 31 Aug 2004
Posts: 109
Location: Finland
ATV
World is full of Sudoku people, so here is Mini Sudoku.
I don't like solve by myself, so lets give computer do the hard job.

If you want see really small Sudoku solver check Hugi Size Coding Compo 25
http://www.hugi.scene.org/compo

ToDo:
- sudoku generator
- save best times into file

edit1: Madis, thanks for info, it's fixed now
edit2: Added enable/disable undo, drag/drop data file
edit3: Ask to save after changes, few bugs fixed
edit4: menu, undo/redo, show used time, arrow keys, bigger number font
edit5: is solvable test,copy2clipboard,filename in caption,initial digits read-only
edit6: load multi entry sudoku file,restart,output in 81/9x9/9x9grid format


Description: Mini Sudoku v0.06
Download
Filename: Sudoku006.zip
Filesize: 15.85 KB
Downloaded: 727 Time(s)



Last edited by ATV on 08 Sep 2006, 11:59; edited 6 times in total
Post 23 Mar 2006, 12:00
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2145
Location: Estonia
Madis731
That is my kind of program Smile

The only problem is that your stack is floating away and its crashing when returning from your code to user32.dll

You do NOT want to modify EBX in your dialog code - I've made this kind of mistakes a lot.

Replace:
Code:
line 38:
        push    ebx esi edi
        cmp     [msg],WM_INITDIALOG
;Then replace
line 220:
        pop     edi esi ebx
        ret
    


Its always a good idea to preserve registers - I think you have WinXP, that is why it works.

PS. http://www.hugi.scene.org/compo <= I see Estonia listed there, also Smile
Post 23 Mar 2006, 12:16
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Code:
77D1870C   55               PUSH EBP
77D1870D   8BEC             MOV EBP,ESP
77D1870F   56               PUSH ESI
77D18710   57               PUSH EDI
77D18711   53               PUSH EBX
.
.
.
77D18731   FF55 08          CALL DWORD PTR SS:[EBP+8] ;call to DialogProc
.
.
.
77D18753   5B               POP EBX
77D18754   5F               POP EDI
77D18755   5E               POP ESI
77D18756   5D               POP EBP
77D18757   C2 1400          RETN 14    

Well it's good for programmers who forgot to save registers but it's bad for programmers who are cautionous of it (and programmers that use high level languages) because it waste time and a little more stack memory.

ATV, you don't need to save ecx and edx, stdcall calling conventions says that those registers are volatile soo the caller knows that those registers are garbage on return. You need to save EBX, EDI, ESI and EBP.
Post 23 Mar 2006, 15:28
View user's profile Send private message Reply with quote
ATV



Joined: 31 Aug 2004
Posts: 109
Location: Finland
ATV
locodelassembly, This is my first win program (and few visual basic progs over 10 years ago)
I don't know anything about windows programming, DOS is my thing.
My old P166 has some startup problems (hd or motherboard problem), so I start to try win
programming with my HP laptop with WinXP/SP2 Home.
And Sudoku seems to be easy to start with.
Post 25 Mar 2006, 10:10
View user's profile Send private message Reply with quote
ATV



Joined: 31 Aug 2004
Posts: 109
Location: Finland
ATV
Above attachment updated

New features in v0.04
- menu
- undo/redo rewritten
- show used time
- use arrow keys
- bigger number font
Post 27 Apr 2006, 07:09
View user's profile Send private message Reply with quote
rugxulo



Joined: 09 Aug 2005
Posts: 2341
Location: Usono (aka, USA)
rugxulo
There's a Sudoku generator and solver in IOCCC's '05 compilation (in C). The full list of winners and their programs are here.
Post 27 Apr 2006, 18:43
View user's profile Send private message Visit poster's website Reply with quote
ATV



Joined: 31 Aug 2004
Posts: 109
Location: Finland
ATV
Above attachment updated

New features in v0.05
- try automatically detect empty char
- is solvable test
- copy current numbers to clipboard
- filename in caption
- initial digits is read-only thanks to Alex Torba
Post 31 Jul 2006, 09:06
View user's profile Send private message Reply with quote
ATV



Joined: 31 Aug 2004
Posts: 109
Location: Finland
ATV
Above attachment updated

New features in v0.06
- load multi entry sudoku file
- cell count/81
- restart
- output in 81/9x9/9x9grid format
Post 08 Sep 2006, 12:01
View user's profile Send private message Reply with quote
rugxulo



Joined: 09 Aug 2005
Posts: 2341
Location: Usono (aka, USA)
rugxulo
Here's another similar thread: Smallest sudoku solver
Post 24 Oct 2006, 17:12
View user's profile Send private message Visit poster's website Reply with quote
0.1



Joined: 24 Jul 2007
Posts: 474
Location: India
0.1
Hello ATV!
Cool stuff really!
Just a little favor from you plz.
Can you post the logic of your SuDoKu solver in plain English here?
plz. thx.

PS: Well not the whole program Shocked Only the solver function!
Post 08 Aug 2007, 13:45
View user's profile Send private message Reply with quote
ATV



Joined: 31 Aug 2004
Posts: 109
Location: Finland
ATV
0.1, plain English, huh, then Im wrong person to answer, my English is very bad.

It's just brute-force solver using recursive call (it keep previous values/empty position in stack).

Code:
Find empty position, if not found puzzle is solved
then set it '1' and check if other '1' found in same row or column or box
if same value not found, find next empty position and so on
else try '2' then '3' ...
if '9' can't be set, go back to previous empty position (note: it's not empty any more)
and set it +1 then check, and so on    

If you are new with recursive calls try find some Fibonacci, factorial, GCD, sort, dir-search and Towers_Of_Hanoi algorithms, they are often written with recursive calls
http://en.wikipedia.org/wiki/Recursion_%28computer_science%29
Post 09 Aug 2007, 07:15
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2145
Location: Estonia
Madis731
I think it was nicely explained Smile I didn't even know it before, how actually brute-force works on Sudoku. My mind can only handle 3x3 squares and 1x9, 9x1 lines Smile
Post 09 Aug 2007, 08:00
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
0.1



Joined: 24 Jul 2007
Posts: 474
Location: India
0.1
Thx a lot ATV!
I must confess I'm still pretty confused Shocked (DUMB!)
But your explanation is very valuable to me!

_________________
Code:
 o__=-
 )
(\
 /\  
    
Post 09 Aug 2007, 08:09
View user's profile Send private message Reply with quote
ATV



Joined: 31 Aug 2004
Posts: 109
Location: Finland
ATV
Madis731, brute-force works very well, because it will always find solution. More human like solvers usually gives "running out of algorithms" errors with really difficult sudoku. It's really difficult to write solver without brute-force. And those solvers are very big, no chance in Hugi Size Coding compo. Look from sudoku boards thinks like "X-Wing", "XY-Wing", "Forcing Chain", "Swordfish". Sometimes brute-force is little slow because it don't see easy numbers. Like last row "12345678x" that "x" will be filled in last with try "1" to "9", human just put "9" there without big thinking and looks second easy place.
Post 09 Aug 2007, 11:22
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 721
tthsqe
Your program is really great, but the solver is realy slow.....
I have got a solver (working on a generator) that is VERY fast....
would you mind putting it in your program?
Post 06 Jan 2010, 19:21
View user's profile Send private message Reply with quote
ManOfSteel



Joined: 02 Feb 2005
Posts: 1153
ManOfSteel
ATV's last post is the one right above yours. And it's 2 years and a half old.
Post 06 Jan 2010, 22:31
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 721
tthsqe
so this project has been abandoned?
Post 07 Jan 2010, 01:37
View user's profile Send private message Reply with quote
ManOfSteel



Joined: 02 Feb 2005
Posts: 1153
ManOfSteel
No idea. Probably. Ask ATV if you ever find a way to contact him.

But feel free to continue where he left.
Post 07 Jan 2010, 13:01
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.