Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- <?php
- // mem max usage by cell (bytes) : 4(1+size-1) = 4 size
- // - - - - table : size*size*4size = 4size^3 bytes
- // size = 9 => table = 4*9^3 = 2916 bytes ~ 3 Ko : acceptable
- class Cell
- {
- public $value = 0;
- public $imp_values = array();
- }
- class Sudoku
- {
- private $grid = array();
- private $cells = array();
- private $size = 0;
- private $sqrtsize = 0;
- private $lastsolved;
- public function cell($x, $y)
- {
- $i = ($y<<$this->size) + $x;
- return &$this->cells[$i];
- }
- private function generate_cells()
- {
- for($x = 0; $x < $this->size; $x++) for($y = 0; $y < $this->size; $y++)
- {
- $i = ($y<<$this->size) + $x;
- $this->cells[$i] = new Cell();
- $this->cells[$i]->value = $this->grid[$x][$y];
- }
- }
- // manage exclusions implied by the presence of a value
- private function exclude_value($vx, $vy, $value)
- {
- if($value < 1 || $value > 9) return;
- // line
- for($x = 0; $x < $this->size; $x++)
- {
- $cell = $this->cell($x, $vy);
- if(!in_array($value, $cell->imp_values) $cell->imp_values[] = $value;
- }
- // column
- for($y = 0; $y < $this->size; $y++)
- {
- $cell = $this->cell($vx, $y);
- if(!in_array($value, $cell->imp_values) $cell->imp_values[] = $value;
- }
- // big cells
- $cell_x = ($vx - ($vx % $this->sqrtsize)) / $this->sqrtsize;
- $cell_y = ($vy - ($vy % $this->sqrtsize)) / $this->sqrtsize;
- for($x = $cell_x; $x < $this->sqrtsize+$cell_x; $x++) for($y = $cell_y; $y < $this->sqrtsize+$cell_y; $y++)
- {
- $cell = $this->cell($x, $y);
- if(!in_array($value, $cell->imp_values) $cell->imp_values[] = $value;
- }
- }
- public function __construct($grid)
- {
- $this->size = sizeof($grid);
- $this->sqrtsize = sqrt($this->size);
- $this->grid = $grid;
- $this->check();
- $this->generate_cells();
- }
- public function check()
- {
- // check grid :
- for($i = 0; $i < $this->size; $i++) if(sizeof($this->grid[$i]) != $size) return false;
- }
- private function cansolve()
- {
- $sum = 0;
- for($i = 0; $i<$this->size*$this->size; $i++) $sum += $this->cells[$i];
- if($sum == $this->lastsolvedsum) return false;
- }
- // 1 try
- private function trysolve()
- {
- // check impossible values and deduce solutions
- // check columns and lines !
- for($x = 0; $x < $this->size; $x++) for($y = 0; $y < $this->size; $y++)
- {
- $cell = $this->cell($x, $y);
- if($cell->value) $this->exclude_value($x, $y, $cell->value);
- }
- for($i = 0; $i<$this->size*$this->size; $i++)
- {
- $sum = array_sum($this->cells[$i]->imp_values);
- $remaining = $this->size*$this->size - $sum;
- if($remaining <= $this->size)
- {
- $this->cells[$i]->value = $remaining;
- }
- }
- }
- // try to solve while we can find new values.
- public function solve()
- {
- while($this->cansolve()) $this->trysolve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement