GAZAR

Principal Engineer | Mentor
Home
Algorithm
Sudoku Algorithm and Problem

Sudoku Algorithm and Problem

Sudoku Algorithm and Problem

A Sudoku puzzle consists of a partially filled grid where the objective is to fill in the empty cells with digits from 1 to 9 such that every row, column, and 3x3 subgrid contains each digit exactly once.

Backtracking Algorithm:

The backtracking algorithm is a systematic method to explore all possible configurations of the Sudoku puzzle. It starts with an initial configuration and systematically tries different combinations until a solution is found or all possibilities are exhausted.

First I have a sample of a Grid:

const sudokuGrid = [
  [5, 3, 0, 0, 7, 0, 0, 0, 0],
  [6, 0, 0, 1, 9, 5, 0, 0, 0],
  [0, 9, 8, 0, 0, 0, 0, 6, 0],
  [8, 0, 0, 0, 6, 0, 0, 0, 3],
  [4, 0, 0, 8, 0, 3, 0, 0, 1],
  [7, 0, 0, 0, 2, 0, 0, 0, 6],
  [0, 6, 0, 0, 0, 0, 2, 8, 0],
  [0, 0, 0, 4, 1, 9, 0, 0, 5],
  [0, 0, 0, 0, 8, 0, 0, 7, 9]
];

Then to make sure I wrote a function to test the grid if it's complete or not

const gridLineTest = (myGrid) => {
    let myGridRow = []
    let myGridCol = []
    for ( let i = 0; i < myGrid.length ; i++) {
        myGridRow = [];
        myGridCol = []
        for ( let j = 0; j < myGrid.length ; j++) {
            if (myGridRow.includes(myGrid[i][j])) return false;
            myGridRow.push(myGrid[i][j])
            if (myGridCol.includes(myGrid[j][i])) return false;
            myGridCol.push(myGrid[j][i])
        }
    }
    return true;
}

And finally wrote a functionto solve and check for an available number with the 3 by 3 box withing i and j.

const checkForANumberLeft = (myGrid, i, j) => {
    const numbersUsed = []
    
    const startRow = Math.floor(i / 3) * 3;
    const startCol = Math.floor(j / 3) * 3;
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        numbersUsed.push(myGrid[startRow + i][startCol + j])
      }
    }
    
    for ( let index = 0; index < myGrid.length ; index++) {
        if (!numbersUsed.includes(index+1)) return index+1;
    }
    
    console.log(numbersUsed)
    
    return false;
}

const solveSudoku = (myGrid) => {
    for ( let i = 0; i < myGrid.length ; i++) {
        for ( let j = 0; j < myGrid.length ; j++) {
            if (myGrid[i][j] === 0) {
                const numberToUse = checkForANumberLeft(myGrid,i,j)
                if (numberToUse) {
                    myGrid[i][j] = numberToUse    
                } else {
                    myGrid[i][j] = 0
                    return {
                        status: false,
                        myGrid
                    };
                }
            }
        }
    }
    return {
        status: true,
        myGrid
    }
}

which you can easily test by writing this.

const solvedGrid = solveSudoku(sudokuGrid);
console.log(solvedGrid)
if (solvedGrid.status) {
    console.log(gridLineTest(solvedGrid))
}

Solving Sudoku puzzles requires a combination of logic, pattern recognition, and algorithmic techniques. In this article, we explored different approaches to solve Sudoku puzzles, including backtracking, constraint satisfaction, and brute-force search algorithms, with JavaScript examples.

Comments