sudoku.asm

数独解答程序汇编源码

;Sudoku Puzzle Solver
;Usage: sudoku.com < filename.puz

;The input consists of nine lines. Each line contains only the ASCII
;characters 1 through 9, "." and space; and is terminated with a carriage
;return and line feed (in that order). The "." indicates an empty cell.
;One space character separates each printable character.

;For example, the above puzzle would have this input:
;4 3 . . . . . 8 .<cr><lf>
;9 7 8 . . . . 6 5<cr><lf>
;. . . 8 6 9 . . 3<cr><lf>
;. . 5 . . 4 6 . .<cr><lf>
;. . 1 9 5 8 3 . .<cr><lf>
;. . 3 2 . . 9 . .<cr><lf>
;5 . . 1 7 3 . . .<cr><lf>
;8 6 . . . . 5 3 1<cr><lf>
;. 1 . . . . . 4 2<cr><lf>

	org	100h		;assume bx=0, ch=0, si=100h
	mov	ah,3Fh		;ah=3Fh - read
	mov	dx,2EFFh	;dh='.', dl=-1
	mov	bp,dx		;bp=dx - offset of puzzle array 
L10:
	mov	cl,171		;number of bytes to read/write
	int	21h		;read/write/exit
	inc	bx		;bx=1 - handle to stdout
L20:	
	mov	[si+bp],al	;make trial entry with digit
	pusha			;save digit and index of cell
L30:
	dec	si		;next cell
	js	L10		;jump if puzzle solved
	cmp	[si+bp],dh	;[si+2EFF]='.' ?
	jnz	L30		;loop while cell is not empty
	mov	ax,4031h	;ah=40h - write, al='1' / 40h - inc ax
L40:
	cmp	al,3Ah
	jz	L70		;jump if al>'9'
	mov	cl,171		;size of puzzle array
	mov	di,dx		;di=dx - offset of puzzle array 
L50:				;search for cell contains the digit in al with
	repnz	scasb		;identical row or column or 3x3 region coordinates
	jnz	L20		;jump if digit in al is not already used
	pusha			;save digit and index of cell
	xchg	ax,si		;al=si&00FF - index of first cell
L60:
	aam	19		;ah=al/19 - row, al=al%19 - column
	imul	bp,ax,11	;ah/3=(ah*11)>>5, al/6=(al*11)>>6
	or	bp,9F3Fh	;bp=1rr11111cc111111 where rr=row/3, cc=column/6
	xor	bx,bp		;compare 3x3 region coordinates of two cells
	xchg	ax,di		;al=di&00FF - index of second cell
	js	L60		;loop 2 times
	xor	ax,di		;compare row and column of two cells
	mul	ah		;set al=0 if al=0 or ah=0
	cmp	al,1		;set cf=1 if al=0 (rows or columns are equal)
	dec	bx		;set zf=1 if bx=1 (3x3 region coordinates are equal)
L70:	
	popa			;restore digit and index of cell
	jnbe	L50		;jump if cf=0 and zf=0 
	mov	[si+bp],dh	;undo trial entry
	jmp	L40-1		;next digit