Code Snippets PHP

Write a PHP program to solve a Sudoku puzzle by filling the empty cells.

By on Sunday, February 27, 2022
sudoku program

I am trying to scale up my programming skills every day. So I go through this program problem. It shows me I need to work on my coding skill and need more improvements in logical programming.

I am sharing this code snippet with you, so you can review this code at your end. You can improve this code as per your logic. If the program needs more improvement, please share your comments in the comment section.

Program Logic

A sudoku solution must satisfy all of the following rules:

    1. Each of the digits 1-9 must occur exactly once in each row.
    2. Each of the digits 1-9 must occur exactly once in each column.
    3. Each of the digits 1-9 must occur exactly once in each of the 9 3×3 sub-boxes of the grid.
    4. The ‘.’ character indicates empty cells.

Solution

  1. I create a class “SudokuSolution”.
  2. Divide the problem into three different function blocks
  3. 1st function “solveSudoku” is for set grid size and call another function. This is just two line code.
    So it looks easy and tidy for calling through class Object.
  4. 2nd function “iterateGrid” is a recursive function and it is iterating backtracking the grid number.
  5. 3rd function “checkBoxNumber” is conditional based. It is validating each gird box. it has 3 major conditions.
    • a. Number must be 1-9.
    • b. Each grid row has no duplicate number
    • c. Each grid column has no duplicate number.
    • c. Each sub-grid 3X3 has no duplicate number.
<?php

class SudokuSolution {

    /**
     * @param String[][] $board
     * @return NULL
    */

    function solveSudoku(&$board) {
        $gridSize = 9;

        $this->iterateGrid($board, 0, 0, $gridSize);
    }

    function iterateGrid(&$board, $row, $col, $gridSize){

        // check if reach end of array 8th row and 9th column. Stop iterating array.
        if( $row == $gridSize - 1 && $col == $gridSize )
        return true;

        // check if reach row end 9th column. Increase the row and make column index 0
        if( $col == $gridSize ){
            $row++;
            $col = 0;
        }

        // check if column have digit already
        if($board[$row][$col] != '.')
        return $this->iterateGrid($board, $row, $col+1, $gridSize );

        for($num = 1; $num < 10; $num++){

            // check if number is valid for board box
            if($this->checkBoxNumber($board, $row, $col, $num)){

                // place value in current row and column
                $board[$row][$col] = (string) $num;

                // move to next column
                if($this->iterateGrid($board, $row, $col+1, $gridSize ))
                return true;

            }

            // make current column value empty
            $board[$row][$col] = '.';
        }

        return false;
    }

    function checkBoxNumber($board, $row, $col, $num){

        // check same number in similar row
        for($counter = 0; $counter < 9; $counter++)
            if($board[$row][$counter] == $num)
                return false;

        // check same number in similar col
        for($counter = 0; $counter < 9; $counter++)
            if($board[$counter][$col] == $num)
                return false;
        
        // check the 3X3 sub box grid

        $startRow = $row - $row % 3;
        $startCol = $col - $col % 3;

        for($rowCounter = 0; $rowCounter < 3; $rowCounter++)
            for($colCounter = 0; $colCounter < 3; $colCounter++)
                if($board[$rowCounter + $startRow ][$colCounter + $startCol] == $num)
                    return false;

        return true;

    }


}

$board = [
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]];

echo '<h2>Sudoku Box Unsolved</h2>
<table border="1" style="width:200px;" align="center">';
for($row = 0; $row < 9; $row++){
    echo '<tr>';
    for($col =0; $col <9; $col++){
        echo '<td align="center">'.$board[$row][$col].'</td>';
    }
    echo '</tr>';
}
echo '</table>';

$obj = new SudokuSolution;
$obj->solveSudoku($board);
//echo '<pre/>'; print_r($board);
//echo json_encode($board);

echo '<h2>Sudoku Box Solved</h2>
<table border="1" style="width:200px;" align="center">';
for($row = 0; $row < 9; $row++){
    echo '<tr>';
    for($col =0; $col <9; $col++){
        echo '<td align="center">'.$board[$row][$col].'</td>';
    }
    echo '</tr>';
}
echo '</table>';
0
Related Posts