sudoku breaker-php edition

Deducer class:

  1 php
  2 class  Deducer
  3 {
  4      private   $array ;
  5      public   function  __construct( $array )
  6     { 
  7          $this -> array = array ();
  8          for ( $row = 0 ; $row   9         {
 10              for ( $column = 0 ; $column  11             {
 12                  $this -> array [ $row ][ $column ] = $array [ $row ][ $column ];
 13             }
 14         }
 15        } 
 16      private   function  isFinished()
 17     {
 18          for ( $row = 0 ; $row  19         {
 20              for ( $column = 0 ; $column  21             {
 22                  if ( $this -> array [ $row ][ $column ] == 0 )
 23                 {
 24                      return   false ;
 25                 }
 26             }
 27         }
 28          return   true ;
 29     }
 30      public   function  deduceAll()
 31     {
 32          if ( $this -> isFinished())
 33         {
 34              return ;
 35         }
 36          for ( $row = 0 ; $row  37         {
 38              for ( $column = 0 ; $column  39             {
 40                  if ( $this -> reduceFromOneZone( $this -> array , $row , $column ))
 41                 {
 42                      $this -> deduceAll();
 43                      return ;
 44                 }
 45             }
 46         }
 47          for ( $row = 0 ; $row  48         {
 49              if ( $this -> reduceFromOneRow( $this -> array , $row ))
 50             {
 51                  $this -> deduceAll();
 52                  return ;
 53             }
 54         }
 55          for ( $column = 0 ; $column  56         {
 57              if ( $this -> reduceFromOneColumn( $this -> array , $column ))
 58             {
 59                  $this -> deduceAll();
 60                  return ;
 61             }
 62         }
 63          for ( $row = 0 ; $row  64         {
 65              if ( $this -> reduceFromThreeRows( $this -> array , $row , $row + 2 ))
 66             {
 67                  $this -> deduceAll();
 68                  return ;
 69             }
 70         } 
 71          for ( $column = 0 ; $column  72         {
 73              if ( $this -> reduceFromThreeColumns( $this -> array , $column , $column + 2 ))
 74             {
 75                  $this -> deduceAll();
 76                  return ;
 77             }
 78         }
 79     }
 80      public   function  deduceOnce()
 81     {
 82          for ( $row = 0 ; $row  83         {
 84              for ( $column = 0 ; $column  85             {
 86                  if ( $this -> reduceFromOneZone( $this -> array , $row , $column ))
 87                 {
 88                      return ;
 89                 }
 90             }
 91         }
 92          for ( $row = 0 ; $row  93         {
 94              if ( $this -> reduceFromOneRow( $this -> array , $row ))
 95             {
 96                  return ;
 97             }
 98         }
 99          for ( $column = 0 ; $column 100         {
101              if ( $this -> reduceFromOneColumn( $this -> array , $column ))
102             {
103                  return ;
104             }
105         }
106          for ( $row = 0 ; $row 107         {
108              if ( $this -> reduceFromThreeRows( $this -> array , $row , $row + 2 ))
109             {
110                  return ;
111             }
112         } 
113          for ( $column = 0 ; $column 114         {
115              if ( $this -> reduceFromThreeColumns( $this -> array , $column , $column + 2 ))
116             {
117                  return ;
118             }
119         }
120     }
121      private   function  reduceFromOneZone( & $array , $row , $column )
122     {
123          $startRow = ( floor ( $row / 3 )) * 3 ;
124          $startColumn = ( floor ( $column / 3 )) * 3 ;
125          $unknown = array ();
126          for ( $pointer = 0 ; $pointer 127         {
128              $unknown [ $pointer ] = $pointer + 1 ;
129         }
130          for ( $rowPointer = $startRow ; $rowPointer 131         {
132              for ( $columnPointer = $startColumn ; $columnPointer 133             {
134                  if ( $array [ $rowPointer ][ $columnPointer ] != 0 )
135                 {
136                      $unknown [ $array [ $rowPointer ][ $columnPointer ] - 1 ] = 0 ;
137                 }
138             }
139         }
140          for ( $digit = 0 ; $digit 141         {
142              if ( $unknown [ $digit ] != 0 )
143             {
144                  $number = $unknown [ $digit ];
145                  $posibilities = 0 ;
146                  $rowPosition =- 1 ;
147                  $columnPosition =- 1 ;
148                  for ( $rowPointer = $startRow ; $rowPointer 149                 {
150                      for ( $columnPointer = $startColumn ; $columnPointer 151                     {
152                          if ( $array [ $rowPointer ][ $columnPointer ] == 0 )
153                         {
154                              if ( $this -> isPossibleInThatCellCheckByColumn( $array , $number , $rowPointer , $columnPointer ) && $this -> isPossibleInThatCellCheckByRow( $array , $number , $rowPointer , $columnPointer ))
155                             {
156                                  $rowPosition = $rowPointer ;
157                                  $columnPosition = $columnPointer ;
158                                  $posibilities ++ ;
159                             }
160                         }
161                     }
162                 }
163                  if ( $posibilities == 1 )
164                 {
165                      $array [ $rowPosition ][ $columnPosition ] = $number ;
166                      return   true ;
167                 }
168             }
169         }
170          return   false ;
171     }
172      private   function  reduceFromOneRow( & $array , $row )
173     {
174          $unknown = array ();
175          for ( $column = 0 ; $column 176         {
177              $unknown [ $column ] = $column + 1 ;
178         }
179          for ( $column = 0 ; $column 180         {
181              if ( $array [ $row ][ $column ] != 0 )
182             {
183                  $unknown [ $array [ $row ][ $column ] - 1 ] = 0 ;
184             }
185         }
186          for ( $column = 0 ; $column 187         {
188              if ( $unknown [ $column ] != 0 )
189             {
190                  $number = $unknown [ $column ];
191                  $posibilities = 0 ;
192                  $position =- 1 ;
193                  for ( $pointer = 0 ; $pointer 194                 {
195                      if ( $array [ $row ][ $pointer ] == 0 )
196                     {
197                          if ( $this -> isPossibleInThatCellCheckByColumnAndZone( $array , $number , $row , $pointer ))
198                         {
199                              $position = $pointer ;
200                              $posibilities ++ ;
201                         }
202                     }
203                 }
204                  if ( $posibilities == 1 )
205                 {
206                      $array [ $row ][ $position ] = $number ;
207                      return   true ;
208                 }
209             }
210         }
211          return   false ;
212     }
213      private   function  reduceFromOneColumn( & $array , $column )
214     {
215          $unknown = array ();
216          for ( $row = 0 ; $row 217         {
218              $unknown [ $row ] = $row + 1 ;
219         }
220          for ( $row = 0 ; $row 221         {
222              if ( $array [ $row ][ $column ] != 0 )
223             {
224                  $unknown [ $array [ $row ][ $column ] - 1 ] = 0 ;
225             }
226         }
227          for ( $row = 0 ; $row 228         {
229              if ( $unknown [ $row ] != 0 )
230             {
231                  $number = $unknown [ $row ];
232                  $posibilities = 0 ;
233                  $position =- 1 ;
234                  for ( $pointer = 0 ; $pointer 235                 {
236                      if ( $array [ $pointer ][ $column ] == 0 )
237                     {
238                          if ( $this -> isPossibleInThatCellCheckByRowAndZone( $array , $number , $pointer , $column ))
239                         {
240                              $position = $pointer ;
241                              $posibilities ++ ;
242                         }
243                     }
244                 }
245                  if ( $posibilities == 1 )
246                 {
247                      $array [ $position ][ $column ] = $number ;
248                      return   true ;
249                 }
250             }
251         }
252          return   false ;
253     }
254      private   function  isPossibleInThatCellCheckByRowAndZone( $array , $number , $row , $column )
255     {
256          if ( ! $this -> isPossibleInThatCellCheckByRow( $array , $number , $row , $column ))
257         {
258              return   false ;
259         }
260          else   if ( ! $this -> isPossibleInThatCellCheckByZone( $array , $number , $row , $column ))
261         {
262              return   false ;
263         }
264          else   if ( ! $this -> canBeInThatZoneCheckByColumn( $array , $number , $row , $column ))
265         {
266              return   false ;
267         }
268          else
269         {
270              return   true ;
271         }
272     }
273      private   function  isPossibleInThatCellCheckByColumnAndZone( $array , $number , $row , $column )
274     {
275          if ( ! $this -> isPossibleInThatCellCheckByColumn( $array , $number , $row , $column ))
276         {
277              return   false ;
278         }
279          else   if ( ! $this -> isPossibleInThatCellCheckByZone( $array , $number , $row , $column ))
280         {
281              return   false ;
282         }
283          else   if ( ! $this -> canBeInThatZoneCheckByRow( $array , $number , $row , $column ))
284         {
285              return   false ;
286         }
287          else
288         {
289              return   true ;
290         }
291     }
292      private   function  canBeInThatZoneCheckByRow( $array , $number , $row , $column )
293     {    
294          $startRow = ( floor ( $row / 3 )) * 3 ;
295          $startColumn = ( floor ( $column / 3 )) * 3 ;
296          for ( $rowPointer = $startRow ; $rowPointer 297         {
298              if ( $rowPointer != $row )
299             {
300                  if ( ! $this -> isPossibleInThatCellCheckByRow( $array , $number , $rowPointer , $column ))
301                 {
302                      continue ;
303                 }
304                  $canItBe = true ;
305                  for ( $columnPointer = 0 ; $columnPointer 306                 {
307                      if ( $columnPointer $startColumn + 2 )
308                     {
309                          if ( $array [ $rowPointer ][ $columnPointer ] == 0 )
310                         {
311                              if ( $this -> isPossibleInThatCellCheckByColumn( $array , $number , $rowPointer , $columnPointer ) && $this -> isPossibleInThatCellCheckByZone( $array , $number , $rowPointer , $columnPointer ))
312                             {
313                                  $canItBe = false ;
314                             }
315                         }
316                     }
317                 }
318                  if ( $canItBe )
319                 {
320                      return   false ;
321                 }
322             }
323         }
324          return   true ;
325     }
326      private   function  canBeInThatZoneCheckByColumn( $array , $number , $row , $column )
327     {    
328          $startRow = ( floor ( $row / 3 )) * 3 ;
329          $startColumn = ( floor ( $column / 3 )) * 3 ;
330          for ( $columnPointer = $startColumn ; $columnPointer 331         {
332              if ( $columnPointer != $column )
333             {
334                  if ( ! $this -> isPossibleInThatCellCheckByColumn( $array , $number , $row , $columnPointer ))
335                 {
336                      continue ;
337                 }
338                  $canItBe = true ;
339                  for ( $rowPointer = 0 ; $rowPointer 340                 {
341                      if ( $rowPointer $startRow + 2 )
342                     {
343                          if ( $array [ $rowPointer ][ $columnPointer ] == 0 )
344                         {
345                              if ( $this -> isPossibleInThatCellCheckByRow( $array , $number , $rowPointer , $columnPointer ) && $this -> isPossibleInThatCellCheckByZone( $array , $number , $rowPointer , $columnPointer ))
346                             {
347                                  $canItBe = false ;
348                             }
349                         }
350                     }
351                 }
352                  if ( $canItBe )
353                 {
354                      return   false ;
355                 }
356             }
357         }
358          return   true ;
359     }
360      private   function  isPossibleInThatCellCheckByZone( $array , $number , $row , $column )
361     {
362          $startRow = ( floor ( $row / 3 )) * 3 ;
363          $startColumn = ( floor ( $column / 3 )) * 3 ;
364          for ( $rowPointer = $startRow ; $rowPointer 365         {
366              for ( $columnPointer = $startColumn ; $columnPointer 367             {
368                  if ( $array [ $rowPointer ][ $columnPointer ] == $number )
369                 {
370                      return   false ;
371                 }
372             }
373         }
374          return   true ;
375     }
376      private   function  reduceFromThreeColumns( & $array , $firstColumn , $lastColumn )
377     {
378          $numberAndCount = array ();
379          $numberAndPosition = array ();
380          for ( $row = 0 ; $row 381         {
382              $numberAndCount [ $row ][ 0 ] = $row + 1 ;
383              $numberAndCount [ $row ][ 1 ] = 0 ;
384         }
385          for ( $row = 0 ; $row 386         {
387              for ( $column = 0 ; $column 388             {
389                  $numberAndPosition [ $row ][ $column ] = 0 ;
390             }
391         }
392          for ( $column = $firstColumn ; $column 393         {
394              for ( $row = 0 ; $row 395             {
396                  if ( $array [ $row ][ $column ] != 0 )
397                 {
398                      $numberAndCount [ $array [ $row ][ $column ] - 1 ][ 1 ] ++ ;
399                      $numberAndPosition [ 9 * ( $column % 3 ) + $row ][ 0 ] = $array [ $row ][ $column ];
400                      $numberAndPosition [ 9 * ( $column % 3 ) + $row ][ 1 ] = $row ;
401                      $numberAndPosition [ 9 * ( $column % 3 ) + $row ][ 2 ] = $column ;
402                 }
403             }
404         }
405          for ( $row = 0 ; $row 406         {
407              if ( $numberAndCount [ $row ][ 1 ] == 2 )
408             {
409                  $number = $numberAndCount [ $row ][ 0 ];
410                  $pointer = 0 ;
411                  $firstAppearanceRowPosition =- 1 ;
412                  $firstAppearanceColumnPosition =- 1 ;
413                  $secondAppearanceRowPosition =- 1 ;
414                  $secondAppearanceColumnPosition =- 1 ;
415                  while ( $pointer 416                 {
417                      if ( $numberAndPosition [ $pointer ][ 0 ] == $number )
418                     {
419                          $firstAppearanceRowPosition = $numberAndPosition [ $pointer ][ 1 ];
420                          $firstAppearanceColumnPosition = $numberAndPosition [ $pointer ][ 2 ];
421                          $pointer ++ ;
422                          break ;
423                     }
424                      else
425                     {    
426                          $pointer ++ ;
427                     }
428                 }
429                  while ( $pointer 430                 {
431                      if ( $numberAndPosition [ $pointer ][ 0 ] == $number )
432                     {
433                          $secondAppearanceRowPosition = $numberAndPosition [ $pointer ][ 1 ];
434                          $secondAppearanceColumnPosition = $numberAndPosition [ $pointer ][ 2 ];
435                          break ;
436                     }
437                      else
438                     {
439                          $pointer ++ ;
440                     }
441                 }
442                  $thirdAppearanceColumnPosition = 3 * ( floor ( $firstAppearanceColumnPosition / 3 )) + 3 - $firstAppearanceColumnPosition % 3 - $secondAppearanceColumnPosition % 3 ;
443                  $thirdAppearanceRowStartPosition = ( 3 - ( floor ( $firstAppearanceRowPosition / 3 )) - ( floor ( $secondAppearanceRowPosition / 3 ))) * 3 ;
444                  $posibilities = 0 ;
445                  $thirdAppearanceRowPosition =- 1 ;
446                  for ( $indicator = $thirdAppearanceRowStartPosition ; $indicator 447                 {
448                      if ( $array [ $indicator ][ $thirdAppearanceColumnPosition ] == 0 )
449                     {
450                          if ( $this -> isPossibleInThatCellCheckByRow( $array , $number , $indicator , $thirdAppearanceColumnPosition ))
451                         {
452                              $thirdAppearanceRowPosition = $indicator ;
453                              $posibilities ++ ;
454                         }
455                     }
456                 }
457                  if ( $posibilities == 1 )
458                 {    
459                      $array [ $thirdAppearanceRowPosition ][ $thirdAppearanceColumnPosition ] = $number ;
460                      return   true ;
461                 }
462             }
463         }
464          return   false ;
465     }
466      private   function  reduceFromThreeRows( & $array , $firstRow , $lastRow )
467     {
468          $numberAndCount = array ();
469          $numberAndPosition = array ();
470          for ( $column = 0 ; $column 471         {
472              $numberAndCount [ 0 ][ $column ] = $column + 1 ;
473              $numberAndCount [ 1 ][ $column ] = 0 ;
474         }
475          for ( $row = 0 ; $row 476         {
477              for ( $column = 0 ; $column 478             {
479                  $numberAndPosition [ $row ][ $column ] = 0 ;
480             }
481         }
482          for ( $row = $firstRow ; $row 483         {
484              for ( $column = 0 ; $column 485             {
486                  if ( $array [ $row ][ $column ] != 0 )
487                 {
488                      $numberAndCount [ 1 ][ $array [ $row ][ $column ] - 1 ] ++ ;
489                      $numberAndPosition [ 0 ][ 9 * ( $row % 3 ) + $column ] = $array [ $row ][ $column ];
490                      $numberAndPosition [ 1 ][ 9 * ( $row % 3 ) + $column ] = $row ;
491                      $numberAndPosition [ 2 ][ 9 * ( $row % 3 ) + $column ] = $column ;
492                 }
493             }
494         }
495          for ( $column = 0 ; $column 496         {
497              if ( $numberAndCount [ 1 ][ $column ] == 2 )
498             {
499                  $number = $numberAndCount [ 0 ][ $column ];
500                  $pointer = 0 ;
501                  $firstAppearanceRowPosition =- 1 ;
502                  $firstAppearanceColumnPosition =- 1 ;
503                  $secondAppearanceRowPosition =- 1 ;
504                  $secondAppearanceColumnPosition =- 1 ;
505                  while ( $pointer 506                 {
507                      if ( $numberAndPosition [ 0 ][ $pointer ] == $number )
508                     {
509                          $firstAppearanceRowPosition = $numberAndPosition [ 1 ][ $pointer ];
510                          $firstAppearanceColumnPosition = $numberAndPosition [ 2 ][ $pointer ];
511                          $pointer ++ ;
512                          break ;
513                     }
514                      else
515                     {    
516                          $pointer ++ ;
517                     }
518                 }
519                  while ( $pointer 520                 {
521                      if ( $numberAndPosition [ 0 ][ $pointer ] == $number )
522                     {
523                          $secondAppearanceRowPosition = $numberAndPosition [ 1 ][ $pointer ];
524                          $secondAppearanceColumnPosition = $numberAndPosition [ 2 ][ $pointer ];
525                          break ;
526                     }
527                      else
528                     {
529                          $pointer ++ ;
530                     }
531                 }
532                  $thirdAppearanceRowPosition = 3 * ( floor ( $firstAppearanceRowPosition / 3 )) + 3 - $firstAppearanceRowPosition % 3 - $secondAppearanceRowPosition % 3 ;
533                  $thirdAppearanceColumnStartPosition = ( 3 - ( floor ( $firstAppearanceColumnPosition / 3 )) - ( floor ( $secondAppearanceColumnPosition / 3 ))) * 3 ;
534