How to resolve the algorithm Sudoku step by step in the PHP programming language

Published on 12 May 2024 09:40 PM

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