<?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();
    }
}