Subversion Repositories Kolibri OS

;unit SudokuSolve;

;interface

;type

;   TSudokuBoard=array[0..8,0..8] of byte;//òèï ïîëå äëÿ èãðû

;   function CheckSudoku(var Map: TSudokuBoard): boolean;

;   //âîçâðàùàåò true åñëè ïîëå ñîñòàâëåíî ïðàâèëüíî

;   function Solve(var Map: TSudokuBoard): integer;

;   //ðåøàåò Ñóäîêó

;   //Result = 1; - ðåøåíèå íàéäåíî

;   //Result = -1; - òóïèêëâàÿ êîìáèíàöèÿ

;   procedure CopyArray(var Dst: TSudokuBoard;Src: TSudokuBoard);

;implementation

;type

;   TSudokuPt=record //òèï òî÷êà ñ ìèíèìàëüíûì ÷èñëîì êàíäèäàòîâ

;       mini,minj,variances: byte;

;   end;

;var

;  TempMap: TSudokuBoard;//ïîëÿ

;  Pt: TSudokuPt;            //òî÷êà

;  i,j: byte;                //ñ÷åò÷èêè

align 4

CheckSudoku:

pushad

;function CheckSudoku(var Map: TSudokuBoard): boolean;		;êàðòà â esi!

;var

;    i,j,x,y: byte;

;    Zap: set of byte;

;begin

;//ïðîâåðÿåì ñòîëáöû

; for i:=0 to 8 do

; begin

; Zap:=[];

; for j:=0 to 8 do

;   if Map[i,j]<>0 then

;     if Map[i,j] in Zap then

;     begin

;       Result:=false;

;       Exit;

;       end else

;       Zap:=Zap+[Map[i,j]];

; end;

	xor	ecx,ecx

	xor	eax,eax

	xor	edx,edx

	mov	bx,0x0909

.1:	mov	al, byte [esi+ecx]

	test	al,al

	jz	@f

		btc	dx,ax

		jc	.ret_false

	@@:

	add	cl,9

	dec	bl

	jnz	.1

;	test	[flags],1 shl 15

;	jz	@f

;	cmp	edx,1022 ;1111111110b

;	jne	.ret_false

;@@:

	bt	[flags],15

	jnc	@f

	cmp	dx,1022 ;1111111110

	jne	.ret_false

@@:

	sub	cl,9*9-1

	xor	edx,edx

	mov	bl,9

	dec	bh

	jnz	.1

;//ïðîâåðÿåì ñòðîêè

; for j:=0 to 8 do

; begin

; Zap:=[];

; for i:=0 to 8 do

;    if Map[i,j]<>0 then

;       if Map[i,j] in Zap then

;       begin

;       Result:=false;

;       Exit;

;       end else

;       Zap:=Zap+[Map[i,j]]

; end;

	xor	ecx,ecx

	xor	eax,eax

	xor	edx,edx

	mov	bx,0x0909

.2:	mov	al, byte [esi+ecx]

	test	al,al

	jz	@f

		btc	dx,ax

		jc	.ret_false

	@@:

	inc	ecx

	dec	bl

	jnz	.2

	bt	[flags],15

	jnc	@f

	cmp	dx,1022 ;1111111110

	jne	.ret_false

@@:

	xor	edx,edx

	mov	bl,9

	dec	bh

	jnz	.2

;//ïðîâåðÿåì ñåêòîðà

;for i:=0 to 2 do

;  for j:=0 to 2 do

;  begin

;  zap:=[];

;  for x:=0 to 2 do

;     for y:=0 to 2 do

;     if map[i*3+y,j*3+x]<>0 then

;     if map[i*3+y,j*3+x] in Zap then

;     begin

;     Result:=false;

;     exit;

;     end else

;     Zap:=zap+[map[i*3+y,j*3+x]];

;  end;

;Result:=true;

;end;

	mov	ecx,0x0303 ;ij

	xor	eax,eax

	xor	edx,edx

	mov	ebx,0x0303 ;xy

