Sudoku resolver and generator

Sudoku.php

<?php

namespace Sudoku;

/**
 * Class to resolve and generate sudoku grids
 */
class Sudoku
{
    /** Grid size */
    const GRID_SIZE = 9;

    /** @var array */
    protected $grid;

    /**
     * @param array|null $grid
     */
    public function __construct(array $grid = null)
    {
        if (null === $grid) {
            $this->grid = array_fill(0, self::GRID_SIZE * self::GRID_SIZE, null);
        } else {
            $this->grid = $grid;
        }
    }

    /**
     * Solve the current sudoku
     */
    public function solve()
    {
        $path = [];
        $step = 0;

        while (false !== $index = $this->getCandidateCell($this->grid)) {
            $exclude = isset($path[$step - 1]['tries']) ? $path[$step - 1]['tries'] : [];
            $values = $this->getValidValues($index, $exclude);

            if (count($values) === 0) {
                $try = array_pop($path);
                $step--;
                $this->grid[$try['index']] = null;
            } else {
                shuffle($values);
                $value = reset($values);
                $this->grid[$index] = $value;
                $path[$step]['index'] = $index;
                if ($step > 0) {
                    $path[$step - 1]['tries'][] = $this->grid[$index];
                }
                $step++;
            }
        }
    }

    /**
     * Generate an uncomplete grid
     */
    public function generateUncompleteGrid($difficulty)
    {
        $time = microtime(true);
        $this->solve();
        $fullResolveTime = microtime(true) - $time;

        do {
            $filteredGrid = array_keys(array_filter($this->grid));
            $suggestion = $filteredGrid[rand(0, (count($filteredGrid) - 1))];

            $this->grid[$suggestion] = null;
            $finalGrid = new Sudoku($this->getGrid());
            $time = microtime(true);
            $finalGrid->solve();
            $finalResolveTime = microtime(true) - $time;
        } while ($finalResolveTime < ($difficulty * $fullResolveTime));
    }

    /**
     * Get the current grid
     *
     * @return array
     */
    public function getGrid()
    {
        return $this->grid;
    }

    /**
     * Get the row number for the given index
     *
     * @param integer $index Item index
     *
     * @return integer
     */
    protected function getRow($index)
    {
        return (int) floor($index / self::GRID_SIZE);
    }

    /**
     * Get the column number for the given index
     *
     * @param integer $index Item index
     *
     * @return integer
     */
    protected function getColumn($index)
    {
        return (int) $index % self::GRID_SIZE;
    }

    /**
     * Get the block number for the given index
     *
     * @param integer $index Item index
     *
     * @return integer
     */
    protected function getBlock($index)
    {
        return (int) (floor($this->getRow($index) / 3) * 3 + floor($this->getColumn($index) / 3));
    }

    /**
     * Get all items of the given type
     *
     * @param integer $index Item index
     * @param string  $type
     *
     * @return array
     */
    protected function getItems($index, $type)
    {
        $method = sprintf('get%s', ucfirst($type));

        return array_filter($this->grid, function ($value, $itemIndex) use ($index, $method) {
            return null !== $value && $this->$method($itemIndex) === $index;
        }, ARRAY_FILTER_USE_BOTH);
    }

    /**
     * Get all items of the column
     *
     * @param integer $index Item index
     *
     * @return array
     */
    protected function getColumnItems($column)
    {
        return $this->getItems($column, 'column');
    }

    /**
     * Get all items of the row
     *
     * @param integer $index Item index
     *
     * @return array
     */
    protected function getRowItems($row)
    {
        return $this->getItems($row, 'row');
    }

    /**
     * Get all items of the block
     *
     * @param integer $index Item index
     *
     * @return array
     */
    protected function getBlockItems($block)
    {
        return $this->getItems($block, 'block');
    }

    /**
     * Check if the given value for the given index
     *
     * @param integer $index
     * @param integer $value
     *
     * @return boolean
     */
    protected function isValid($index, $value)
    {
        if (null === $value) {
            return false;
        }

        return !in_array($value, $this->getColumnItems($this->getColumn($index))) &&
            !in_array($value, $this->getRowItems($this->getRow($index))) &&
            !in_array($value, $this->getBlockItems($this->getBlock($index)));
    }

    /**
     * Check if a row is valid
     *
     * @param integer $row
     *
     * @return boolean
     */
    protected function isValidRow($row)
    {
        return count(array_diff($this->getRowItems($row), range(1, self::GRID_SIZE))) === 0;
    }

    /**
     * Check if a column is valid
     *
     * @param integer $column
     *
     * @return boolean
     */
    protected function isValidColumn($column)
    {
        return count(array_diff($this->getColumnItems($column), range(1, self::GRID_SIZE))) === 0;
    }

    /**
     * Check if a block is valid
     *
     * @param integer $block
     *
     * @return boolean
     */
    protected function isValidBlock($block)
    {
        return count(array_diff($this->getBlockItems($block), range(1, self::GRID_SIZE))) === 0;
    }

    /**
     * Check if the sudoku is solved
     *
     * @return boolean
     */
    protected function isSolved()
    {
        foreach ($this->grid as $index => $value) {
            if (!$this->isValid($index, $value)) {
                return false;
            }
        }

        return true;
    }

    /**
     * Get possible valid values for the given index
     *
     * @param integer $index
     * @param array   $exclude
     *
     * @return array
     */
    protected function getValidValues($index, array $exclude)
    {
        $values = [];

        foreach (range(1, self::GRID_SIZE, 1) as $value) {
            if (!in_array($value, $exclude) && $this->isValid($index, $value)) {
                $values[] = $value;
            }
        }

        return $values;
    }

    /**
     * Get the next empty cell
     *
     * @return integer
     */
    protected function getCandidateCell()
    {
        $filteredGrid = array_keys(array_filter($this->grid, function ($value) {
            return null === $value;
        }));

        return reset($filteredGrid);
    }
}