CoenMooij\Sudoku\Solver\BacktrackSolver

Complexity

Total Complexity

28

Size/Duplication

Total Lines	147
Duplicated Lines	0 %

Importance

Changes

0

13 Methods

Rating	Name	Duplication	Size	Complexity
A	solve()	0	17	5
A	locationIsValid()	0	3	2
A	currentLocationHasPossibleValues()	0	3	1
A	getCurrentLocation()	0	3	1
A	isPresetValue()	0	3	1
A	initializePresetValues()	0	9	4
A	initialize()	0	9	1
A	nextLocation()	0	8	6
A	reachedEndOfGrid()	0	3	1
A	handleForwardsIteration()	0	8	2
A	fillCurrentLocationWithNextPossibleValue()	0	4	1
A	handleBackwardsIteration()	0	7	2
A	findAllPossibleValuesForCurrentLocation()	0	5	1

<?php

declare(strict_types=1);

namespace CoenMooij\Sudoku\Solver;

use CoenMooij\Sudoku\Exception\UnsolvableException;
use CoenMooij\Sudoku\Puzzle\Grid;
use CoenMooij\Sudoku\Puzzle\Location;

/**
 * Informed depth first search.
 */
class BacktrackSolver implements GridSolverInterface
{
    private const DIRECTION_FORWARDS = true;
    private const DIRECTION_BACKWARDS = false;

    /**
     * @var Grid
     */
    private $grid;

    /**
     * @var int[][][]
     */
    private $possibleValues;

    /**
     * @var bool[][]
     */
    private $presetValues;

    /**
     * @var bool
     */
    private $direction;

    /**
     * @var int
     */
    private $row;

    /**
     * @var int
     */
    private $column;

    public function solve(Grid $grid): Grid
    {
        $this->initialize($grid);

        while ($this->locationIsValid()) {
            if (!$this->isPresetValue()) {
                $this->direction === self::DIRECTION_FORWARDS
                    ? $this->handleForwardsIteration()
                    : $this->handleBackwardsIteration();
            }
            $this->nextLocation();
        }
        if (!$this->reachedEndOfGrid()) {
            throw new UnsolvableException();
        }

        return $grid;
    }

    private function handleForwardsIteration(): void
    {
        $this->findAllPossibleValuesForCurrentLocation();
        if ($this->currentLocationHasPossibleValues()) {
            $this->fillCurrentLocationWithNextPossibleValue();
        } else {
            $this->grid->empty($this->getCurrentLocation());
            $this->direction = self::DIRECTION_BACKWARDS;
        }
    }

    private function handleBackwardsIteration(): void
    {
        if ($this->currentLocationHasPossibleValues()) {
            $this->fillCurrentLocationWithNextPossibleValue();
            $this->direction = self::DIRECTION_FORWARDS;
        } else {
            $this->grid->empty($this->getCurrentLocation());
        }
    }

    private function initialize(Grid $grid): void
    {
        $this->direction = self::DIRECTION_FORWARDS;
        $this->column = 0;
        $this->row = 0;
        $this->grid = $grid;
        $this->possibleValues = [];
        $this->presetValues = [];
        $this->initializePresetValues();
    }

    private function initializePresetValues(): void
    {
        for ($row = 0; $row < 9; $row++) {
            for ($column = 0; $column < 9; $column++) {
                $location = new Location($row, $column);
                if ($this->grid->isEmpty($location)) {
                    $this->presetValues[$row][$column] = false;
                } else {
                    $this->presetValues[$row][$column] = true;
                }
            }
        }
    }

    private function currentLocationHasPossibleValues(): bool
    {
        return !empty($this->possibleValues[$this->row][$this->column]);
    }

    private function findAllPossibleValuesForCurrentLocation(): void
    {
        $possibilities = $this->grid->getAllPossibilitiesFor(new Location($this->row, $this->column));
        shuffle($possibilities);
        $this->possibleValues[$this->row][$this->column] = $possibilities;
    }

    private function nextLocation(): void
    {
        if ($this->direction === self::DIRECTION_FORWARDS) {
            $this->row = $this->column === 8 ? $this->row + 1 : $this->row;
            $this->column = $this->column === 8 ? 0 : $this->column + 1;
        } else {
            $this->row = $this->column === 0 ? $this->row - 1 : $this->row;
            $this->column = $this->column === 0 ? 8 : $this->column - 1;
        }
    }

    private function fillCurrentLocationWithNextPossibleValue(): void
    {
        $this->grid->set($this->getCurrentLocation(), $this->possibleValues[$this->row][$this->column][0]);
        array_shift($this->possibleValues[$this->row][$this->column]);
    }

    private function getCurrentLocation(): Location
    {
        return new Location($this->row, $this->column);
    }

    private function isPresetValue(): bool
    {
        return !empty($this->presetValues[$this->row][$this->column]);
    }

    private function locationIsValid(): bool
    {
        return $this->row >= 0 && $this->row < 9;
    }

    private function reachedEndOfGrid(): bool
    {
        return $this->row > 8;
    }
}