.3:	movzx	eax,ch

	dec	al

	lea	eax,[eax*2+eax]

	add	al,bl		;i*3+y

	dec al

	mov	edi,eax

	movzx	eax,cl

	dec	al

	lea	eax,[eax*2+eax]

	add	al,bh		;j*3+x

	dec al

	xchg	eax,edi

	mov	ah,9

	mul	ah

	add	eax,edi		;i*3+y,j*3+x

	mov	al,[esi+eax]

	test	al,al

	jz	@f

		btc	dx,ax

		jc	.ret_false

	@@:

	dec	bl

	jnz	.3

	mov	bl,3

	dec	bh

	jnz	.3

	bt	[flags],15

	jnc	@f

	cmp	dx,1022 ;1111111110

	jne	.ret_false

@@:

	mov	bx,0x0303

	xor	edx,edx

	dec	cl

	jnz	.3

	mov	cl,3

	dec	ch

	jnz	.3

popad

clc

ret

.ret_false:

popad

stc

ret

_iRet	dw ?

Pt:

.mini db ?

.minj db ?

.variances db ?

bFree db ?

nVariances db ?

nMinVariances db ?

align 4

FindMinPoint:

	pushad

	mov	[bFree],0

	mov	[nMinVariances],10

	mov	cx,0x0909 ;ij

.1:	movzx	eax,ch

	mov	ah,9

	dec	al

	mul	ah

	add	al,cl

	dec	al

	cmp	byte [esi+eax],0

	je	@f

.11:	dec	cl

	jnz	.1

	mov	cl,9

	dec	ch

	jnz	.1

	jmp	.3

@@:	mov	[nVariances],0

	mov	[bFree],1

	mov	ebx,1

.2:	mov	[esi+eax],bl

	call	CheckSudoku

	jc	@f

	inc	[nVariances]

@@:	inc	ebx

	cmp	ebx,9

	jbe	.2

	mov	byte [esi+eax],0

	mov	dl,[nVariances]

	cmp	dl,0

	je	.11

	cmp	dl,[nMinVariances]

	jnb	.11

	mov	[Pt.mini],ch

	mov	[Pt.minj],cl

	mov	[Pt.variances],dl

	mov	[nMinVariances],dl

	jmp	.11

.3:	cmp	[bFree],1

	jne	@f

	cmp	[nMinVariances],10

	jge	@f

	mov	[_iRet],1

	popad

	ret

@@:	cmp	[bFree],1

	jne	@f

	mov	[_iRet],-1

	popad

	ret

@@:	mov	[_iRet],0

	popad

ret

;   //èùåò òî÷êó ñ ìèíèìàëüíûì ÷èñëîì êàíäèäàòîâ è çàïèñèâàåò ðåçóëüòàò â MinPt

;   //Result = -1; - íàøëè, êóäà ìîæíî ïîñòàâèòü öèôðó

;   //Result = 1; - ñâîáîäíîå ìåñòî åñòü íà ïîëå, íî ïîñòàâèòü íèêóäà íåëüçÿ

;   //Result = 0; - íåò ñâîáîäíîãî ìåñòà

;function FindMinPoint(var MinPt: TSudokuPt;var Map: TSudokuBoard): integer;

;var

;nVariances,nMinVariances,variance: byte;

;bFree: boolean;

;begin

;bFree:= false;

;nMinVariances:=10;

;for i:=0 to 8 do

;  for j:=0 to 8 do

;  begin

;  if Map[i,j]<>0 then continue;

;  nVariances := 0;

;  bFree := true;

;  for variance:=1 to 9 do

;   begin

;     map[i,j]:=variance;

;     if CheckSudoku(Map) then inc(nVariances);

;   end;

;  Map[i,j]:=0;

;  if nVariances=0 then continue;

;  if nVariances < nMinVariances then

;    begin

;    MinPt.mini:=i;

;    MInPt.minj:=j;

