flat assembler
Message board for the users of flat assembler.

 Index > Main > Question about an incremental sudoku-solver
Author
 Thread
andyz74

Joined: 26 Nov 2007
Posts: 36
Location: Germany
andyz74 02 Nov 2010, 21:28
I assume, the most of U know these sudoku-games, which are very modern these days. At the moment, I am trying to code a solver for sudoku (fasm/linux).
But all I get is a horrible slowly try... besides this, I asked me the following question:
Let's assume, we put all the numbers of the sudoku in a row, as we read them from left to right, like a normal text. The UNKNOWN shall be zero (0).

Quote:
sudo_ori db "165000000048031605290576001407063000600204007000710304800397016306180470000000538"

Ok, and now, back to the roots: We assume, EVERY number is a zero.

Quote:
sudo_ori db "0000000000000000000000000000000000000000....

Then we begin on the left side to increment.

100000000...
200000000...
3...
4
....
11000.....
21000.....
31...
41...
51...
61...
71...
81..
91...
12...
22...
32...
---------------------

81 numbers, as 9 * 9 is 81.

And after every incremention we test, if it is a working sudoku, or it doesn't work, until we get the FIRST working sudoku.

Would any computer, which stands in our working-rooms reach that in acceptable time?
Your opinion please ...'cuz I hate my f**king slow algorithm.

PS: I just a theory, so please don't bother my Linux. (...and my bad english for the fact that I am german)
02 Nov 2010, 21:28
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20135
Location: In your JS exploiting you and your system
revolution 02 Nov 2010, 22:08
Sudoku can be solved in sub-millisecond times on even a slow machine. By "slow" I mean in the modern sense so anything from 386 and up can do it that quickly. I once wrote a solver that was two stage layout. Stage 1 was to place obvious H, V and box values and was simply looped until no more spaces could be filled. Then stage 2 was trail and backtrack that called stage 1 after placing each trial. And since it could solve faster than I could blink I never went any further towards making it any faster.

Last edited by revolution on 03 Nov 2010, 13:59; edited 1 time in total
02 Nov 2010, 22:08
andyz74

Joined: 26 Nov 2007
Posts: 36
Location: Germany
andyz74 03 Nov 2010, 08:51
I somewhere saw a sudoku-solver in a 256-byte contest, and therefore got the opinion that this can't be done in a mathematic algorithm (by this small size) but by brute-force, and therefore tried it this way. But now I think your way (obvious infilling) is the one which speeds it enormely up. I'll see if i can insert it in my source. ThX for the idea!

btw: my real question was another:
Quote:

And after every incremention we test, if it is a working sudoku, or it doesn't work, until we get the FIRST working sudoku.

03 Nov 2010, 08:51
vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid 03 Nov 2010, 13:56
Way with smallest code is almost never the fastest one. You've got to decide what you are after - code size or speed?
03 Nov 2010, 13:56
rugxulo

Joined: 09 Aug 2005
Posts: 2341
Location: Usono (aka, USA)
rugxulo 08 Nov 2010, 16:02
vid, you never did open source your (multi-solution solver) ss.com tool. Should I just disassemble it for you/us?
08 Nov 2010, 16:02
vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid 08 Nov 2010, 19:39
Hmm, I think I did write something like that long ago, but sources are definitively lost and it wasn't nothing worth of wasting efforts on.
08 Nov 2010, 19:39
rugxulo

Joined: 09 Aug 2005
Posts: 2341
Location: Usono (aka, USA)
rugxulo 08 Nov 2010, 23:55
http://board.flatassembler.net/topic.php?t=6076

vid from 2006 wrote:

here is my quick try to beat you. It's 360 bytes of pure oldschool 16bit DOS code.

it shows ALL possible solutions (yours seem to get stuck in endless loop if there is more than 1 solution)

btw, code is still not after some heavy optimizations.

sources may be released after it is optimized. anyway, 360 bytes isn't that much to reverse

It was a long time ago, in a galaxy far far away, when vid still programmed for DOS (four years and two weeks) ... back when XP SP2 was king, and the plague of Vista hadn't ruined our crops, back when men were men, and coding challenges were the norm, when small size and fast speed still mattered, when the OS didn't need a DVD just to install, when 1 GB was considered luxurious, when the world was still just ....

Ahem, anyways, I did reverse that silly program, not perfectly obvious what's going on, and I still need to fix a few magic numbers, but it assembles to the same binary and works. When I finish cleaning it up, I'll post it in the (old) thread, with your permission of course.

EDIT: Posted in other thread, enjoy!
08 Nov 2010, 23:55
vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid 09 Nov 2010, 09:44
Permission given, do whatever you like with it. But reasons for putting efforts into this old crappy demo are still unclear to me. Reversing para512 would be way more fun... if the source wasn't already published, of course.
09 Nov 2010, 09:44
rugxulo

Joined: 09 Aug 2005
Posts: 2341
Location: Usono (aka, USA)
rugxulo 12 Nov 2010, 16:08
Why bother?

a). it works! (DOS too, heh, my fav)
b). it's small, written in FASM, by you, (the infamous) vid
c). it's unique since most others just assume all Sudokus only have one solution (which I think is supposed to be true, officially, but isn't always)
d). okay, guess I'm bored, heh, but also finally un-lazy enough to say, "360 bytes? Sure, I can disassemble that for him/us" (since nobody else did so far)
12 Nov 2010, 16:08
tthsqe

Joined: 20 May 2009
Posts: 767
tthsqe 15 Nov 2010, 07:16
Hey,
I saw sudoku solvers being discussed, and I just had to post a program written not for size but for speed. The solver is robust and as fast as I could get it, but the interface is a little primitive!

 Description: Download Filename: sudoku.zip Filesize: 176.35 KB Downloaded: 324 Time(s)

15 Nov 2010, 07:16
rugxulo

Joined: 09 Aug 2005
Posts: 2341
Location: Usono (aka, USA)
rugxulo 15 Nov 2010, 18:15
tthsqe, what's with the huge textfiles? Is that like a database (a la chess moves) to save time?? Oh, and just curious (since no srcs), was it written in FASM?

P.S. Interface? It's GUI, but I guess you could call that primitive.
15 Nov 2010, 18:15
tthsqe

Joined: 20 May 2009
Posts: 767
tthsqe 16 Nov 2010, 18:43
The text files are just collections of (hard) puzzles for rapid testing. All of the look-up tables used by the solver are computed at initialization and total less that ~2kb.
Of course it was written in fasm.
16 Nov 2010, 18:43
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum

Copyright © 1999-2024, Tomasz Grysztar. Also on GitHub, YouTube.

Website powered by rwasa.