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