How to resolve the algorithm Sudoku step by step in the PHP programming language
How to resolve the algorithm Sudoku step by step in the PHP programming language
Table of Contents
Problem Statement
Solve a partially filled-in normal 9x9 Sudoku grid and display the result in a human-readable format.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Sudoku step by step in the PHP programming language
1. Class Definition
The code defines a class named SudokuSolver
that provides methods for solving Sudoku puzzles.
2. Properties
The class has two protected properties:
$grid
: Represents the Sudoku grid as a one-dimensional array of numbers.$emptySymbol
: Represents the symbol used to denote empty cells in the grid.
3. Constructor
The constructor __construct
initializes the properties based on the provided input string:
- It parses the input string into a grid of numbers using the
parseString
method. - It sets the
$emptySymbol
to the specified value.
4. parseString
Method (Static)
This static method is used to parse the input Sudoku string into a grid of numbers. It replaces empty cells with 0 and converts other characters to their integer equivalents.
5. solve
Method
The solve
method attempts to solve the Sudoku puzzle using a recursive backtracking algorithm:
- It calls the
placeNumber
method with an initial position of 0. - If the algorithm fails to find a solution, it throws an exception, indicating that the puzzle is unsolvable. Otherwise, it returns
false
to indicate a successful solution.
6. placeNumber
Method (Protected)
This method is used for placing numbers in the Sudoku grid:
- If the position is 81 (the last cell), it throws an exception, indicating a finished solution.
- If the cell already contains a number, it moves to the next cell.
- Otherwise, it checks all possible values (1-9) for the current cell, using the
checkValidity
method. - If a valid value is found, it places it in the cell and recursively calls itself for the next cell.
- If no valid value is found for the current cell, it backtracks and tries the next possible value.
7. checkValidity
Method (Protected)
This method checks if a given value is valid for a specific cell in the Sudoku grid:
- It checks if the value is already present in the same row or column.
- It checks if the value is present in the corresponding 3x3 block.
- If none of these conditions is met, the value is considered valid.
8. display
Method
This method displays the Sudoku grid in a user-friendly format.
9. __toString
Method
This method is used to convert the Sudoku grid back into a string, replacing any empty cells with the $emptySymbol
.
10. Usage
An instance of the SudokuSolver
class is created with an input Sudoku puzzle string. The solve
method is called to attempt a solution. If successful, the solution is displayed using the display
method.
Source code in the php programming language
class SudokuSolver {
protected $grid = [];
protected $emptySymbol;
public static function parseString($str, $emptySymbol = '0')
{
$grid = str_split($str);
foreach($grid as &$v)
{
if($v == $emptySymbol)
{
$v = 0;
}
else
{
$v = (int)$v;
}
}
return $grid;
}
public function __construct($str, $emptySymbol = '0') {
if(strlen($str) !== 81)
{
throw new \Exception('Error sudoku');
}
$this->grid = static::parseString($str, $emptySymbol);
$this->emptySymbol = $emptySymbol;
}
public function solve()
{
try
{
$this->placeNumber(0);
return false;
}
catch(\Exception $e)
{
return true;
}
}
protected function placeNumber($pos)
{
if($pos == 81)
{
throw new \Exception('Finish');
}
if($this->grid[$pos] > 0)
{
$this->placeNumber($pos+1);
return;
}
for($n = 1; $n <= 9; $n++)
{
if($this->checkValidity($n, $pos%9, floor($pos/9)))
{
$this->grid[$pos] = $n;
$this->placeNumber($pos+1);
$this->grid[$pos] = 0;
}
}
}
protected function checkValidity($val, $x, $y)
{
for($i = 0; $i < 9; $i++)
{
if(($this->grid[$y*9+$i] == $val) || ($this->grid[$i*9+$x] == $val))
{
return false;
}
}
$startX = (int) ((int)($x/3)*3);
$startY = (int) ((int)($y/3)*3);
for($i = $startY; $i<$startY+3;$i++)
{
for($j = $startX; $j<$startX+3;$j++)
{
if($this->grid[$i*9+$j] == $val)
{
return false;
}
}
}
return true;
}
public function display() {
$str = '';
for($i = 0; $i<9; $i++)
{
for($j = 0; $j<9;$j++)
{
$str .= $this->grid[$i*9+$j];
$str .= " ";
if($j == 2 || $j == 5)
{
$str .= "| ";
}
}
$str .= PHP_EOL;
if($i == 2 || $i == 5)
{
$str .= "------+-------+------".PHP_EOL;
}
}
echo $str;
}
public function __toString() {
foreach ($this->grid as &$item)
{
if($item == 0)
{
$item = $this->emptySymbol;
}
}
return implode('', $this->grid);
}
}
$solver = new SudokuSolver('009170000020600001800200000200006053000051009005040080040000700006000320700003900');
$solver->solve();
$solver->display();
You may also check:How to resolve the algorithm Sum of squares step by step in the NewLISP programming language
You may also check:How to resolve the algorithm Introspection step by step in the UNIX Shell programming language
You may also check:How to resolve the algorithm 99 bottles of beer step by step in the Lambdatalk programming language
You may also check:How to resolve the algorithm Machine code step by step in the M2000 Interpreter programming language
You may also check:How to resolve the algorithm Amicable pairs step by step in the Common Lisp programming language