Log In Sign Up
Day 50

Day 50: Sudoku Solver

50/60 Days

Day 50: Sudoku Solver #

Welcome to Day 50 of our 60 Days of Coding Algorithm Challenge! Today, we’ll tackle the Sudoku Solver problem, another classic application of backtracking algorithms.

What is Sudoku? #

Sudoku is a logic-based number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, row, and 3×3 sub-grid contains all digits from 1 to 9 without repetition.

Understanding the Problem #

  • We have a 9×9 grid, partially filled with digits from 1 to 9.
  • Empty cells are represented by 0 or ‘.’.
  • We need to fill all empty cells following Sudoku rules.
  • A valid Sudoku solution must satisfy:
    1. Each row contains digits 1-9 without repetition.
    2. Each column contains digits 1-9 without repetition.
    3. Each of the nine 3×3 sub-grids contains digits 1-9 without repetition.

Backtracking Approach #

We’ll use a backtracking approach to solve this problem:

  1. Find an empty cell.
  2. Try placing digits 1-9 in this cell.
  3. Check if the digit is valid in the current cell.
  4. If valid, recursively try to fill the rest of the grid.
  5. If the recursive call is successful, return true.
  6. If not successful, backtrack and try the next …