flat assembler
Message board for the users of flat assembler.

Index > Windows > Smallest sudoku solver

Goto page 1, 2  Next
Author
Thread Post new topic Reply to topic
Reverend



Joined: 24 Aug 2004
Posts: 408
Location: Poland
Reverend
Size of code: 575
Size of initialised data: 44
Size of uninitialised data: 1863
Sum: 2482

Size of file: 1,5 kB

This version was written for a competition and is the smallest version of sudoku solver. It gets sudoku in format:
Code:
x 2 x 1 5 x 4 x x
5 x x x x x x 2 x
x x 1 9 2 x x x 8
x 3 x x x 4 9 x x
6 x x 7 3 x x 1 x
4 x x 5 8 x x 7 x
x x 9 3 6 x x x 1
x 8 x 4 7 x 6 x x
1 x x x x x x 8 x    
And outputs:
Code:
9 2 8 1 5 6 4 3 7
5 7 6 8 4 3 1 2 9
3 4 1 9 2 7 5 6 8
8 3 7 6 1 4 9 5 2
6 9 5 7 3 2 8 1 4
4 1 2 5 8 9 3 7 6
7 5 9 3 6 8 2 4 1
2 8 3 4 7 1 6 9 5
1 6 4 2 9 5 7 8 3    
Usage:
Code:
solver filename    
Result is saved in output.bin
There are 4 example sudoku to solve in package


Description:
Download
Filename: Sudoku.zip
Filesize: 60.62 KB
Downloaded: 363 Time(s)

Post 23 Oct 2006, 12:39
View user's profile Send private message Visit poster's website Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7106
Location: Slovakia
vid
are there some rules on input / file format? do you have link to competition?

i am sure i can write much smaller one as dos .com file reading from standard input and writing to standard output.

anyway, i believe i can write just the code smaller than you Wink
Post 23 Oct 2006, 22:25
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7106
Location: Slovakia
vid
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


Description:
Download
Filename: ss.zip
Filesize: 1014 Bytes
Downloaded: 316 Time(s)

Post 23 Oct 2006, 23:14
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
Not to burst anyone's bubble (in fact, I think you're all freakin' geniuses for even solving such a complex problem!), but it's been done: Very Happy

Quote:

Hugi Size Coding Competition #25 - The "Sudoku" Compo

1st -- G3, Russia, 67 bytes, 30 Jan 2006
1st -- Digimind, Russia, 67 bytes, 31 Jan 2006


download .ASM source/rules/examples/tests

http://www.frontiernet.net/~fys/hugi/compoold.htm#compo25
Post 24 Oct 2006, 06:27
View user's profile Send private message Visit poster's website Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7106
Location: Slovakia
vid
yes, wonderful.
i HAVE told i haven't optimized it yet... Smile
Post 24 Oct 2006, 10:21
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
sylwek32



Joined: 27 Apr 2006
Posts: 339
sylwek32
These two examples do not work on my dual athlon pc..

Machine Specifications:

2 x Athlon MP 2000+
1024 Infineon DDR-RAM
Tyan Tiger MP Board
Post 24 Oct 2006, 11:20
View user's profile Send private message Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7106
Location: Slovakia
vid
what happens?
Post 24 Oct 2006, 11:38
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
Someone set up us the bomb!
Post 24 Oct 2006, 11:41
View user's profile Send private message Visit poster's website Reply with quote
Reverend



