xeeeveee/sudoku

PHP sudoku logic library - Generate and solve sudoku puzzles

, _(*1)

PHP Sudoku Generator & Solver

A PHP Sudoku generate and solver implemented via a bruteforce backtracking algorithm., _(*2)

Installation

Install via composer with php composer require xeeeveee/sudoku:*, _(*3)

Usage

TL;DR full examples

    // Generate a new puzzle
    $puzzle = new Xeeeveee\Sudoku\Puzzle();
    $puzzle->generatePuzzle();
    $puzzle = $puzzle->getPuzzle();

    // Solve a pre-determined puzzle
    $puzzle = new Xeeeveee\Sudoku\Puzzle($puzzle);
    $puzzle->solve();
    $solution = $puzzle->getSolution();

    // Check a puzzle is solvable
    $puzzle = new Xeeeveee\Sudoku\Puzzle();
    $puzzle->setPuzzle($puzzle);
    $solvable = $puzzle->isSolvable();

    // Check a puzzle is solved
    $puzzle = new Xeeeveee\Sudoku\Puzzle();
    $puzzle->setPuzzle($puzzle);
    $puzzle->solve($puzzle);
    $solved = $puzzle->isSolved();

    // Generate a puzzle with a different cell size
    $puzzle = new Xeeeveee\Sudoku\Puzzle();
    $puzzle->setCellSize(5); // 25 * 25 grid
    $puzzle->generatePuzzle();

    // Setting properties in the constructor
    $puzzle = new Xeeeveee\Sudoku\Puzzle($cellSize, $puzzle, $solution);

Generator

Once an instance has been initialized you can generate a new sudoku puzzle by calling the generatePuzzle() method as below:, _(*4)

    $puzzle = new Xeeeveee\Sudoku\Puzzle();
    $puzzle->generatePuzzle();

You can also specify the difficulty of the puzzle to generate by passing an integer between 0 and the maximum number of cells in the puzzle (81 for a 3*3 $cellSize). This represents how many of the cells will be pre-populated in the puzzle. For example, the below snippet should generate a puzzle with 25 of the cells pre-populated., _(*5)

    $puzzle = new Xeeeveee\Sudoku\Puzzle();
    $puzzle->generatePuzzle(25);

Solver

Solving a puzzle is as simple as calling the solve() method on the object, which will return either true or false depending on the outcome, see below for example:, _(*6)

    $puzzle = new Xeeeveee\Sudoku\Puzzle();
    $puzzle->generatePuzzle(25);
    $puzzle->solve();

You can use the isSolved() method to check if the object contains a solved solution, and use the getSolution method to retrieve the array, a more complete example might look like the below:, _(*7)

    $puzzle = new Xeeeveee\Sudoku\Puzzle();
    $puzzle->generatePuzzle(25);

    if($puzzle->isSolvable() && $puzzle->isSolved() !== true) {
        $puzzle->solve();
    }

    $solution = $puzzle->getSolution();

Puzzle & solution format

A standard ($cellSize 3) puzzle and solution is represented as 3 dimensional array, effectively 9 ($cellSize * $cellSize) rows with the same number of columns. Blank values are represented as 0. The definition for a complete empty (`$cellSize 3) puzzle or solution would look like the below:, _(*8)

    $puzzle = [
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
    ];

Performance notice

Due to the nature of the algorithm used to generate and solve puzzles, the execution time for these commands increases exponentially as the $cellSize used is increased, puzzles with a $cellSize exceeding 4 will take an exceptionally long time to solve on average., _(*9)

Available methods

integer getCellSize() Returns cell size of the puzzle., _(*10)

boolean setCellSize() Sets the cell size of the puzzle. Note - This will reset the $puzzle and $solution properties on the object., _(*11)

integer getGridSize() Returns cell size of the puzzle. Note - This is calculated based on the $cellSize property., _(*12)

array getPuzzle() Returns the puzzle array., _(*13)

boolean setPuzzle(array $puzzle = []) Sets the puzzle array - If the $puzzle parameter is omitted or an invalid array structure is pass, a empty grid will be generated and false will be returned. Note - Setting the puzzle always resets the solution to an empty grid., _(*14)

array getSolution() Returns the solution array., _(*15)

boolean setSolution(array $solution) Sets the solution, if the $solution parameter supplied is an invalid format false is returned and the solution is not modified., _(*16)

boolean solve() Attempts to solve the puzzle., _(*17)

boolean isSolved() Returns true if a the solution is valid for the current puzzle., _(*18)

boolean isSolvable() Returns true if the puzzle is solvable - This is significantly quicker then actually solving the puzzle., _(*19)

boolean generatePuzzle($cellCount = 15) Generates a new puzzle, the $cellCount parameter specifies how many cells will be pre-populated, effectively manipulating the difficulty. 0 - 81 are valid values for $cellCount if any other value is supplied false is returned. Note - Generating a puzzle always resets the solution to an empty grid., _(*20)