flat assembler
Message board for the users of flat assembler.
Index
> Main > Question about an incremental sudoku-solver |
Author |
|
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 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:
|
|||
03 Nov 2010, 08:51 |
|
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 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 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 08 Nov 2010, 23:55
http://board.flatassembler.net/topic.php?t=6076
vid from 2006 wrote:
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 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 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 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!
|
|||||||||||
15 Nov 2010, 07:16 |
|
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 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 |
|
< Last Thread | Next Thread > |
Forum Rules:
|
Copyright © 1999-2024, Tomasz Grysztar. Also on GitHub, YouTube.
Website powered by rwasa.