;    MinPt.variances:=nVariances;

;    nMinVariances := nVariances;

;    end;

;  end;

;if (bFree) and (nMinVariances<10) then // íàøëè, êóäà ìîæíî ïîñòàâèòü öèôðó

;  begin

;  Result:=1;

;  Exit;

;  end;

;if bFree then  // ñâîáîäíîå ìåñòî åñòü íà ïîëå, íî ïîñòàâèòü íèêóäà íåëüçÿ

;   begin

;   Result:=-1;

;   exit;

;   end;

;result:=0; // íåò ñâîáîäíîãî ìåñòà

;end;

;procedure CopyArray(var Dst: TSudokuBoard;Src: TSudokuBoard);

;begin

;for i:=0 to 8 do

;  for j:=0 to 8 do

;   Dst[i,j]:=Src[i,j];

;end;

CopyArray:

	push	ecx eax

	xor	ecx,ecx

@@:	mov	al,[esi+ecx]

	mov	[edi+ecx],al

	inc	ecx

	cmp	ecx,9*9

	jb	@b

	pop	eax ecx

ret

align 4

Solve:

	pushad

if DEBUG

dbg_dec esp

dbg_dec ecx

mcall 5,1

endf

	call	FindMinPoint

	cmp	[_iRet],0

	jne	@f

		mov	[_iRet],1

		popad

		ret

	@@:

	cmp	[_iRet],-1

	jne	@f

		popad

		ret

@@:

	push	esi edi

	mov	edi,TempMap

	call	CopyArray

	pop	edi esi

	mov	ecx,1

	movzx	eax, byte [Pt.mini]

	dec	al

	mov	ah,9

	mul	ah

	add	al,byte [Pt.minj]

	dec	al

.1:	mov	byte [esi+eax],cl

	call	CheckSudoku

	jnc	@f

.2:	inc	ecx

	cmp	ecx,9

	jbe	.1

;	jmp	.1

@@:	call	Solve

	cmp	[_iRet],-1

	jne	@f

	push	esi edi

	mov	edi,TempMap

	xchg	esi,edi

	call	CopyArray

	pop	edi esi

	popad

	ret

@@:	cmp	[_iRet],1

	jne	.3

	popad

	ret

.3:	mov	[_iRet],0

	popad

ret

;function Solve(var Map: TSudokuBoard): integer;

;var

;  variance: byte;

;  iRet: integer;

;begin

;// èùåì êëåòêó ñ íàèìåíüøèì ÷èñëîì êàíäèäàòîâ:

;iRet:=FindMinPoint(Pt,Map);

;if (iRet = 0) then

;   begin

;   result:=1;// ðåøåíèå íàéäåíî

;   exit;

;   end else

;if (iRet = -1) then // òóïèêîâàÿ êîìáèíàöèÿ

;     begin

;     result:=-1;

;     exit;

;     end;

;CopyArray(TempMap,Map); // ñîõðàíÿåì òî, ÷òî åñòü

;for variance:=1 to 9 do

;begin

; Map[pt.mini,pt.minj]:=variance; // ïûòàåìñÿ ñòàâèòü íà íàéäåííóþ êëåòêó öèôðû îò 1 äî 9

; if not CheckSudoku(Map) then continue; // òàêóþ öèôðó ïîñòàâèòü íåëüçÿ. Áåð¸ì ñëåäóþùóþ.

; iRet:=Solve(Map); // çàïóñêàåì ôóíêöèþ ðåêóðñèâíî

; if iRet=-1 then // òóïèêîâàÿ êîìáèíàöèÿ

;  begin

;  CopyArray(Map,tempmap); // âîññòàíàâëèâàåì ìàññèâ è áåð¸ì ñëåäóþùóþ öèôðó íà òî æå ìåñòî

;  continue;

;  end;

;if iRet=1 then // ðåøåíèå íàéäåíî

;  begin

;  Result:=1;

;  exit;

;  end;

;end;

;Result:=0;

;end;

;end.