Sudoku
in [ASM]
|
From: Herbert Kleebauer on 4 Dec 2007 03:16 Terence wrote: > > My point was to emulate how a human solves SUDOKU puzzles with using > exhaustive searches. > May Herbert's isn't that kind. I think it's the same way a human would do it. I have two 16 bit variables (put into the lower and upper word of a 32 bit variable) for each position. If the number for a position is given or already found, then in the lower word the appropriate bit (1-9) is set. If the number is still not found for this position, then the upper word has a 1 bit in all positions (1-9) which could be the correct value (this means, each position which is not specified in the original puzzle is initializes with 0x03fe in the upper word and 0x0000 in the lower word). Then for each row, column and 3x3 square the "add" and "or" of the nine 32 bit variables is calculated. For the low word the "add" and the "or" must be the same or the same number occurs twice. If the "add" result of the lower word is "ored" to the "or" result of the upper word, then the result must be 0x03fe or the puzzle is not solvable. This is repeated until no more numbers can be excluded. If after this the puzzle is not solved, then a guess for a single position is made and then the above is repeated. I didn't find a puzzle till now, which couldn't be saved this way so never implemented recursive code which guesses 2,3 or more values.
From: Herbert Kleebauer on 4 Dec 2007 03:25 Terence wrote: > Then I tried dis-assembly of the created program: this can't be > correct surely? > . > code SEGMENT > ASSUME CS:code, DS:code > ORG 100h > start: INC DX > PUSH 40h > PUSH 7Ah > PUSH 3060h > POP AX > SUB AX,2F60h > PUSH AX > PUSH AX > PUSH AX > PUSH AX > PUSH AX > PUSH AX > POPA > SUB [SI+45h],AL > SUB [SI+4Dh],AL > SUB [SI+4Fh],AL > SUB [SI+68h],AL > SUB [SI+73h],CL > SUB [SI+75h],CL The is the decoder routine (the first two lines of the text) written with x86 instructions in the ascii range only. The ascii encoded program starts in line 3 of the text and is decoded by the decoder routine in the first two lines before it is executed. @=$100 inc.w r1 ; Fuellbyte moveq.w #$40,-(sp) moveq.w #$7a,-(sp) move.w #$3060,-(sp) move.w (sp)+,r0 sub.w #$3060-$100,r0 ; r0=$100 move.w r0,-(sp) move.w r0,-(sp) move.w r0,-(sp) move.w r0,-(sp) move.w r0,-(sp) move.w r0,-(sp) movem.w (sp)+,r0-r7 ; r0=$40, r2=$7a, r1=r3=r4=r5=r6=$100 sub.b r0,_b1+1-$100.b(r5.w) sub.b r0,_b2+1-$100.b(r5.w) sub.b r0,_b3+1-$100.b(r5.w) sub.b r0,_d1+3-$100.b(r5.w) sub.b r2,_c1+1-$100.b(r5.w) sub.b r2,_c2+1-$100.b(r5.w) sub.b r2,_c3+1-$100.b(r5.w) sub.b r2,_d1 -$100.b(r5.w) move.w (sp)+,r1 move.w r1,-(sp) ; r1=0 move.w r1,-(sp) move.w (sp)+,r4 inc.w r4 inc.w r4 inc.w r4 ; r4=3 _20: move.w r4,-(sp) move.w (sp)+,r2 ; r2=3 _30: move.w r1,-(sp) move.w (sp)+,r0 eor.b buf-$100.b(r5.w),r0 ; r0 = nextch cmp.w #$0a0d,r0 ; crlf eor.b r0,buf-$100.b(r5.w) ; clear buf inc.w r5 move.w r0,-(sp) sub.b #'0',r0 ; < '0' move.w (sp)+,r0 _b1: bmi.b _30+$40 ; ja, dann ignorieren beq.b buf ; =, dann fertig move.w r0,-(sp) sub.b #'=',r0 ; < '=' move.w (sp)+,r0 _b2: beq.b _10+$40 ; =, dann nicht veraendern _b3: bcc.b _11+$40 ; > '=', dann um 1 erhoehen eor.b #'o',r0 ; 1 wird zu ^ _11: inc.w r0 ; um 1 erhoehen and.b #$3f,r0 ; nur 6 Bit _10: move.w r0,-(sp) ; auf stack ablegen dec.w r2 ; schon 4 mal durchlaufen _c3: bpl.b _30+$7a ; nein, dann zurueck ; and.w r1,tmp-$100.b(r3.w) ; 20.5.02 ersetzt, da ! and.b r1,tmp+1-$100.b(r3.w) move.w (sp)+,r0 eor.b r0,tmp+1-$100.b(r3.w) move.w r4,-(sp) move.w (sp)+,r2 _50: and.b r1,tmp-$100.b(r3.w) _d1: dc.b $c1+$7a-$100,$6f,tmp-$100,$02+$40 ; lsr.w #2,tmp-$100.b(r3.w) move.w (sp)+,r0 eor.b tmp-$100.b(r3.w),r0 eor.b r0,buf-$100.b(r6.w) inc.w r6 dec.w r2 _c1: bne.b _50+$7a _c2: beq.b _20+$7a tmp: dc.b 13,10 buf:
From: Herbert Kleebauer on 4 Dec 2007 03:33 Rosario wrote: > but how to play in that game? what are the rules? ...7 ... 8.. ..5. .2. .9. 9.3 ... 7.1 .... 4.8 ... ..3. ... .6. .... 7.5 ... 4.9 ... 3.. ..2. .8. .7. ...1 ... 4.. Replace each . with a digit (1-9) so that in each row and column and each of the 9 3x3 squares any digit from 1 to 9 occurs. For the above the solution is: 267 941 853 158 327 694 943 856 721 715 468 239 834 219 567 692 735 148 489 572 316 326 184 975 571 693 482
From: Spam Killer on 5 Dec 2007 13:03 On Sun, 02 Dec 2007 04:35:48 +0100, Herbert Kleebauer wrote: >... I'm still looking for an >example which can't be solved with a very simple algorithm >with only 1 level of indirection. >... This gives: ...8...4.. 3.......2 ..7.2...5. ......1... 4..8.6..9 ....5..... ..8.3.9.7. 79..6...3 ...5...9.. not solveable with one recursion The solution would be: 528613497 341975682 679284351 962741835 457836219 813592746 286359174 794168523 135427968 but there is an additional requirement for solving it. The colors do matter. The numbers 1-9 must appear in every color only once, and this variation seems to be relatively new. I've only seen this one so far. -- wfz
From: Herbert Kleebauer on 5 Dec 2007 12:55
Spam Killer wrote: > > On Sun, 02 Dec 2007 04:35:48 +0100, Herbert Kleebauer wrote: > >... I'm still looking for an > >example which can't be solved with a very simple algorithm > >with only 1 level of indirection. > >... That's not a valid sudoku puzzle, there are at least two more solutions: ...8...4.. 528613497 528637491 528673491 3.......2 341975682 346915782 341985762 ..7.2...5. 679284351 179284356 679214358 ......1... 962741835 863791245 962741835 4..8.6..9 457836219 457826139 457836219 ....5..... 813592746 912543867 813592647 ..8.3.9.7. 286359174 281359674 286359174 79..6...3 794168523 794168523 794168523 ...5...9.. 135427968 635472918 135427986 > but there is an additional requirement for solving it. The colors do > matter. The numbers 1-9 must appear in every color only once, and > this variation seems to be relatively new. I've only seen this one so > far. Which colors? |