flat assembler
Message board for the users of flat assembler.

Index > Main > Question about an incremental sudoku-solver

Author
Thread Post new topic Reply to topic
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... Sad 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. Wink

PS: I just a theory, so please don't bother my Linux. (...and my bad english for the fact that I am german)
Post 02 Nov 2010, 21:28
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 20363
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
Post 02 Nov 2010, 22:08
View user's profile Send private message Visit poster's website Reply with quote
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! Smile


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.


Wink
Post 03 Nov 2010, 08:51
View user's profile Send private message Visit poster's website Reply with quote
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?
Post 03 Nov 2010, 13:56
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
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? Wink
Post 08 Nov 2010, 16:02
View user's profile Send private message Visit poster's website Reply with quote
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.
Post 08 Nov 2010, 19:39
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
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. Wink

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 Twisted Evil


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! Laughing
Post 08 Nov 2010, 23:55
View user's profile Send private message Visit poster's website Reply with quote
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.
Post 09 Nov 2010, 09:44
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
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 Wink
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)
Post 12 Nov 2010, 16:08
View user's profile Send private message Visit poster's website Reply with quote
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: 356 Time(s)

Post 15 Nov 2010, 07:16
View user's profile Send private message Reply with quote
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. Wink
Post 15 Nov 2010, 18:15
View user's profile Send private message Visit poster's website Reply with quote
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.
Post 16 Nov 2010, 18:43
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-2024, Tomasz Grysztar. Also on GitHub, YouTube.

Website powered by rwasa.