Sudoku
Spam Killer
I learned a lot about the Windows API while writing this, so I thought
I'd share it with you guys. No solver, 'cause you should use your
brains to solve 'em, not your CPU. It is just meant to do it on the
screen, instead of the paper.
Enjoy! Or if you don't, you don't have to tell me, there is enough
bitching going on around here!
In the Menu Editor:
&File
[TAB]&Open
[TAB]&Save
[Empty Line]
[TAB]E&xit
&Edit
[TAB]&Check
[TAB]C&lear
[WINDOW_WIDTH 225 WINDOW_HEIGHT 225]
[M00_Menu 1000 M00_Open 1001 M00_Save 1002
M00_Exit 1003 M00_Check 1004 M00_Clear 1005]
[AppName: b$ "Sudoku.", 0]
[ClassName: b$ "SKELETON", 0]
[StrFilter: b$ 'All files', 0, '*.*', 0, 0]
[<32 LoadName: b$ "csod00.txt" b$ 0 #&MAXPATH - 6]
[<32 SaveName: b$ "csol00.txt" b$ 0 #&MAXPATH - 12]
[Correct: b$ "Correct!", 0 Incorrect: b$ "Incorrect!", 0]
[<32 Multiple_of_3: d$ 0010010000]
[hOutFile: d$ ? hInFile: d$ ? read: d$ ?]
[hWnd: d$ ? hMenu: d$ ?
hBlackPen: d$ ? hFont: d$ ?]
[<32 chartab: b$ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 b$ 0 #192]
[<32 colors: d$ 04080ff 0ffff00 0ff00 0808080
0ff0080 0ff 0ff00ff 0c0c0c0 0ffff]
[rows: d$ 9 columns: d$ 9]
[current_row: d$ 0 current_column: d$ 0]
[<32 column_buffer: b$ ' ' #(9*9)]
[<32 row_buffer: b$ 0 #(9*9)]
[<32 color_buffer: d$ 0 #(9*9)]
[<32 rcZells: d$ 0 0 0 0 #256]
[<32 wcx: ; WNDCLASSEX
@cbSize: d$ len
@style: d$ &CS_HREDRAW+&CS_VREDRAW
@lpfnWndProc: d$ MainWindowProc @cbClsExtra: d$ 0
@cbWndExtra: d$ 0 @hInstance: d$ 0
@hIcon: d$ 0 @hCursor: d$ 0
@hbrBackground: d$ &COLOR_WINDOW+1 @lpszMenuName: d$ 0
@lpszClassName: d$ ClassName @hIconSm: d$ 0]
[psx: ; PAINTSTRUCT
@hdc: D$ 0 @fErase: D$ 0
@rcPaint.left: D$ 0 @rcPaint.top: D$ 0
@rcPaint.right: D$ 0 @rcPaint.bottom: D$ 0
@fRestore: D$ 0 @fIncUpdate: D$ 0
@rgbReserved: B$ 0 #32]
[rect: ; RECT
@left: d$ 0 @top: d$ 0
@right: d$ WINDOW_WIDTH @bottom: d$ WINDOW_HEIGHT]
[pnt: ; POINT
@x: D$ ? @y: D$ ?]
[msg: ; MSG
@hwnd: D$ 0 @message: D$ 0 @wParam: D$ 0 @lParam: D$ 0
@time: D$ 0 @pt.x: D$ 0 @pt.y: D$ 0]
[<16 clf: ; LOGFONT
@lfHeight: D$ 8
@lfWidth: D$ 8
@lfEscapement: D$ 0
@lfOrientation: D$ 0
@lfWeight: D$ &FW_NORMAL
@lfItalic: B$ 0
@lfUnderline: B$ 0
@lfStrikeOut: B$ 0
@lfCharSet: B$ &ANSI_CHARSET
@lfOutPrecision: B$ &OUT_DEFAULT_PRECIS
@lfClipPrecision: B$ &CLIP_DEFAULT_PRECIS
@lfQuality: B$ &DEFAULT_QUALITY
@lfPitchAndFamily: B$ &DEFAULT_PITCH
@lfFaceName: B$ "Fixedsys", 0]
[<32 ofn: ; OPENFILENAME
@lStructSize: d$ len @hwndOwner: d$ &NULL
@hInstance: d$ &NULL @lpstrFilter: d$ StrFilter
@lpstrCustomFilter:d$ 0 @nMaxCustFilter: d$ 0
@nFilterIndex: d$ 0 @lpstrFile: d$ 0
@nMaxFile: d$ &MAX_PATH @lpstrFileTitle: d$ 0
@nMaxFileTitle: d$ 0 @lpstrInitialDir: d$ 0
@lpstrTitle: d$ 0 @Flags: d$ &OFN_FILEMUSTEXIST
@nFileOffset: W$ 0 @nFileExtension: W$ 0
@lpstrDefExt: d$ 0 @lCustData: d$ 0
@lpfnHook: d$ 0 @lpTemplateName: d$ 0]
[hAccel: d$ ?]
[accelerators: ; ACCELERATORS
@key1: u$ &FVIRTKEY+080 &VK_ESCAPE M00_Exit]
[ACCELS 1]
Main: fninit
call 'comctl32.InitCommonControls'
call 'user32.CreateAcceleratorTableA' accelerators,
ACCELS
mov d$hAccel eax
call 'kernel32.GetModuleHandleA' &NULL
cmp eax 1 | jc ExitProg | mov d$wcx@hInstance eax
call 'user32.LoadIconA' &NULL &IDI_APPLICATION
cmp eax 1 | jc ExitProg | mov d$wcx@hIcon eax
call 'user32.LoadCursorA' &NULL &IDC_ARROW
cmp eax 1 | jc ExitProg | mov d$wcx@hCursor eax
call 'user32.LoadMenuA', d$wcx@hInstance, M00_Menu
mov d$hMenu,eax
; Register the window class for the main window.
call 'user32.RegisterClassExA' wcx
cmp eax 1 | jc ExitProg
call 'user32.AdjustWindowRectEx' rect,
&WS_OVERLAPPED+&WS_CAPTION+&WS_SYSMENU+&WS_MINIMIZEBOX,
&TRUE &NULL
cmp eax 1 | jc ExitProg
mov esi d$rect@right | sub esi d$rect@left
mov edi d$rect@bottom | sub edi d$rect@top
call 'user32.GetSystemMetrics' &SM_CXSCREEN
sub eax esi | shr eax 1 | mov ebx eax
call 'user32.GetSystemMetrics' &SM_CYSCREEN
sub eax edi | shr eax 1
; Create the main window.
call 'user32.CreateWindowExA' &NULL ClassName AppName,
&WS_OVERLAPPED+&WS_CAPTION+&WS_SYSMENU+&WS_MINIMIZEBOX,
ebx eax esi edi,
&NULL d$hMenu,
d$wcx@hInstance &NULL
cmp eax 1 | jc ExitProg | mov d$hWnd,eax
; Show the window and paint its contents.
call 'user32.ShowWindow' eax &SW_SHOWDEFAULT
call 'user32.UpdateWindow' d$hWnd
jmp F1>
; Start the message loop.
B1: call 'user32.TranslateAcceleratorA' d$hWnd d$hAccel,
msg
call 'user32.TranslateMessage' msg
call 'user32.DispatchMessageA' msg
F1: call 'user32.GetMessageA' msg &NULL 0 0
test eax eax | jnz B1
; Return the exit code to Windows.
call 'kernel32.ExitProcess' d$msg@wParam
ExitProg: call 'user32.DestroyAcceleratorTable' d$hAccel
call 'kernel32.GetLastError'
call 'kernel32.ExitProcess' eax
align 16
proc MainWindowProc:
arguments @hWnd @uMsg @wParam @lParam
uses ebx esi edi
mov eax d@uMsg
P1: cmp eax &WM_COMMAND | jne P1>>
mov eax d@wParam
P2: cmp ax M00_Exit | je E9>>
P2: cmp ax M00_Open | jne P2>>
mov d$ofn@lpstrfile LoadName
call 'comdlg32.GetOpenFileNameA', ofn
cmp eax &TRUE | jc P9>>
call 'kernel32.CreateFileA', LoadName &GENERIC_READ,
&NULL &NULL &OPEN_EXISTING,
&FILE_ATTRIBUTE_NORMAL 0
cmp eax &INVALID_HANDLE_VALUE | je E0>>
mov d$hInFile eax
mov eax d$rows | imul eax d$columns
call 'kernel32.ReadFile' d$hInFile column_buffer eax,
read 0
cmp eax &TRUE | jne E0>>
call 'kernel32.CloseHandle' d$hInFile
cmp eax &TRUE | jc P9>>
call 'user32.SetCaretPos' 0 0
mov d$current_column 0, d$current_row 0
call 'user32.InvalidateRect' d@hWnd rect &TRUE
jmp E0>>
P2: cmp ax M00_Save | jne P2>>
mov d$ofn@lpstrfile SaveName
call 'comdlg32.GetSaveFileNameA' ofn
cmp eax &TRUE | jc P9>>
call 'kernel32.CreateFileA', SaveName &GENERIC_WRITE,
&NULL &NULL &CREATE_NEW,
&FILE_ATTRIBUTE_NORMAL 0
cmp eax &INVALID_HANDLE_VALUE | je E0>>
mov d$hOutFile eax
mov eax d$rows | imul eax d$columns
call 'kernel32.WriteFile' d$hOutFile column_buffer,
eax read 0
cmp eax &TRUE | jne E0>>
call 'kernel32.CloseHandle' d$hOutFile
cmp eax &TRUE | jc P9>>
jmp E0>>
P2: cmp ax M00_Clear | jne P2>
mov ecx d$rows | imul ecx d$columns
mov al ' ', edi column_buffer | rep stosb
call 'user32.InvalidateRect' d@hWnd rect &TRUE
jmp E0>>
P2: cmp ax M00_Check | jne E1>>
L1: call check
mov eax Correct | cmovne eax d${d$ Incorrect}
call 'user32.MessageBoxA' d@hWnd eax {"Error", 0},
&MB_OK
jmp E0>>
P1: cmp eax &WM_SETFOCUS | jne P1>
; Create a solid black caret.
call 'user32.CreateCaret' d@hWnd &NULL 25 25
; Adjust the caret position, in client coordinates.
imul esi d$current_column 25 | imul edi d$current_row
25
call 'user32.SetCaretPos' esi edi
; Display the caret.
call 'user32.ShowCaret' d@hWnd
jmp E1>>
P1: cmp eax &WM_CREATE | jne P1>>
push ebp
mov ebp rcZells
xor eax eax | xor ebx ebx ; left, top
mov ecx 25, edx 25 ; right, bottom
mov edi d$rows
B1: mov esi d$columns
B2: mov d$ebp eax, d$ebp+4 ebx, d$ebp+8 ecx, d$ebp+12 edx
add ebp 16 | add eax 25 | add ecx 25
dec esi | jnz B2
xor eax eax | mov ecx 25
add ebx 25 | add edx 25
dec edi | jnz B1
pop ebp
call 'gdi32.CreateFontIndirectA' clf
mov d$hFont eax
call 'gdi32.GetStockObject' &BLACK_PEN
mov d$hBlackPen eax
mov esi colors, edi color_buffer
B0: mov ebx 9
B1: call 'gdi32.CreateSolidBrush' d$esi | add esi 4
mov d$edi eax, d$edi+(3*4) eax, d$edi+(6*4) eax
mov d$edi+(27*4) eax, d$edi+(30*4) eax
mov d$edi+(33*4) eax, d$edi+(54*4) eax
mov d$edi+(57*4) eax, d$edi+(60*4) eax
mov ecx 4
bt d$multipleof3 ebx | cmovc ecx d${d$ (6*4)+4}
add edi ecx | sub ebx 1 | jnz B1
jmp E0>>
P1: cmp eax &WM_KEYDOWN | jne P1>>
mov eax d@wParam
P2: cmp eax &VK_UP | jne P2>
mov eax d$current_row | sub eax 1 | js E0>>
mov d$current_row eax | jmp F1>
P2: cmp eax &VK_DOWN | jne P2>
mov eax d$current_row | add eax 1
cmp eax d$rows | jae E0>>
mov d$current_row eax | jmp F1>
P2: cmp eax &VK_LEFT | jne P2>
mov eax d$current_column | sub eax 1 | js E0>>
mov d$current_column eax | jmp F1>
P2: cmp eax &VK_RIGHT | jne E0>>
mov eax d$current_column | add eax 1
cmp eax d$columns | jae E0>>
mov d$current_column eax
F1: imul esi d$current_column 25
imul edi d$current_row 25
call 'user32.SetCaretPos' esi edi
jmp E0>>
P1: cmp eax &WM_CHAR | jne P1>>
mov eax d@wParam, esi d$columns, edi d$rows
mov ecx d$current_column, edx d$current_row
cmp eax 8 | je F1>>
test b$chartab+eax 1 | jz E0>>
; Write the character to the buffer.
mov ebx edx | imul ebx esi | add ebx ecx
mov b$column_buffer+ebx al
; Increment cursor position.
add ecx 1 | cmp ecx esi | jb F3>> | xor ecx ecx
add edx 1 | cmp edx edi | jb F3>> | xor edx edx
jmp F3>>
; Decrement cursor position.
F1: sub ecx 1 | jns F2> | lea ecx d$esi-1
sub edx 1 | jns F2> | lea edx d$edi-1
; Write a space character to the buffer.
F2: mov ebx edx | imul ebx esi | add ebx ecx
mov b$column_buffer+ebx ' '
; Set new row and column and initiate redraw.
F3: mov d$current_column ecx, d$current_row edx
shl ebx 4 | add ebx rcZells
call 'user32.InvalidateRect' d@hWnd ebx &TRUE
jmp E0>>
P1: cmp eax &WM_PAINT | jne P7>>
call 'user32.BeginPaint' d@hWnd psx
call 'user32.HideCaret' d@hWnd
call 'gdi32.SelectObject' d$psx@hdc d$hFont
; Draw the grid.
xor ebx ebx
mov edi d$rows
B1: mov esi d$columns
B2: call 'gdi32.SelectObject' d$psx@hdc,
d$color_buffer+ebx*4
lea eax d$rcZells+ebx*8 | lea eax d$eax+ebx*8
call 'gdi32.Rectangle' d$psx@hdc d$eax d$eax+4,
d$eax+8 d$eax+12
inc ebx | dec esi | jnz B2
dec edi | jnz B1<<
call 'gdi32.CreatePen' &PS_SOLID 4 0 | push eax
call 'gdi32.SelectObject' d$psx@hdc eax
call 'gdi32.MoveToEx' d$psx@hdc 74 0 pnt
call 'gdi32.LineTo' d$psx@hdc 74 225
call 'gdi32.MoveToEx' d$psx@hdc 149 0 pnt
call 'gdi32.LineTo' d$psx@hdc 149 225
call 'gdi32.MoveToEx' d$psx@hdc 0 74 pnt
call 'gdi32.LineTo' d$psx@hdc 225 74
call 'gdi32.MoveToEx' d$psx@hdc 0 149 pnt
call 'gdi32.LineTo' d$psx@hdc 225 149
pop eax | call 'gdi32.DeleteObject' eax
; Fill in the characters.
call 'gdi32.SetTextColor' d$psx@hdc 0
xor ebx ebx, esi esi, edi edi
B1: xor esi esi
B2: imul edx edi 25 | add edx 6
imul ecx esi 25 | add ecx 6
lea eax d$ColumnBuffer+ebx
call 'gdi32.TextOutA' d$psx@hdc ecx edx eax 1
add ebx 1
add esi 1 | cmp esi d$columns | jb B2 | xor esi esi
add edi 1 | cmp edi d$rows | jb B1
imul edi d$current_column 25
imul esi d$current_row 25
call 'user32.SetCaretPos' edi esi
call 'user32.ShowCaret' d@hWnd
call 'user32.EndPaint' d@hWnd psx
jmp E0>
P7: cmp eax &WM_DESTROY | jne P8>
E9: call 'gdi32.DeleteObject' d$hFont
call 'user32.PostQuitMessage' &NULL
P8: call 'user32.DefWindowProcA' d@hWnd d@uMsg,
d@wParam d@lParam
jmp P9>
E1: mov eax &TRUE | jmp P9>
E0: xor eax eax
endp
align 16
subrt check:
mov ecx 9, esi column_buffer
S4: mov eax d$esi, ebx d$esi+9, edx d$esi+18
lea eax d$eax+(-6316128)+ebx
lea eax d$eax+(-3158064)+edx
add ah al | shr eax 8 | add al ah
cmp al 45 | jne S2>> ; | add esi 3
mov edi 3 | bt d$Multiple_of_3 ecx | cmovc edi d${d$
21}
add esi edi | dec ecx | jnz S4<
mov ecx 9, esi column_buffer
S4: mov eax d$esi, ebx d$esi+3, edx d$esi+6
lea eax d$eax+(-6316128)+ebx
lea eax d$eax+(-3158064)+edx
add ah al | shr eax 8 | add al ah
cmp al 45 | jne S2>> | add esi 9
dec ecx | jnz S4<<
pxor mm0 mm0 | xor eax eax
movq mm1 q${q$ 03030303030303030}
mov ecx 9, esi column_buffer
S1: paddb mm0 q$esi | add al b$esi+8 | add esi 9
psubb mm0 mm1 | sub al 030
dec ecx | jnz S1
cmp al 02d | jne S2>
pcmpeqb mm0 q${q$ 02d2d2d2d2d2d2d2d} | pmovmskb eax mm0
cmp al 0ff
S2: ret
ends check
;------------------------
; General purpose macros:
;------------------------
[push | push #1 | #+1] [pop | pop #1 | #+1] [mov | mov #1 #2 | #+2]
[inc | inc #1 | #+1] [dec | dec #1 | #+1] [xor | xor #1 #2 | #+2]
[movq | movq #1 #2 | #+2]
[call | push #L>2 | call #1] [subrt | #1] [ends | nope]
[Proc | &1=0 | &2=0 | &3= | #1 | push ebp | mov ebp esp]
[Arguments | {#1 Arg#x} | #+1 | &1=SizeOf#x]
[Argument | {#1 Arg#x} | #+1 | &1=SizeOf#x]
[Local | {#1 Local#x} | #+1 | sub esp SizeOf#x | &2=SizeOf#x]
[StrucPtrs | {#3 ebp+#2+#F} | #+2]
[Structure | {#1 ebp-&2-4} | sub esp #2+4
| mov D$#1 esp | StrucPtrs 0-&2-#2-4 #L>3]
[Uses | push #1>L | &3=pop #L>1]
[EndP | P9: | &3 | mov esp ebp | pop ebp | ret &1]
[Arg1 ebp+8 Arg2 ebp+12 Arg3 ebp+16 Arg4 ebp+20 Arg5 ebp+24
Arg6 ebp+28 Arg7 ebp+32 Arg8 ebp+36 Arg9 ebp+40 Arg10 ebp+44]
[Local1 ebp-4 Local2 ebp-8 Local3 ebp-12 Local4 ebp-16
Local5 ebp-20 Local6 ebp-24 Local7 ebp-28 Local8 ebp-32
Local9 ebp-36 Local10 ebp-40]
[SizeOf1 4 SizeOf2 8 SizeOf3 12 SizeOf4 16 SizeOf5 20
SizeOf6 24 SizeOf7 28 SizeOf8 32 SizeOf9 36 SizeOf10 40]
--
wfz
Frank Kotler
> Hi!
>
> I learned a lot about the Windows API while writing this, so I thought
> I'd share it with you guys. No solver, 'cause you should use your
> brains to solve 'em, not your CPU. It is just meant to do it on the
> screen, instead of the paper.
Herbert already posted a "solver", IIRC. :)
> Enjoy! Or if you don't, you don't have to tell me, there is enough
> bitching going on around here!
Well... I can't test it, but it *looks* like it'd be cool!
Hey, "Spam Killer"... do you recall sending me the examples from
Jonathan Bartlett's "PGU" book, translated to Nasm? That's something I
lost in "the partition mishap" that I haven't recovered. If you've still
got that around, could you resend? ( fbko...@verizon.net) If you can't
lay your hands on it, no great problem to redo it...
Haven't heard from you for a while. Good to see you still "active" in asm!
Best,
Frank
Spam Killer
>
>Hey, "Spam Killer"... do you recall sending me the examples from
>Jonathan Bartlett's "PGU" book, translated to Nasm? That's something I
>lost in "the partition mishap" that I haven't recovered. If you've still
Look into your mail-box.
>
>Haven't heard from you for a while. Good to see you still "active" in asm!
>
Thanks! That will never change, I'm hooked to it!
BTW.: There are two wraping lines in the code
One where the 25 from an imul wraps.
And one from a cmovcc where 21} wraps.
The latter confuses RosAsm when loaded as source only, and
should be fixed before hitting the compile menu option.
--
wfz
Frank Kotler
> On Thu, 29 Nov 2007 23:25:23 GMT, Frank Kotler wrote:
>
>>Hey, "Spam Killer"... do you recall sending me the examples from
>>Jonathan Bartlett's "PGU" book, translated to Nasm? That's something I
>>lost in "the partition mishap" that I haven't recovered. If you've still
>>got that around, could you resend? If you can't
>>lay your hands on it, no great problem to redo it...
>
> Look into your mail-box.
Presto! Thanks! Lest I lose it again, I've repackaged it to include just
the Nasm examples, and stuck it up as:
<http://mysite.verizon.net/fbkotler/nasm-pgu-examples.tar.bz2>
The "READDME" I put with it goes like:
--------------------------
These are the examples from Jonathan Bartlett's book,
"Programming from the Ground Up", which uses Gas syntax,
kindly translated to Nasm syntax by Wilhelm Zadrapa.
Note that these are for Linux - sorry, Windows users.
To make any sense of 'em, you'll want the book:
http://www.cafepress.com/bartlettpublish.8640017
Also available in the "'free' as in 'freeloader'" version:
http://savannah.nongnu.org/projects/pgubook/
for those not in the bucks.
If you'd like to read the book, but "follow along" using Nasm,
here are the examples! Thanks Jonathan! Thanks Wilhelm!
fbk - 11/30/07
------------------------
Really appreciate the quick response! Something I meant to do ages ago...
Best,
Frank
Terence
colours and screen switching..
Allows input, storing, solving, optional step-by-step, which shows
rules applied and second screen of possibilities, progress, optional
hints and so on. Runs in DOS or DOS in Windows.
Terence
Tried program on over 100 "hard" problems.
Three non-solved, needing me to add two further uncommon rules.
a) if "only 2 or 3 same possibilities exist in intersection of square
and row (or column); three of same square in row of three still blank;
then remove these three possibilities from the rest of the row (or
column) and intersected square".
b) same applied to four places, with same four possibilities as three
blank places in intersection as above, and fourth place in same square
elsewhere. Remove four possibiliteis from rest of square only.
Maybe that will do it!
By hand I found drawing lines from one "onely two possibilities" by
each implied route of possibile resolution, always causes one route
(the invalid one) to arrive a a point of oppossite conclusion, leaving
other route and victor and solution. But programming this is fiendish.
Solving by exhaustion is, to me, cheating.
Spam Killer
I accidently hit an 'a' and when it went in I found that error:
>[<32 chartab: b$ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
> 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
> 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
> 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 b$ 0 #192]
The last line should be changed to:
0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0]
[<charpad: b$ 0 #192]
I'm always surprised how easily such errors slip into a post, and ok,
that calls for a bonus pack. The stuff below inserted before another
P1: in the MainWindowProc will set the cursor with the left mouse
button.
P1: cmp eax &WM_LBUTTONDOWN | jne P1>
movzx eax w@lParam | mul d${d$ 0a3d70a4}
imul esi edx 25 | mov d$current_column edx
movzx eax w@lParam+2 | mul d${d$ 0a3d70a4}
imul edi edx 25 | mov d$current_row edx
call 'user32.SetCaretPos' esi edi
jmp E0>>
--
wfz
Spam Killer
>Still working on adding to this.
>...
If you want feedback from the group, you would have to supply an URL
to your program.
--
wfz
Herbert Kleebauer
>
> Still working on adding to this.
> Tried program on over 100 "hard" problems.
> Three non-solved, needing me to add two further uncommon rules.
Can you please post this 3 puzzles. I'm still looking for an
example which can't be solved with a very simple algorithm
with only 1 level of indirection. Here five examples (and the
binary of the program; assembler source already posted here) which
I was told to be hard to solve, but which the program still
solves.
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
@echo off
echo Bj@jzh`0X-`/PPPPPPa(DE(DM(DO(Dh(Ls(Lu(LX(LeZRR]EEEUYRX2Dx=>sudo.com
echo 0DxFP,0Xx.t0P,=XtGsB4o@$?PIyU WwX0GwUY Wv;ovBX2Gv0ExGIuht6>>sudo.com
echo }e{f?D[@xe?c??P@ge?s?Bu?ok??suq\H{P?eov\eQp[AjNwHefdGjUKFe>>sudo.com
echo ft??E?eB}RCEBMSaf=Ngel??A?Wge\??@?ANe`??n@ge?s??uA1s?S[}eX>>sudo.com
echo ??D?PxeX????Jefd?DEwe{tPOg@NAyeH????H=eH????ODexeWsP?WgFf?>>sudo.com
echo ?OUHeHzge\????essP?UgFe??OeaP1[tLt_@e=efOSeEHQCEBMtaflsweH>>sudo.com
echo ??D?e[jRDEwAj??oweMc?CuBKj?KWweH??D?~ge=??@?[ge\??A?]gel??>>sudo.com
echo A?e_eTD[}Ee??OE_~Ij??o_eMS_}eh??E?[~eX??D?PxeX????efrV`edU>>sudo.com
echo BeOue_eTD[}Ee??O?PxEe??Of~p[EJeHt?D]BeZde@NROg@NAyeH????Zp>>sudo.com
echo epH=eH????ODexfbsPUHeHUge\????eHrP~NB}OpepeMjRtZD]HeDcCjRN>>sudo.com
echo JBexPe~vLeaVePt\sZD]EwfCHefdGj]K_@e=efOSeEHQCEBMUafl~DexGN>>sudo.com
echo e`~~==`e~VewO]BeBfe@GRxO`xeBe\}e_d?D[@xe?c??H?ze?c??G?ef?S>>sudo.com
echo eEJQfAH]CBe@ef]U]SJ_tJeTAxqrDNe`??xB@e?seOiR=OHKeB}RgDNw??>>sudo.com
echo ??EBexafcs}eCf?D[@xe?c??H?ze?c??G?ef?SeEJQfAH]kLeHefZTlkLU>>sudo.com
echo ef?SmCB_JefDemSWftJteAx[eDNg????i@e=HeOC}=OrNeBC?TDIe??OCE>>sudo.com
echo BMxafl[}eX??D?BxeH????BzeH????JefdHeEcefAVCEBCJefDfCUPEBeP>>sudo.com
echo efGSGUJCBefDfcEPUJePefcSgEBCJefDfgUPEBePefkSkUJCBefDfGETUJ>>sudo.com
echo ePefGTKEBSJefDfKUTEBePefOTOUJStAx[@e`seOiR=OHKtB}RBeTceKER>>sudo.com
echo PtJdEBexafGt`eCUewO]`eBVexO]_eBVeLoQ?IgJo??_geIs??AA}e?c?D>>sudo.com
echo [@ze?c??H?=e?c??H?ef?SeUJQCEBMIxeH????eooQqiP1?eFSuaf=emoQ>>sudo.com
echo ?MgFe??OYtLteLoQ?AgFo??_geIs??y?Je?Se?t\eO`X_eBVEHexCkfhGs>>sudo.com
echo ?F_geL????eqj1eO`X_eBVy~saxDW`p?@?`LZNO`eduNe`DWECeBe\Wa_X>>sudo.com
echo ?sDWDWyE?@xA?@zAe`LReO`X?wBJ`LKLhILOdkkTk`fTmh_SstoTIL??qh>>sudo.com
echo cTsbdT_xkDknrTcduTIL??knrTcduThv_S_gsDdmnTdq_SqtbTnhrTL?m@>>sudo.com
echo nmISr_sPuknTa`dT_dkDshvTn_gP_dmDbdqTrqtTmnhTm??O0xxxxxxxxx>>sudo.com
:::::::::::::::::::::::::: puzzle 1
echo 000 000 501 >a1
echo 000 040 060 >>a1
echo 620 300 000 >>a1
echo 001 702 000 >>a1
echo 000 406 083 >>a1
echo 007 000 000 >>a1
echo 083 000 009 >>a1
echo 700 050 400 >>a1
echo 000 900 100 >>a1
:::::::::::::::::::::::::: puzzle 2
echo 000 060 080 >a2
echo 700 500 000 >>a2
echo 000 801 000 >>a2
echo 009 006 000 >>a2
echo 000 000 201 >>a2
echo 000 024 600 >>a2
echo 030 000 052 >>a2
echo 105 003 000 >>a2
echo 020 900 408 >>a2
:::::::::::::::::::::::::: puzzle 3
echo 060 700 080 >a3
echo 040 050 900 >>a3
echo 000 001 003 >>a3
echo 002 000 001 >>a3
echo 070 004 060 >>a3
echo 800 003 500 >>a3
echo 900 800 000 >>a3
echo 001 020 070 >>a3
echo 050 006 000 >>a3
:::::::::::::::::::::::::: puzzle 4
echo 070 080 050 >a4
echo 900 000 002 >>a4
echo 000 405 000 >>a4
echo 006 040 700 >>a4
echo 300 702 004 >>a4
echo 000 050 900 >>a4
echo 004 803 000 >>a4
echo 700 000 009 >>a4
echo 030 090 010 >>a4
:::::::::::::::::::::::::: puzzle 5
echo 000 005 009 >a5
echo 001 000 300 >>a5
echo 040 902 010 >>a5
echo 506 030 007 >>a5
echo 000 020 000 >>a5
echo 003 000 408 >>a5
echo 090 500 020 >>a5
echo 007 000 900 >>a5
echo 000 008 000 >>a5
:::::::::::::::::::::::::: puzzle 6 (an easy one)
echo 400 000 582 >a6
echo 000 503 000 >>a6
echo 700 028 090 >>a6
echo 897 000 050 >>a6
echo 304 090 108 >>a6
echo 060 000 937 >>a6
echo 070 630 005 >>a6
echo 000 807 000 >>a6
echo 238 000 001 >>a6
sudo <a1
pause
sudo <a2
pause
sudo <a3
pause
sudo <a4
pause
sudo <a5
pause
sudo <a6
pause
for %%i in (a1 a2 a3 a4 a5 a6 sudo.com) do del %%i
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Evenbit
>
> Presto! Thanks! Lest I lose it again, I've repackaged it to include just
> the Nasm examples, and stuck it up as:
>
> <http://mysite.verizon.net/fbkotler/nasm-pgu-examples.tar.bz2>
>
> The "READDME" I put with it goes like:
>
> --------------------------
> These are the examples from Jonathan Bartlett's book,
> "Programming from the Ground Up", which uses Gas syntax,
> kindly translated to Nasm syntax by Wilhelm Zadrapa.
>
> Note that these are for Linux - sorry, Windows users.
>
Here are two of those examples transmuted to Windows (using MinGW):
----------------------------------------------
;; Time-stamp: <> -*-nasm-*-
;; windows.inc: Common Windows Definitions.
; Library call
%macro lcall 1
extern %1
call %1
%endmacro
# Standard File Descriptors
STD_INPUT_HANDLE equ -10
STD_OUTPUT_HANDLE equ -11
STD_ERROR_HANDLE equ -12
# Common Status Codes
END_OF_FILE equ 0
----------------------------------------------
;; Time-stamp: <> -*-nasm-*-
;; helloworld.asm: This program writes the message "hello world" and
exits.
%include "windows.inc"
global _main
section .text
_main: push helloworld
lcall _printf
push 0
lcall _exit
section .data
helloworld db "hello world", 10, 0
----------------------------------------------
;; Time-stamp: <> -*-nasm-*-
;; helloworld-nolib.asm: This program writes the message "hello world"
and exits.
%include "windows.inc"
global _main
section .text
_main: push DWORD STD_OUTPUT_HANDLE
lcall _GetStdHandle@4
push DWORD 0
push written
push DWORD HWLEN
push helloworld
push eax
lcall _WriteFile@20
push DWORD 0
lcall _ExitProcess@4
section .data
helloworld db "hello world", 10
HWLEN equ $ - helloworld
written dd 0
Nathan.
Evenbit
>
> ----------------------------------------------
> ;; Time-stamp: <> -*-nasm-*-
> ;; helloworld.asm: This program writes the message "hello world" and
> exits.
>
> %include "windows.inc"
>
> global _main
>
> section .text
> _main: push helloworld
> lcall _printf
Oops! I believe this needs 'add esp, 4' ... isn't present in
Wilhelm's code either.
> push 0
> lcall _exit
>
> section .data
> helloworld db "hello world", 10, 0
>
Nathan.
Spam Killer
>> section .text
>> _main: push helloworld
>> lcall _printf
>
>Oops! I believe this needs 'add esp, 4' ... isn't present in
>Wilhelm's code either.
>
>> push 0
>> lcall _exit
>>
>> section .data
>> helloworld db "hello world", 10, 0
>>
I sticked as close as I could to the original code in the examples:
.section .text
.globl _start
_start:
pushl $helloworld
call printf
pushl $0
call exit>
Frank Kotler
Yeah, not in Jonathan's code either... I think it's fair to say that we
"should" balance the stack (unlike the Windows API, the callee won't do
it for us). We can "defer" it, however... and since we exit with
"(_)exit", we don't give a damn what's on the stack. Unlike a "main"
that's called from C startup code, the "_start" label is jumped-to, not
called. Starting from a "_start" label, we don't have the option of
exiting with "ret". With "main", we do. In this case, it would be
disasterous to not clean up the stack! Note that if we do a stack frame
using ebp, the "mov esp, ebp" or "leave" will save our ass if we "defer"
cleaning up the stack...
In an example of "how to call C", it really ought to be there, I think.
Printf is wasted on hello world, anyway. Now *floats* are a bit of a
PITA to display, and might be worth compromising our principles for.
Printf thinks all floats are double precision, and take 8 bytes on the
stack. If you've got the thing in an FPU reg, "sub esp, 8","fst qword
[esp]"...
Best,
Frank
; nasm -f elf32 floatnum.asm
; ld -o floatnum floatnum.o -I/lib/ld-linux.so.2 -lc
extern printf
global _start
section .data
fmt db "The number is: %f", 10, 0
num dq 1.234
section .text
_start:
push dword [num + 4]
push dword [num]
push fmt
call printf
add esp, 3 * 4
mov eax, 1
int 80h
Terence
HARD BUT SOLVABLE
007000800050020090903000701000408000030000060000705000409000300020080070001000400
200030056007010000001600003840000000002000500000000061500003900000040700370090005
040000065009020300005100000000500030000639000010008090004006700008040100350000040
009700001704800000500060070000300060020000010030009000090030002000008504800001600
020000900400506710300000000003085000000174000000390600000000008085901007006000040
810000200000007800007000014400090008006050900200070001570000300003400000009000026
REALLY DIFFICULT
593006001010050006000700000050000400070804050002000090000008000700030060600100732
000109000006040900800000005070050080215000739030010020700000003001070200000804000
039007000000500201000090070960000000407000503000000019090020000503008000000400120
NOT SURE IF POSSIBLE!
700605009000800030001000004007000205090000080308000700200000600010009000800506007
500200010001900730000000800050020008062039000000004300000000000080467900007300000
000023000004000100050084090001070902093006000000010760000000000800000004060000587
000042059450090008000000000000004080000000703000836002369200001700000000005001600
000000000360000920000010070000000204000036500100025730072809300900000080040000000
600400030000001050410800000040350200000700008002060500900000000730500086004000700
000300805060000030000050267006100002003405700004008000278000900000001000000000600
040080700020000000800030510000208906000009020000500000100000300090406005000050000
005100000600003000300000706000030601009050400802090000401000005000500008000007200
200000007015000020080200006000000064890000000000050910040815000061030000000006400
TBW
Mike Jones
I just passed the last 10 to Herbert's Solver and it rattled through
them, no problem.
Terence
exhaustive searches.
May Herbert's isn't that kind.
I took Herebert's batch file code and cut-and-pasted to Notepad, saved
as a batch file and then ran the batch file to make sudo.com
Then I ran this with the a1 problem as-is.
.
It wouldn't terminate and hung up on "illegal instruction"
.C5:057b IP:058c OP:63 3f 48 3f
Any clues?
.
Terence
My point was to emulate how a human solves SUDOKU puzzles WITHOUT
using
exhaustive searches.
May Herbert's isn't that kind.
I took Heebert's batch file code and cut-and-pasted to Notepad, saved
as a batch file and then ran the batch file to make sudo.com
This does some funny things at 100H which don't look right at all.
Anyway, I ran this with the a1 problem as-is, using
sudo a1 <ret>.
.
It wouldn't terminate and hung up on "illegal instruction"
.C5:057b IP:058c OP:63 3f 48 3f
Any clues?
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
Evenbit
>
> In an example of "how to call C", it really ought to be there, I think.
> Printf is wasted on hello world, anyway. Now *floats* are a bit of a
> PITA to display, and might be worth compromising our principles for.
> Printf thinks all floats are double precision, and take 8 bytes on the
> stack. If you've got the thing in an FPU reg, "sub esp, 8","fst qword
> [esp]"...
Interesting....
extern _printf
extern _exit
global _main
section .data
fmt db "Your holiday desert is %f percent of pie.", 10, 0
section .text
_main:
finit
fldpi
sub esp, 8
fst qword [esp]
push fmt
call _printf
add esp, 3 * 4
push dword 0
call _exit
> ; nasm -f elf32 floatnum.asm
> ; ld -o floatnum floatnum.o -I/lib/ld-linux.so.2 -lc
>
> extern printf
> global _start
>
> section .data
> fmt db "The number is: %f", 10, 0
> num dq 1.234
>
> section .text
> _start:
> push dword [num + 4]
> push dword [num]
> push fmt
> call printf
> add esp, 3 * 4
>
> mov eax, 1
> int 80h
Yes, a few extra examples sprinkled on top of the PGU group makes a
nice beginner collection. Maybe I'll get some ideas from the HLA
examples or the "12 Lessons" to flesh it out some.
Nathan.
Rosario
>OOPS!
>My point was to emulate how a human solves SUDOKU puzzles WITHOUT
>using
>exhaustive searches.
>May Herbert's isn't that kind.
>
>I took Heebert's batch file code and cut-and-pasted to Notepad, saved
>as a batch file and then ran the batch file to make sudo.com
>
>This does some funny things at 100H which don't look right at all.
>Anyway, I ran this with the a1 problem as-is, using
>sudo a1 <ret>.
>.
>It wouldn't terminate and hung up on "illegal instruction"
>.C5:057b IP:058c OP:63 3f 48 3f
>Any clues?
i have pasted *all* code and exercise in notepad
change the name of the file in "h.bat"
run h.bat in a dos windows, no .com file but all goes ok for the run
(not know how)
but how to play in that game? what are the rules?
Herbert Kleebauer
> I took Herebert's batch file code and cut-and-pasted to Notepad, saved
> as a batch file and then ran the batch file to make sudo.com
> Then I ran this with the a1 problem as-is.
> .
> It wouldn't terminate and hung up on "illegal instruction"
> .C5:057b IP:058c OP:63 3f 48 3f
> Any clues?
Most probably this is a copy and paste error (some editors
have a problem with ` followed by a character). Better don't
copy and paste but save the posting and then open it with an
editor (or assembly the source yourself, then you get the real
binary and not an ascii encoded one). Here a different ascii
version without the ` character.
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
@echo off
echo hD1X-s0P_kUHP0UxGWX4ax1y1ieimnfeinklddmemkjanmndnadmndnpbbn>sudo.com
echo hhpbbnpljhoxolnhaigidpllnbkdnhlkfhlflefblffahfUebdfahhfkokh>>sudo.com
echo wPajQJ///MKiF0///M5uqA///k1AmNDRFkH1r0jNl7hNDgekbNKWKgC1bNq>>sudo.com
echo l5///yDUN2OA0b8CpaVyX1///aVCK0///axUUj0///M5uq1///ErLat@L4/>>sudo.com
echo //aZPI////bNqW5I7kplXN0XC3adf/////apP1////aJ7ooVVNcX4///kNa>>sudo.com
echo Zc4aVyS////oFXNcP4///UNF@iNBJ6ra4AsEQaN8OUN2OA0b8ShaV@B4///>>sudo.com
echo fnVNsOE0//kuCM5iqH///gC2aV@54///aVyz0///aVCL1///aVib1///a0a>>sudo.com
echo NymJ0//UNz1e0//kuCM5Mat@c5///ax@L4///aZPI////nTaNZOKMEOqka0>>sudo.com
echo aNymJ0//UNt54///UNlwzNahc041QRPNqUD6UN0XC3adf/////a4nqapP1/>>sudo.com
echo ///aJ7ooBmNaZc4aViJ////nZUN2ywza42ofvUN4iRR4MKWHjC0aBsmzPKo>>sudo.com
echo WPKHp4hN4iBRbUb0bNKWSgC1a4AsEQaN8OUN2OA0b8iZaJszax/WxxzzzPK>>sudo.com
echo MEWjN2PqU76UNV0NyaBgNUNajQJ///MKi8////Mqi7////QaN@OUN89wNaB>>sudo.com
echo /0SSaN@EVbahIRmbXkaxEVt2///MKke2VN8/RDyDUNDI7u////aBclYQas3>>sudo.com
echo PajQJ///MKi8////Mqi7////QaN@OUN89wNap7@PRaNBmKP/QaN2EUfbNq1>>sudo.com
echo IseN@Jrtt7gNDIcd////a4guEMK1ErXz2Mq24K8///UN2OA0b8Siat@L4//>>sudo.com
echo /aZv/////ahv/////bNqW5MKW1TaN2M30bNq1KFkNaBUF7QaN@M41bNq/5F>>sudo.com
echo mNahUJYQaN2M39bNq1KVmNaBUFgQaN@M4@bNq/5VoNahUJ7RaN2M3HbNq1K>>sudo.com
echo loNaBUFERaN@M4It7QRVMKke2VN8/RDyDERJMqU5nUN@JLYaBcl7Ras3OKM>>sudo.com
echo EWjN2PKMEajN2P5MkqUNcf7////g9M5u11///MajQJ///Mqi8////MKj8//>>sudo.com
echo //QaN@OVN2OA0aZf1////k1XNFfiQ6M5Eb8ixkuWNcv3///UNBJbqkqUNc@>>sudo.com
echo 3////g9M5uu////MqGp0gNV0dN2P5MaZclbl9V/H61aVC7////f@jNV0dN2>>sudo.com
echo P5MoyXiMJEi0/EAPrQ7a45YaxUh5UJ0aBgNU89K4E@EuWJ0t5//v5//B6WN>>sudo.com
echo V0dN2X@/ApQ7BcEOglKNb45PUYaPkJ6R/oU1YZaQZB5RgZ67nx5PqJ5N/oU>>sudo.com
echo 1nx5PqJ5NUQLOoV57jtKNU7LNXJbQnZqPi0E29sqPo0mQjlaRZ4aMgJ57rZ>>sudo.com
echo 5Rc0mPiJ57mJqMp8rQdxaP//UP.>>sudo.com
:::::::::::::::::::::::::: puzzle 7
echo 000 000 002 >a7
echo 009 700 100 >>a7
echo 050 301 040 >>a7
echo 023 000 650 >>a7
echo 000 000 000 >>a7
echo 046 000 790 >>a7
echo 000 507 000 >>a7
echo 002 600 300 >>a7
echo 800 000 001 >>a7
:::::::::::::::::::::::::: puzzle 8
echo 300 070 005 >a8
echo 070 009 000 >>a8
echo 400 005 020 >>a8
echo 701 060 008 >>a8
echo 008 000 300 >>a8
echo 090 000 700 >>a8
echo 020 700 009 >>a8
echo 050 800 040 >>a8
echo 000 010 000 >>a8
sudo <a1
pause
sudo <a2
pause
sudo <a3
pause
sudo <a4
pause
sudo <a5
pause
sudo <a6
pause
sudo <a7
pause
sudo <a8
pause
for %%i in (a1 a2 a3 a4 a5 a6 a7 a8 sudo.com) do del %%i
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
The source code:
@=$100
bclr.w #10,sr
;***********************************************************************
; read 81 digits from stdin, anything else is ignored, 0 for unknown
;***********************************************************************
move.l #brett,r5
move.l #81,r2
_10: bsr.l getc
sub.b #'0',r0
blo.b _10
beq.b _20
cmp.b #9,r0
bhi.b _10
eor.l r1,r1
bset.l r0,r1
move.l r1,(r5)
br.b _30
_20: move.l #$03fe0000,(r5)
_30: addq.l #4,r5
dbf.l r2,_10
;***********************************************************************
bsr.l display
bsr.l check
bcs.l _err
bsr.l reduce
beq.b _found0
;***********************************************************************
; if not found directly, do one level of recursion of try and error
;***********************************************************************
move.l #brett,r5
move.l #81,r2
_50: move.l (r5),r0
tst.w r0,r0
bne.b _40
lsr.l #16,r0
move.l #2,r1
move.l #9,r4
_60: tst.l r1,r0
beq.b _70
bsr.l save
move.l r1,(r5)
bsr.l reduce
beq.b _found1
bsr.l restore
_70: lsl.l #1,r1
dec.l r4
bne.b _60
_80: lsl.l #16,r0
move.l r0,(r5)
_40: addq.l #4,r5
dbf.l r2,_50
move.l #text4,r0
br.b _130
_found0:move.l #text2,r0
br.b _120
_err: move.l #text1,r0
br.b _130
_found1:move.l #text3,r0
_120: bsr.l display
_130: bsr.l out_text
bsr.l exit
;***********************************************************************
save: movem.l r0-r7,-(sp)
move.l #brett,r5
move.l #brett1,r6
br.b rest1
restore:movem.l r0-r7,-(sp)
move.l #brett1,r5
move.l #brett,r6
rest1: move.l #81,r2
rep_r2 move.l (r5)+-,(r6)+-{s1}
movem.l (sp)+,r0-r7
rts.l
;***********************************************************************
; remove all impossible configurations
; carry: 1: unsolveabel
; 0: solveabel
; zero: 1: solved
; 0: not solved
;***********************************************************************
reduce: movem.l r0-r7,-(sp)
_90: move.l #brett,r5
move.l #81,r2
eor.l r6,r6
_50: move.l (r5),r0
tst.w r0,r0
bne.b _40
orq.l #1,r6
lsr.l #16,r0
move.l #2,r1
eor.l r3,r3
move.l #9,r4
_20: tst.l r1,r0
beq.b _10
move.l r1,(r5)
bsr.l check
bcc.b _70
orq.l #-1,r6
eor.l r1,r0
br.b _10
_70: tst.l r3,r3
bne.b _30
move.l r1,r3
br.b _10
_30: orq.l #-1,r3
_10: lsl.l #1,r1
dec.l r4
bne.b _20
tst.l r3,r3
beq.b _err
bmi.b _80
move.l r3,(r5)
br.b _40
_80: lsl.l #16,r0
move.l r0,(r5)
_40: addq.l #4,r5
dbf.l r2,_50
tst.l r6,r6
bmi.l _90
movem.l (sp)+,r0-r7
bclr.w #0,sr ; carry=0 zero=1(solution found) or 0
rts.l
_err: orq.l #1,r0 ; clear zero flag
movem.l (sp)+,r0-r7
bset.w #0,sr
rts.l
;***********************************************************************
; check if legal
; carry: 0: legal
; 1: illegal
;***********************************************************************
check: movem.l r0-r7,-(sp)
move.l #brett,r5
move.l #9,r2
_40: move.l #8,r3
move.l (r5),r0
move.l r0,r1
_30: add.l (r5,r3*4),r0
or.l (r5,r3*4),r1
dec.l r3
bne.b _30
cmp.w r0,r1
bne.l _err
lsr.l #16,r1
or.l r1,r0
cmp.w #$03fe,r0
bne.l _err
addq.l #9*4,r5
dbf.l r2,_40
move.l #brett,r5
move.l #9,r2
_60: move.l #8,r3
move.l (r5),r0
move.l r0,r1
_50: lea.l (r3,r3*2),r4
lea.l (r4,r4*2),r4
add.l (r5,r4*4),r0
or.l (r5,r4*4),r1
dec.l r3
bne.b _50
cmp.w r0,r1
bne.l _err
lsr.l #16,r1
or.l r1,r0
cmp.w #$03fe,r0
bne.l _err
addq.l #4,r5
dbf.l r2,_60
move.l #brett,r5
move.l #3,r2
_20: move.l #3,r3
_10: move.l (r5),r0
move.l r0,r1
add.l 0*36+1*4.b(r5),r0
or.l 0*36+1*4.b(r5),r1
add.l 0*36+2*4.b(r5),r0
or.l 0*36+2*4.b(r5),r1
add.l 1*36+0*4.b(r5),r0
or.l 1*36+0*4.b(r5),r1
add.l 1*36+1*4.b(r5),r0
or.l 1*36+1*4.b(r5),r1
add.l 1*36+2*4.b(r5),r0
or.l 1*36+2*4.b(r5),r1
add.l 2*36+0*4.b(r5),r0
or.l 2*36+0*4.b(r5),r1
add.l 2*36+1*4.b(r5),r0
or.l 2*36+1*4.b(r5),r1
add.l 2*36+2*4.b(r5),r0
or.l 2*36+2*4.b(r5),r1
cmp.w r0,r1
bne.b _err
lsr.l #16,r1
or.l r1,r0
cmp.w #$03fe,r0
bne.b _err
addq.l #3*4,r5
dec.l r3
bne.b _10
addq.l #2*9*4,r5
dbf.l r2,_20
movem.l (sp)+,r0-r7
bclr.w #0,sr
rts.l
_err: movem.l (sp)+,r0-r7
bset.w #0,sr
rts.l
;***********************************************************************
display:movem.l r0-r7,-(sp)
move.b #13,r0
bsr.l putc
move.b #10,r0
bsr.l putc
move.l #brett,r5
move.l #9,r3
_40: move.l #9,r4
_30: move.l (r5),r1
addq.l #4,r5
move.l #10,r2
move.b #'0',r0
_20: lsr.l #1,r1
bcs.b _10
inc.l r0
dbf.l r2,_20
move.b #'.',r0
_10: bsr.l putc
dec.l r4
bne.b _30
move.b #13,r0
bsr.l putc
move.b #10,r0
bsr.l putc
dec.l r3
bne.b _40
movem.l (sp)+,r0-r7
rts.l
;***********************************************************************
out_text:
movem.l r0-r7,-(sp)
move.l r0,r5
_20: move.b (r5)+-,r0
tst.b r0,r0
beq.b _10
bsr.l putc
br.b _20
_10: movem.l (sp)+,r0-r7
rts.l
;***********************************************************************
;*************** start OS dependent functions **************************
;***********************************************************************
getc: movem.l r0-r7,-(sp)
move.b #$3f,m0
move.w #buf,r1
move.w #1,r2
eor.w r3,r3
trap #$21
movem.l (sp)+,r0-r7
movu.bl buf,r0
rts.l
putc: movem.l r0-r7,-(sp)
move.b r0,buf
move.b #$40,m0
move.w #buf,r1
move.w #1,r2
move.w #1,r3
trap #$21
movem.l (sp)+,r0-r7
rts.l
exit: move.w #$4c00,r0
trap #$21
;***********************************************************************
;***************** end OS dependent functions **************************
;***********************************************************************
text1: dc.b 13,10,"illegal input",0
text2: dc.b 13,10,"directly solved",0
text3: dc.b 13,10,"solved with one recursion",0
text4: dc.b 13,10,"not solveable with one recursion",0
even 4
buf: blk.l 1
brett: blk.l 9*9
brett1: blk.l 9*9
Herbert Kleebauer
>
> Herbert, better still here are even some I coudn't solve anyway.
>
> 200030056007010000001600003840000000002000500000000061500003900000040700370090005
> 040000065009020300005100000000500030000639000010008090004006700008040100350000040
> 009700001704800000500060070000300060020000010030009000090030002000008504800001600
> 020000900400506710300000000003085000000174000000390600000000008085901007006000040
> 810000200000007800007000014400090008006050900200070001570000300003400000009000026
> 000109000006040900800000005070050080215000739030010020700000003001070200000804000
> 039007000000500201000090070960000000407000503000000019090020000503008000000400120
> 700605009000800030001000004007000205090000080308000700200000600010009000800506007
> 500200010001900730000000800050020008062039000000004300000000000080467900007300000
> 000023000004000100050084090001070902093006000000010760000000000800000004060000587
> 000042059450090008000000000000004080000000703000836002369200001700000000005001600
> 000000000360000920000010070000000204000036500100025730072809300900000080040000000
> 600400030000001050410800000040350200000700008002060500900000000730500086004000700
> 000300805060000030000050267006100002003405700004008000278000900000001000000000600
> 040080700020000000800030510000208906000009020000500000100000300090406005000050000
> 005100000600003000300000706000030601009050400802090000401000005000500008000007200
> 200000007015000020080200006000000064890000000000050910040815000061030000000006400
Saved it as a.txt and the following solved them all:
for /f %%i in (a.txt) do (
echo %%i|sudo.com
pause)
Herbert Kleebauer
>
> 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.
Herbert Kleebauer
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:
Herbert Kleebauer
> 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
Spam Killer
>... 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
Herbert Kleebauer
>
> 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?
Spam Killer
>
>> 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?
color 1 color 2 color 3 ...
color 4 color 5 color 6 ...
color 7 color 8 color 9 ...
color 1 color 2 color 3 ...
...
in each of the squares.
--
wfz
Terence
The 3x3 subsquares and the rows and the columns are what the oriental
fans call "houses".
Other names are SQUARE, ROW, COLUMN and the 81 items are BOXES.
I uses alternate colours myself, like a chess board, when displaying
sets of possible digits per box in partial solutions.
The preferred oriental way of solving is to use a 3 by 3 dot array in
each BOX to represent possible digits, and crossing a dot (or filling
a tiny circle) if a possibility is eliminated
123
456
789
I still trying to understand Herbert's strange code. It does seem to
be pure X86; possibly 32 bit asm.
I'm really more interested in the algorithm he mentioned (which does
involve guessing when stuck; I'm trying to find rules to get past that
part). My "HARD" examples all need a guess except for one.
Herbert Kleebauer
> I still trying to understand Herbert's strange code. It does seem to
> be pure X86; possibly 32 bit asm.
You again disassembled the decoder and not the program.
The following batch will generate the real (not ascii encoded)
binary which you can disassemble:
@echo off
echo hD1X-s0P_kUHP0UxGWX4ax1y1ieimnfeinklddmemkjanmndnadmndnpbbn>bat.com
echo hhpbbnpljhoxolnhaigidpllnbkdnhlkfhlflefblffahfUebdfahhfkokh>>bat.com
echo wvPp0w@L4k9C5/R/pN0d0uDL47bwo1YiQJEWtbGov5//B6mkuMEo0IL0l/w>>bat.com
echo ef2iC57R/pNEA/jeefHhC5AR/pNEA/juefXgC5ER/phCfDM@m042knfuur9>>bat.com
echo l3LYV5wPajYHk3aZPILM5uqAk3g/XQqHL3wYkRkPKAGPq2f9wNaZc4fXkNa>>bat.com
echo Rg0Hsz/aBcl3QasIP5uD9k3aVCK0AVND7sPLM5uqS0RTNajYHk3aZPILQaN>>bat.com
echo @OEV/L6Da4AuEMai1QVNxak4aJ7ooVVNcXp4bNKWKM5uvR0RoM5uKRVNF@i>>bat.com
echo NBJ6ra4AsEQaN8OUN2OA0b8ShaV@j3AluQM5iCGk3fvUNsu60HgC2aV@c3A>>bat.com
echo VNczT/HM5uQ8k3aVib1AVNUNajYHk3ax@95AluCM5Mat@95AVNzGC0HMKiF>>bat.com
echo RlwbNKda45YaBgNUNajYHk3aZPILMKAzTaN@OEV/LrKaBsn0MKkc2VNu9k4>>bat.com
echo a4nqapP1LMKVEHr7bNKWKM5uKRlQ8MqUDzjNl/xuCMKVPLL0aZsofHUN2iw>>bat.com
echo za4hsapIRFPKVPHr8sNkNaZc6fXUN02C3bNKW5MqU5HkNWPdN4yjNDUMTzz>>bat.com
echo zza45YsPqkaB7m0MKMEajN2P5Mat@t3AVNtak4ah@1LQaN@OUN89wNaB/0S>>bat.com
echo SaN@EVbahIRmbXkaxEVtTVN0fC3aZ/oxsz/axEVcTVN2OA8b8Clat@t3AVN>>bat.com
echo tak4ah@1LQaN@OUN89wNap7@PRaNBmKP/QaN2EUfbNq1IseN@Jrtt7gNDIc>>bat.com
echo dLMKke2VN8/RDyDUNDIMZLMqU5HkNWbfNyGC0HMKi2QVNvCk4bNqW5MKW1T>>bat.com
echo aN2M30bNq1KFkNaBUF7QaN@M41bNq/5FmNahUJYQaN2M39bNq1KVmNaBUFg>>bat.com
echo QaN@M4@bNq/5VoNahUJ7RaN2M3HbNq1KloNaBUFERaN@M4It7QRVMKke2VN>>bat.com
echo 8/RDyDERJMqU5nUN@JLYaBcl7Ras3OKMEWjN2PKMEajN2P5MkqUNcfs4keU>>bat.com
echo Nc@s4at@t3AVNvak4apP1LQaN@OVN2OA0aZf1L/@Aa4humRUN/Rasq2f@aV>>bat.com
echo iHLMKHpdBgBM5u1R0g9M5uuQVN@J6ka45YaBgNUNKW5T5f31AR7M5uUQlum>>bat.com
echo PKMEOqka05hzc@s3YP//3nqB6WNV0dNDMf0UHUN2P5MW1C0o1YiUHEi0/ki>>bat.com
echo 0/EnVMKMEOqks1/HB6G29Y5PgJqNVl57dt5QpF6/Bc/Nd8LNXF6Pt0mQjla>>bat.com
echo RZF5/BckQjlaRZF57rZ5Rc0mPiJ57mJqMp8rQdxaP/oU1ix5RUArPgNLNV8>>bat.com
echo 5PZ0mRdF6OUwaPZ0WQZBKRmBLOjtq3.>>bat.com
bat.com >sudo.com
del bat.com
> I'm really more interested in the algorithm he mentioned (which does
> involve guessing when stuck; I'm trying to find rules to get past that
> part). My "HARD" examples all need a guess except for one.
For each row, column and square you have to check that in this 9
position each digit occurs only once and that it is possible to
insert each 1-9 digit. I use two 9 bit variables for each
position stored in a 32 bit variable. It doesn't matter where
in the 32 bit variable you put this two 9 bit values, I used
bit 25-17 and bit 9-1:
bit 332222 222222111 1 111111 000000000 0
position 109876 543210987 6 543210 987654321 0
000000 xxxxxxxxx 0 000000 yyyyyyyyy 0
If for a position the correct digit is already found (e.g. 2), then
x = 000000000 and y = 000000010
If the digit is not found but can only be 1,2,3 or 7, then
x = 001000111 and y = 000000000
For example, if we have the following values for the 9 postions:
000000 xxxxxxxxx 0 000000 yyyyyyyyy 0
1: 000000 000000000 0 000000 000000001 0
2: 000000 001100110 0 000000 000000000 0
3: 000000 001100110 0 000000 000000000 0
4: 000000 000000000 0 000000 000010000 0
5: 000000 001100110 0 000000 000000000 0
6: 000000 001001101 0 000000 000000000 0
7: 000000 001100110 0 000000 000000000 0
8: 000000 001100110 0 000000 000000000 0
9: 000000 101100110 0 000000 000000000 0
then we calculate the "add" and "or" of these 9 variables.
Then we compare the yyyyyyyyy postion of the "add" and "or"
results: if they are not the same, then in at least two
varibales the same bit in yyyyyyyyy was set which is
illegal.
The yyyyyyyyy position of the "or" result give us all digits
which are already found and the xxxxxxxxx position of the "or"
result give us all digits which can be generated by the not
already solved positions. If we or together this both values
we must get 111111111 or not all digits can be generated
which also would be an error.
Terence
Thanks again Herbert for your explantions.
To be fair, I DID realise Herbert's batch file produced a sudo.com
file which ITSELF started by converting itself from ascii characters
to the real 0-256 binary characters of the machine code.
Then this executed the result in memory and read stdin.
I wrote him to say so, but these crossed I think.
I will try to follow Herbert's algorithm.
I think it has to be same as the human method because it also reaches
a guessing point.
An exhaustive reiteration on oll possibilities would at some point,
have to use a cut and reduce technique on intermediate situations,
which could theoreticaly use a lot of memory to store later more-
complete situations which may or may not be on the route to a
solution.
I have at least one puzzle with more than one solution. Another case
was posted here.
Terence
assembled executable code.
Very interesting, smooth and smart algorithm as coded (in 32-bit
assembler, not 16-bit), but as I suspected, the algorithm tries every
bit possible in order, checks to see if the result is valid over the
rules applied to the 81 boxes and then rejects the new trial or else
saves it and continues. This is exhaustive;Ii'm surprised it doesn't
jam on a false route, with only one saved partial.
I try to fined single possibles, then pairs in the same "house" which
eliminates these bits from the rest of the "house"; then three in a
intersection two "houses", then three plus 1 in a sub-square. There
aren't any more possibilities; but these last two are difficult to
recognise manually. I remain curious as why Herberts routine works on
all puzzles he tessted, without in any way suggesting it's wrong. I
just don't see why..
Herbert Kleebauer
> I worked through a disassembly of Herberts (private language source)
> assembled executable code.
> Very interesting, smooth and smart algorithm as coded (in 32-bit
> assembler, not 16-bit), but as I suspected, the algorithm tries every
> bit possible in order, checks to see if the result is valid over the
> rules applied to the 81 boxes and then rejects the new trial or else
> saves it and continues. This is exhaustive;Ii'm surprised it doesn't
> jam on a false route, with only one saved partial.
I think you misinterpret the algorithm. It does not try all possible values
in an recursive way but does just a linear walk through the array. Each of
the 81 elements has a subset of the digits 1,2,3,4,5,6,7,8,9 attached.
If it is only one digit, then this position is solved. Now, the algorithm
goes through all 81 positions, if the there is only one digit attached
(the position is solved), do nothing, if more digits are attached do:
for any digit attached test, whether this digit is possible in that position
(it is not possible if this digit is already the solution of a position
in the same row, column or square), if yes, do nothing, if no, remove it
from the attached digits for this position. Simple puzzles can be solved this
way (the output of the program is then: directly solved).
If the solution is not found this way, I "guess" the correct digit for
ONE (and only one) position and apply the above algorithm again. Either
this guess was correct, then the solution is found, or the guess was
incorrect, than a contradiction is found and I have to try another guess.
But till now I found no puzzle which couldn't solved with this one guess
(which is a little bit surprising).
Terence
My comment is because I do these steps myself and show the user why,
and the logic (rule) being applied.
In Herbert's interesting code,
There is one "find a single possibility" routine called first and once
again before guessing.
There is a routine to examine if the current array is valid, possible
or impossible.
There is a routine to "find where I can put digit n" but I didn't see
where it checked that, where there were no selected digits within a
set, that that there was only one case of one particular possible
digit, (which Herbert says is present).
It could be he counts singles and recalls the "singles" routine if a
count yield one-any-one only for digit n..
> I think you misinterpret the algorithm. It does not try all possible values
> in an recursive way but does just a linear walk through the array. Each of
> the 81 elements has a subset of the digits 1,2,3,4,5,6,7,8,9 attached.
> If it is only one digit, then this position is solved.
Yes
> Now, the algorithm goes through all 81 positions, if the there is only one digit attached
> (the position is solved), do nothing,
Yes
> if more digits are attached do:
> for any digit attached test, whether this digit is possible in that position
> (it is not possible if this digit is already the solution of a position
> in the same row, column or square), if yes, do nothing, if no, remove it
> from the attached digits for this position.
Yes
> Simple puzzles can be solved this
> way (the output of the program is then: directly solved).
Yes
> If the solution is not found this way, I "guess" the correct digit for
> ONE (and only one) position and apply the above algorithm again. Either
> this guess was correct, then the solution is found, or the guess was
> incorrect, than a contradiction is found and I have to try another guess.
> But till now I found no puzzle which couldn't solved with this one guess
> (which is a little bit surprising).
This is why I don't know why that can always work.
I find that the two rules
1) "any single possibility is part of a solution if the puzzle is
valid".
2) "for each digit 1-9 we must have this digit somewhere in this set-
where is it posible once and once only"
Will solve a lot of puzzles, but I have may many cases where it will
not.
But these are the rules Herbert uses.
But the chance of guessing from a pair is only 50% likely to be the
correct guess.
So I state (well: the SUDOKU site states) that there are 3 more rules
to complete the needed logic.
3) "if there are two pairs of the same possibilities in a set
("house") in the same row or column, remove these possibilities from
the rest of that row or column and also in the sub-square if both
pairs found intersect it".
Obviously both possibilities are present in the same set and only
where found; so they cannot be elswhere.
4) "If three triples are found in the same row or column or sub-
square, remove all other case of the same possibilities form that set
("house"). . Can be 3-3-2 as well. Same concept; only those three can
be there and therfor e not elswhere.
5) "The same, but using three-in-a-row quadruples and one other
identical fousome in the same sub-square, eliminating only from the
rest of the subsquare unless all in the same row or column". Can be
mix of 4, 3 and 2 of same four bits as well. Same argument, but only
applies to a sub-square, if not in the same line set.
This will still not solve ALL puzzles since two pairs of pairs could
be interchanged without the result not being a valid solution, which
is why some contributors gave some examples of multiple solutions.