Алгоритмы решения Судоку

  • Published on
    22-May-2015

  • View
    560

  • Download
    0

Embed Size (px)

DESCRIPTION

21 2009

Transcript

<ul><li><p> (Constraint Satisfaction Problem - CSP) :</p><p> a X1 , X2,,Xn. C1,C2,,Cm.</p><p> Xi Di . .</p></li><li><p> , , .</p><p> , , CSP , .</p><p> CSP .</p></li><li><p> , - .</p></li><li><p> , 99 . 81 (), . :9 9 9 33 (box)</p><p> , box, . c(_ ; _ ), .. c(1;1)- .</p></li><li><p> 2 : ( 99, ); , ;</p></li><li><p> : ; ; ; ; n-m, n ( n=81 ), m , .</p></li><li><p> - CSP , .. .</p><p> O(dn-m), d- .</p><p> :n!*dn . .</p></li><li><p> .</p><p> : , , , .</p><p>: , . .</p></li><li><p> : ? ? - , ?</p></li><li><p> , :</p><p> (Minimum Remaining Values - MRV); ;</p><p> MRV 300-3000 , .</p></li><li><p> MRV .</p></li><li><p> :</p><p> .</p><p> ( -Maintaining Arc Consistency-MAC)</p></li><li><p> : ; ;</p><p> X- , X .</p><p> , .</p></li><li><p> J.F.Crook</p><p> : m {1,2,,9}, 2</p></li><li><p> 1 ( ). X - . X , X, , .</p><p> 2 ( ). , . </p></li><li><p> : , . box 2- { [_] [ ] }. </p><p>, .</p></li><li><p> : 1 c(2,3) ; 9 (2,6). :{[1,2,6],[c(1,7),c(1,9),c(2,9)]} : 8 c(1,8). 9 : 7 c(5,9). 5 (4,7) ; 3 (2,7) ; 5 (3,8). : { [2,3,6] , [c(3,4), c(8,4), c(9,4)] }: [1,9] 4 5 box, . { [2,8] , [c(3,3), c(4,3)] } 3 : box 7 : { [3,4,5,9] ,[c(7,1), c(7,2), c(8,3), c(9,3)] } ; { [3,4], [c(8,3),c(8,8)] } 8 ; { [2,7], [c(9,1), c(9,2)] } 9 { [2,6], [c(8,4), c(8,6)] } 8 box 8. 7 (8,7) ;8 (8,1) ; 3 (9,4). { [4,5], [c(9,3), c(9,5)] } 6 (9,7) 9 (9,8). .</p></li><li><p> , .</p><p> , .</p><p> .</p></li></ul>

Recommended

View more >