← Back

Contents

Introduction Some terminology Task 1: Solve a 9x9 Sudoku grid Further terminology Task 2: Implement heuristics Minimum remaining values heuristic (MRV) Least constrained value heuristic (LCV)

Sudoku Solver

Introduction

Sudoku is a puzzle game played on a 9x9 grid. The grid is divided into nine 3x3 sub-grids. The goal is to fill the grid with digits from 1 to 9, such that: each digit (1-9) appears exactly once in every row, column, and 3x3 sub-grid.

The problem

Given a partially filled Sudoku grid, fill the empty cells such that the resultant fully-filled grid is a valid Sudoku solution.

Figure 1 shows a partially filled input grid and a corresponding fully-filled grid presenting a valid solution.

Figure 1: A partially filled Sudoku grid representing a typical input and a corresponding solution (a valid output)

The input

The input to the program is a partially filled grid: initial state. Each cell in the initial state contains either a digit from 1 to 9 or a '.' representing an empty cell.

The output

The output could be one of two things:

  • A fully filled grid representing a valid Sudoku solution, or,
  • a message that no solution exists for the given initial state.
In other words, you are required to write a recursive program that receives a partially filled initial state and attempts to reach a fully filled final state which satisfies all the Sudoku rules, or reports that no solution exists.

Some terminology

Solution Search Space: The solution search space is the set of all possible configurations that could solve a problem. In Sudoku, it includes every potential way to fill the grid with digits 1-9, regardless of whether the configurations follow the Sudoku rules.

Exhaustive Search: Exhaustive search explores all possible options within the solution search space to find a solution. For Sudoku, this involves trying every combination of numbers until a valid solution is found, but it can be time-consuming due to the large number of possibilities.

Backtracking: Backtracking is a recursive technique that explores possible solutions by making choices and undoing them if they lead to dead ends. In the context of Sudoku, backtracking places a number in a cell and, if it leads to an invalid configuration, reverses the decision and tries a different number.

Task 1: Solve a 9x9 Sudoku grid

Our first goal is to write a recursive exhaustive search algorithm to find a solution to a partially filled Sudoku grid.

Brief description of the algorithm

Following is a brief description of the recursive algorithm. It has been deliberately kept at a high level, leaving it to you to work out the details.

  • Identify the first empty cell: Start from the first empty cell in the Sudoku grid.
  • Attempt to place digits: Try placing each digit from 1 to 9 in the empty cell.
  • Validate placement: Check if the placed digit violates any Sudoku rules (row, column, or subgrid).
  • Recursive progression: If the digit is valid, move to the next empty cell and repeat the process.
  • Backtracking on failure: If no valid digit can be placed, backtrack to the previous cell to try a different placement.
  • Completion check: Continue this process until the grid is fully filled, or all possibilities are exhausted.

Implementation

The code below shows various function prototypes to be implemented. A brief comment against each prototype describes what the function is supposed to do. The main program shows how the functions are to be used. You may want to test your program on more inputs.

Further terminology

State: A specific configuration of the problem at a given moment. In the context of Sudoku, a state refers to the current arrangement of digits on the Sudoku grid, including both filled and empty cells.

State transition: The process of moving from one valid state to a next valid state. In the context of Sudoku, a state transition occurs when a digit is placed in an empty cell, altering the grid to a valid next state.

Goal state: The final configuration in a problem-solving process, where all constraints are satisfied (e.g., a fully solved Sudoku grid).

Heuristic function: A function, often denoted as h(s), which gives an estimate of the potential cost of reaching the goal state from a given state s. A good heuristic function helps guide the search toward more promising paths first.

Task 2: Implement heuristics

Currently, we could be spending a lot of time searching in subtrees that will not ultimately lead to a solution (goal state).

Heuristics can be used to prioritize subtrees (or paths) that are more likely to lead to a solution based on common-sense rules or educated guesses.

The input of a heuristic function h(s) is a potential next state (or child state) s that can be reached directly from the current state by making a single move. The output of the function is an estimate of the cost. This estimate helps choosing the child node to explore next.

Minimum remaining values (MRV) heuristic

The Minimum Remaining Values (MRV) heuristic selects the cell (to fill) that has the fewest legal options available (least number of valid placements). In other words, the most constrained cell. The intuition here is that since a few options are left for this cell one of them is likely to be part of a goal state.

Implementation

Write another version of the solve_sudoku method called solve_sudoku_MRV. Also, write functions count_MRV and h_MRV. The prototypes of these functions are shown below with brief explanations in comments:

Use the solve_sudoku_MRV function in the main and compare the number of recusrive calls it makes with those made in the basic backtracking code. Is there a reduction in the number of calls?

Least constraining value (LCV) heuristic

While the MRV heuristic looks to fill the most constrained cells first, the LCV looks for the least constraining digit.

It works by choosing the value (digit) which, when placed in a selected cell, leaves the most options open for other cells.

Intuitively, this heuristic reduces the likelihood of creating further constraints down the line, helping to avoid dead-ends and excessive backtracking.

Implementation

Following snippet shows prototypes of functions you need to add (feel free to add more utility functions if required). As before, compare the number of recursive calls made by solve_soduku_LCV per puzzle with those made by the basic backtracking and MRV methods.