Joined: 24 Aug 2004
Posts: 408
Location: Poland
Reverend
The solver was supposed to be correct Win32 PE but without any changes made by linker (with fasm that's no problem). The input is as I showed in example ie. 0-9 - given number, x - unknown.
OK, maybe my version is not the smallest possible now... Rolling Eyes
Post 24 Oct 2006, 13:19
View user's profile Send private message Visit poster's website Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7106
Location: Slovakia
vid
by the way, they optimized it to 62 bytes after end of competition
Post 24 Oct 2006, 14:18
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
f0dder, huh? Laughing

vid, where's a link to that? info? download?

BTW, I believe IOCCC '05 has a Sudoku solver and generator (in case you need some more examples to test):

Quote:

# Most ingenious puzzle solution

Aidan Thornton - Sudoku solver and generator
United Kingdom
Post 24 Oct 2006, 15:17
View user's profile Send private message Visit poster's website Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7106
Location: Slovakia
vid
it was mentioned in archive linked by you
Post 24 Oct 2006, 15:32
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
vid, I found it (but I think you have to join the group before being able to access the file attachments, doh).

<EDIT> See the attachment below, it's the real deal! Very Happy </EDIT>


Last edited by rugxulo on 01 Nov 2006, 05:46; edited 2 times in total
Post 24 Oct 2006, 16:11
View user's profile Send private message Visit poster's website Reply with quote
rugxulo



Joined: 09 Aug 2005
Posts: 2341
Location: Usono (aka, USA)
rugxulo
Also, here's another thread for ATV's similar prog: Sudoku solver [DONE]
Post 24 Oct 2006, 17:04
View user's profile Send private message Visit poster's website Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
rugxulo: sorry, off-topic - but perhaps this URL will shed some light on the subject (vid's "what happens?" was what started it all Smile ).
Post 24 Oct 2006, 23:31
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2145
Location: Estonia
Madis731
Think about it Very Happy
81 squares and 62 bytes Wink
Impossible? NO!
Post 25 Oct 2006, 10:32
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
ATV



Joined: 31 Aug 2004
Posts: 109
Location: Finland
ATV
I have been searching my computer to find that 62 bytes entry and finally I have found it.
Original Hugi Compo #25 winner was 67 bytes, but when all ideas is put together after competition this 62 bytes was born.
usage:
entry <1.puz


Description: 62 bytes sudoku solver
Download
Filename: sudoku62.zip
Filesize: 2.64 KB
Downloaded: 305 Time(s)

Post 26 Oct 2006, 11:00
View user's profile Send private message Reply with quote
rugxulo



Joined: 09 Aug 2005
Posts: 2341
Location: Usono (aka, USA)
rugxulo
62-byte Sudoku solver (using Octasm) (six lines, good for a sig):

Code:
LANG OCTASM,0.1 org 100h use16 file_out \sudoku.com ah=3Fh dx=bp # int 21h
xchg ax,cx inc bx # [bp+si]=al # dec si js <3 ax=4031h # cmp b[bp+si],'.'
jne <2 di=cx # dec di pusha js <4 cmp [bp+di],al jne >2 xchg ax,di # aam 19
imul ax,11 xchg ax,si inc bx jpo <1 xor ax,si test ax,0E0C0h jle >2 # mul ah
# popa jo <4 b[bp+si]='.' cmp al,39h je <1 jmp <5-1 ; solver: `sudoku.com < 1.puz'
; G3=tgm80@@mail,ru  TFx=tfx@@bitmaster,it  Digimind=digimind@@aha,ru
    


UUencoded version of the 62-byte Sudoku solver (five lines):
Code:
begin 644 entry.com       /* 62-byte Sudoku solver : `entry < 1.puz' */
MM#^+U<TAD4.(`DYX][@Q0(`Z+G7UB_E/8'CM.`-U$9?4$VO`"Y9#>_<SQJG`
1X'X"]N1A<.+&`BX\.73VZ]$`
`
end /* G3=tgm80@@mail,ru  TFx=tfx@@bitmaster,it  Digimind=digimind@@aha,ru */
    


XXencoded version of the 62-byte Sudoku solver (five lines):
Code:
begin 644 entry.com       /* 62-byte Sudoku solver : `entry < 1.puz' */
hh1y9pQoVYIC6+YtsxvUlE6+u9bLpWzZDM5XhC+Bp2NTI2qj+0tN1SzQnleb+
Fs5s0xiFVQC94+WswCLHqux2+
+
end /* G3=tgm80@@mail,ru  TFx=tfx@@bitmaster,it  Digimind=digimind@@aha,ru */
    


62-byte .COM as raw hex data (four lines)
Quote:

B4 3F 8B D5 CD 21 91 43 88 02 4E 78 F7 B8 31 40 80 3A 2E 75 F5
8B F9 4F 60 78 ED 38 03 75 11 97 D4 13 6B C0 0B 96 43 7B F7 33
C6 A9 C0 E0 7E 02 F6 E4 61 70 E2 C6 02 2E 3C 39 74 F6 EB D1
tgm80@@mail,ru tfx@@bitmaster,it digimind@@aha,ru


Last edited by rugxulo on 02 Jul 2007, 00:12; edited 3 times in total
Post 18 Dec 2006, 00:27
View user's profile Send private message Visit poster's website Reply with quote
kohlrak



Joined: 21 Jul 2006
Posts: 1421
Location: Uncle Sam's Pad
kohlrak
Soduko solvers... I have another interesting contest that's related. A word search solver... but i, myself, won't attempt that one. lol
Post 18 Dec 2006, 02:17
View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger Reply with quote
ssp



Joined: 05 Mar 2007
Posts: 38
Location: India
ssp
rugxulo wrote:
62-byte Sudoku solver (using Octasm) (six lines, good for a sig):

Code:
LANG OCTASM,0.1 org 100h use16 file_out \sudoku.com ah=3Fh dx=bp # int 21h
xchg ax,cx inc bx # [bp+si]=al # dec si js <3 ax=4031h # cmp b[bp+si],'.'
jne <2 di=cx # dec di pusha js <4 cmp [bp+di],al jne >2 xchg ax,di # aam 19
imul ax,11 xchg ax,si inc bx jpo <1 xor ax,si test ax,0E0C0h jle >2 # mul ah
# popa jo <4 b[bp+si]='.' cmp al,39h je <1 jmp <5-1 ; solver: `sudoku.com < 1.puz'
; G3=tgm80@@mail,ru  TFx=tfx@@bitmaster,it  Digimind=digimind@@aha,ru
    



Yeah! That's very nasty!
This code does not belong here. You should have translated it into fasm first and then posted it here.
What's the purpose of it? Tell me you stupid, blockhead, dumb creature!

I can't understand it, or compile it with fasm/nasm/masm/gas/goasm and to top it all it's horrible to look at!

Go learn some ettiquettes before posting here.

_________________
From: Sandeep
Post 19 Jun 2007, 05:26
View user's profile Send private message Yahoo Messenger Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page 1, 2  Next

< 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-2019, Tomasz Grysztar.

Powered by rwasa.