Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. ;unit SudokuSolve;
  2.  
  3. ;interface
  4.  
  5. ;type
  6. ;   TSudokuBoard=array[0..8,0..8] of byte;//Єшя яюых фы  шуЁ√
  7.  
  8. ;   function CheckSudoku(var Map: TSudokuBoard): boolean;
  9. ;   //тючтЁр∙рхЄ true хёыш яюых ёюёЄртыхэю яЁртшы№эю
  10.  
  11. ;   function Solve(var Map: TSudokuBoard): integer;
  12. ;   //Ёх°рхЄ ╤єфюъє
  13. ;   //Result = 1; - Ёх°хэшх эрщфхэю
  14. ;   //Result = -1; - Єєяшъытр  ъюьсшэрЎш 
  15.  
  16. ;   procedure CopyArray(var Dst: TSudokuBoard;Src: TSudokuBoard);
  17.  
  18. ;implementation
  19.  
  20. ;type
  21. ;   TSudokuPt=record //Єшя Єюўър ё ьшэшьры№э√ь ўшёыюь ърэфшфрЄют
  22. ;       mini,minj,variances: byte;
  23. ;   end;
  24.  
  25. ;var
  26. ;  TempMap: TSudokuBoard;//яюы 
  27. ;  Pt: TSudokuPt;            //Єюўър
  28. ;  i,j: byte;                //ёўхЄўшъш
  29.  
  30.  
  31.  
  32. align 4
  33. CheckSudoku:
  34. pushad
  35. ;function CheckSudoku(var Map: TSudokuBoard): boolean;          ;ърЁЄр т esi!
  36. ;var
  37. ;    i,j,x,y: byte;
  38. ;    Zap: set of byte;
  39. ;begin
  40.  
  41. ;//яЁютхЁ хь ёЄюысЎ√
  42. ; for i:=0 to 8 do
  43. ; begin
  44. ; Zap:=[];
  45. ; for j:=0 to 8 do
  46. ;   if Map[i,j]<>0 then
  47. ;     if Map[i,j] in Zap then
  48. ;     begin
  49. ;       Result:=false;
  50. ;       Exit;
  51. ;       end else
  52. ;       Zap:=Zap+[Map[i,j]];
  53. ; end;
  54.         xor     ecx,ecx
  55.         xor     eax,eax
  56.         xor     edx,edx
  57.         mov     bx,0x0909
  58. .1:     mov     al, byte [esi+ecx]
  59.         test    al,al
  60.         jz      @f
  61.                 btc     dx,ax
  62.                 jc      .ret_false
  63.         @@:
  64.         add     cl,9
  65.         dec     bl
  66.         jnz     .1
  67. ;       test    [flags],1 shl 15
  68. ;       jz      @f
  69. ;       cmp     edx,1022 ;1111111110b
  70. ;       jne     .ret_false
  71. ;@@:
  72.         bt      [flags],15
  73.         jnc     @f
  74.         cmp     dx,1022 ;1111111110
  75.         jne     .ret_false
  76. @@:
  77.         sub     cl,9*9-1
  78.         xor     edx,edx
  79.         mov     bl,9
  80.         dec     bh
  81.         jnz     .1
  82.  
  83.  
  84. ;//яЁютхЁ хь ёЄЁюъш
  85. ; for j:=0 to 8 do
  86. ; begin
  87. ; Zap:=[];
  88. ; for i:=0 to 8 do
  89. ;    if Map[i,j]<>0 then
  90. ;       if Map[i,j] in Zap then
  91. ;       begin
  92. ;       Result:=false;
  93. ;       Exit;
  94. ;       end else
  95. ;       Zap:=Zap+[Map[i,j]]
  96. ; end;
  97.  
  98.         xor     ecx,ecx
  99.         xor     eax,eax
  100.         xor     edx,edx
  101.         mov     bx,0x0909
  102. .2:     mov     al, byte [esi+ecx]
  103.         test    al,al
  104.         jz      @f
  105.                 btc     dx,ax
  106.                 jc      .ret_false
  107.         @@:
  108.         inc     ecx
  109.         dec     bl
  110.         jnz     .2
  111.         bt      [flags],15
  112.         jnc     @f
  113.         cmp     dx,1022 ;1111111110
  114.         jne     .ret_false
  115. @@:
  116.         xor     edx,edx
  117.         mov     bl,9
  118.         dec     bh
  119.         jnz     .2
  120.  
  121. ;//яЁютхЁ хь ёхъЄюЁр
  122. ;for i:=0 to 2 do
  123. ;  for j:=0 to 2 do
  124. ;  begin
  125. ;  zap:=[];
  126. ;  for x:=0 to 2 do
  127. ;     for y:=0 to 2 do
  128. ;     if map[i*3+y,j*3+x]<>0 then
  129. ;     if map[i*3+y,j*3+x] in Zap then
  130. ;     begin
  131. ;     Result:=false;
  132. ;     exit;
  133. ;     end else
  134. ;     Zap:=zap+[map[i*3+y,j*3+x]];
  135. ;  end;
  136. ;Result:=true;
  137. ;end;
  138.         mov     ecx,0x0303 ;ij
  139.         xor     eax,eax
  140.         xor     edx,edx
  141.         mov     ebx,0x0303 ;xy
  142.  
  143. .3:     movzx   eax,ch
  144.         dec     al
  145.         lea     eax,[eax*2+eax]
  146.         add     al,bl           ;i*3+y
  147.         dec al
  148.         mov     edi,eax
  149.         movzx   eax,cl
  150.         dec     al
  151.         lea     eax,[eax*2+eax]
  152.         add     al,bh           ;j*3+x
  153.         dec al
  154.         xchg    eax,edi
  155.         mov     ah,9
  156.         mul     ah
  157.         add     eax,edi         ;i*3+y,j*3+x
  158.         mov     al,[esi+eax]
  159.         test    al,al
  160.         jz      @f
  161.                 btc     dx,ax
  162.                 jc      .ret_false
  163.         @@:
  164.         dec     bl
  165.         jnz     .3
  166.         mov     bl,3
  167.         dec     bh
  168.         jnz     .3
  169.         bt      [flags],15
  170.         jnc     @f
  171.         cmp     dx,1022 ;1111111110
  172.         jne     .ret_false
  173. @@:
  174.         mov     bx,0x0303
  175.         xor     edx,edx
  176.         dec     cl
  177.         jnz     .3
  178.         mov     cl,3
  179.         dec     ch
  180.         jnz     .3
  181. popad
  182. clc
  183. ret
  184. .ret_false:
  185. popad
  186. stc
  187. ret
  188.  
  189. _iRet   dw ?
  190.  
  191. Pt:
  192. .mini db ?
  193. .minj db ?
  194. .variances db ?
  195.  
  196. bFree db ?
  197. nVariances db ?
  198. nMinVariances db ?
  199.  
  200. align 4
  201. FindMinPoint:
  202.         pushad
  203.         mov     [bFree],0
  204.         mov     [nMinVariances],10
  205.         mov     cx,0x0909 ;ij
  206. .1:     movzx   eax,ch
  207.         mov     ah,9
  208.         dec     al
  209.         mul     ah
  210.         add     al,cl
  211.         dec     al
  212.         cmp     byte [esi+eax],0
  213.         je      @f
  214. .11:    dec     cl
  215.         jnz     .1
  216.         mov     cl,9
  217.         dec     ch
  218.         jnz     .1
  219.         jmp     .3
  220.  
  221. @@:     mov     [nVariances],0
  222.         mov     [bFree],1
  223.         mov     ebx,1
  224. .2:     mov     [esi+eax],bl
  225.         call    CheckSudoku
  226.         jc      @f
  227.         inc     [nVariances]
  228. @@:     inc     ebx
  229.         cmp     ebx,9
  230.         jbe     .2
  231.  
  232.         mov     byte [esi+eax],0
  233.         mov     dl,[nVariances]
  234.         cmp     dl,0
  235.         je      .11
  236.         cmp     dl,[nMinVariances]
  237.         jnb     .11
  238.         mov     [Pt.mini],ch
  239.         mov     [Pt.minj],cl
  240.         mov     [Pt.variances],dl
  241.         mov     [nMinVariances],dl
  242.         jmp     .11
  243.  
  244. .3:     cmp     [bFree],1
  245.         jne     @f
  246.         cmp     [nMinVariances],10
  247.         jge     @f
  248.         mov     [_iRet],1
  249.         popad
  250.         ret
  251. @@:     cmp     [bFree],1
  252.         jne     @f
  253.         mov     [_iRet],-1
  254.         popad
  255.         ret
  256. @@:     mov     [_iRet],0
  257.         popad
  258. ret
  259.  
  260.  
  261. ;   //ш∙хЄ Єюўъє ё ьшэшьры№э√ь ўшёыюь ърэфшфрЄют ш чряшёштрхЄ Ёхчєы№ЄрЄ т MinPt
  262. ;   //Result = -1; - эр°ыш, ъєфр ьюцэю яюёЄртшЄ№ ЎшЇЁє
  263. ;   //Result = 1; - ётюсюфэюх ьхёЄю хёЄ№ эр яюых, эю яюёЄртшЄ№ эшъєфр эхы№ч 
  264. ;   //Result = 0; - эхЄ ётюсюфэюую ьхёЄр
  265. ;function FindMinPoint(var MinPt: TSudokuPt;var Map: TSudokuBoard): integer;
  266. ;var
  267. ;nVariances,nMinVariances,variance: byte;
  268. ;bFree: boolean;
  269. ;begin
  270. ;bFree:= false;
  271. ;nMinVariances:=10;
  272. ;for i:=0 to 8 do
  273. ;  for j:=0 to 8 do
  274. ;  begin
  275. ;  if Map[i,j]<>0 then continue;
  276. ;  nVariances := 0;
  277. ;  bFree := true;
  278. ;  for variance:=1 to 9 do
  279. ;   begin
  280. ;     map[i,j]:=variance;
  281. ;     if CheckSudoku(Map) then inc(nVariances);
  282. ;   end;
  283. ;  Map[i,j]:=0;
  284. ;  if nVariances=0 then continue;
  285. ;  if nVariances < nMinVariances then
  286. ;    begin
  287. ;    MinPt.mini:=i;
  288. ;    MInPt.minj:=j;
  289. ;    MinPt.variances:=nVariances;
  290. ;    nMinVariances := nVariances;
  291. ;    end;
  292. ;  end;
  293. ;if (bFree) and (nMinVariances<10) then // эр°ыш, ъєфр ьюцэю яюёЄртшЄ№ ЎшЇЁє
  294. ;  begin
  295. ;  Result:=1;
  296. ;  Exit;
  297. ;  end;
  298. ;if bFree then  // ётюсюфэюх ьхёЄю хёЄ№ эр яюых, эю яюёЄртшЄ№ эшъєфр эхы№ч 
  299. ;   begin
  300. ;   Result:=-1;
  301. ;   exit;
  302. ;   end;
  303. ;result:=0; // эхЄ ётюсюфэюую ьхёЄр
  304. ;end;
  305.  
  306.  
  307.  
  308. ;procedure CopyArray(var Dst: TSudokuBoard;Src: TSudokuBoard);
  309. ;begin
  310. ;for i:=0 to 8 do
  311. ;  for j:=0 to 8 do
  312. ;   Dst[i,j]:=Src[i,j];
  313. ;end;
  314.  
  315. CopyArray:
  316.         push    ecx eax
  317.         xor     ecx,ecx
  318. @@:     mov     al,[esi+ecx]
  319.         mov     [edi+ecx],al
  320.         inc     ecx
  321.         cmp     ecx,9*9
  322.         jb      @b
  323.         pop     eax ecx
  324. ret
  325.  
  326.  
  327.  
  328. align 4
  329. Solve:
  330.         pushad
  331. if DEBUG
  332. dbg_dec esp
  333. dbg_dec ecx
  334. mcall 5,1
  335. endf
  336.         call    FindMinPoint
  337.         cmp     [_iRet],0
  338.         jne     @f
  339.                 mov     [_iRet],1
  340.                 popad
  341.                 ret
  342.         @@:
  343.         cmp     [_iRet],-1
  344.         jne     @f
  345.                 popad
  346.                 ret
  347. @@:
  348.         push    esi edi
  349.         mov     edi,TempMap
  350.         call    CopyArray
  351.         pop     edi esi
  352.         mov     ecx,1
  353.         movzx   eax, byte [Pt.mini]
  354.         dec     al
  355.         mov     ah,9
  356.         mul     ah
  357.         add     al,byte [Pt.minj]
  358.         dec     al
  359. .1:     mov     byte [esi+eax],cl
  360.         call    CheckSudoku
  361.         jnc     @f
  362. .2:     inc     ecx
  363.         cmp     ecx,9
  364.         jbe     .1
  365. ;       jmp     .1
  366. @@:     call    Solve
  367.         cmp     [_iRet],-1
  368.         jne     @f
  369.         push    esi edi
  370.         mov     edi,TempMap
  371.         xchg    esi,edi
  372.         call    CopyArray
  373.         pop     edi esi
  374.         popad
  375.         ret
  376. @@:     cmp     [_iRet],1
  377.         jne     .3
  378.         popad
  379.         ret
  380. .3:     mov     [_iRet],0
  381.         popad
  382. ret
  383.  
  384. ;function Solve(var Map: TSudokuBoard): integer;
  385. ;var
  386. ;  variance: byte;
  387. ;  iRet: integer;
  388. ;begin
  389. ;// ш∙хь ъыхЄъє ё эршьхэ№°шь ўшёыюь ърэфшфрЄют:
  390. ;iRet:=FindMinPoint(Pt,Map);
  391. ;if (iRet = 0) then
  392. ;   begin
  393. ;   result:=1;// Ёх°хэшх эрщфхэю
  394. ;   exit;
  395. ;   end else
  396. ;if (iRet = -1) then // Єєяшъютр  ъюьсшэрЎш 
  397. ;     begin
  398. ;     result:=-1;
  399. ;     exit;
  400. ;     end;
  401.  
  402. ;CopyArray(TempMap,Map); // ёюїЁрэ хь Єю, ўЄю хёЄ№
  403. ;for variance:=1 to 9 do
  404. ;begin
  405. ; Map[pt.mini,pt.minj]:=variance; // я√Єрхьё  ёЄртшЄ№ эр эрщфхээє■ ъыхЄъє ЎшЇЁ√ юЄ 1 фю 9
  406. ; if not CheckSudoku(Map) then continue; // Єръє■ ЎшЇЁє яюёЄртшЄ№ эхы№ч . ┴хЁ╕ь ёыхфє■∙є■.
  407. ; iRet:=Solve(Map); // чряєёърхь ЇєэъЎш■ ЁхъєЁёштэю
  408. ; if iRet=-1 then // Єєяшъютр  ъюьсшэрЎш 
  409. ;  begin
  410. ;  CopyArray(Map,tempmap); // тюёёЄрэртыштрхь ьрёёшт ш схЁ╕ь ёыхфє■∙є■ ЎшЇЁє эр Єю цх ьхёЄю
  411. ;  continue;
  412. ;  end;
  413. ;if iRet=1 then // Ёх°хэшх эрщфхэю
  414. ;  begin
  415. ;  Result:=1;
  416. ;  exit;
  417. ;  end;
  418. ;end;
  419. ;Result:=0;
  420. ;end;
  421.  
  422. ;end.
  423.  
  424.