| 0,0 → 1,423 |
|---|
| ;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. |
| |