sudoku breaker-php edition
- WBOY原创
- 2016-06-23 14:35:46802浏览
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