Project Euler Problem 96 Statement

Su Doku (Japanese meaning number place) is the name given to a popular puzzle concept. Its origin is unclear, but credit must be attributed to Leonhard Euler who invented a similar, and much more difficult, puzzle idea called Latin Squares. The objective of Su Doku puzzles, however, is to replace the blanks (or zeros) in a 9 by 9 grid in such that each row, column, and 3 by 3 box contains each of the digits 1 to 9. Below is an example of a typical starting puzzle grid and its solution grid.

A well constructed Su Doku puzzle has a unique solution and can be solved by logic, although it may be necessary to employ "guess and test" methods in order to eliminate options (there is much contested opinion over this). The complexity of the search determines the difficulty of the puzzle; the example above is considered easy because it can be solved by straight forward direct deduction.

The 6K text file, sudoku.txt (right click and 'Save Link/Target As...'), contains fifty different Su Doku puzzles ranging in difficulty, but all with unique solutions (the first puzzle in the file is the example above).

By solving all fifty puzzles find the sum of the 3-digit numbers found in the top left corner of each solution grid; for example, 483 is the 3-digit number found in the top left corner of the solution grid above.

Solution

Although the problem statement proclaims the puzzles to solve are easy and don't require backtracking or guessing, I took it a step further and wrote a complete solution. So, this Sudoku solver employs recursive backtracking combined with efficient constraint checking to solve the puzzle.

For each empty cell (marked as '0'), it creates a set of excluded numbers by checking what's already present in the same row, column, and 3x3 block, then tries each valid remaining number (1-9) in that cell. When it places a number, it recursively attempts to solve the rest of the puzzle with that choice; if no solution is found, it backtracks and tries the next possible number. This process continues until either all cells are filled (success) or no valid numbers remain for a cell (requiring backtracking).

Code Breakdown

Lambda Functions for Row, Column, and Block Matching

same_row = lambda i, j: i // 9 == j // 9
same_col = lambda i, j: (i - j) % 9 == 0
same_block = lambda i, j: i // 27 == j // 27 and i % 9 // 3 == j % 9 // 3

These functions help determine whether two cells (indices i and j) are in the same:

• Row: Both indices divide into the same integer when divided by 9 (i // 9 == j // 9).
• Column: The difference between indices is divisible by 9 ((i - j) % 9 == 0).
• Block: Both indices fall into the same 3x3 block:
  • Same top-level block by row: i // 27 == j // 27.
  • Same sub-block by column: i % 9 // 3 == j % 9 // 3.

Finding the First Empty Cell

Handling Solved Board

If no empty cell exists (board.index('0') raises a ValueError), the board is solved:

except ValueError:
    print('\n'.join(board[i:i+9] for i in range(0, 81, 9)))
    return True

• The board is printed in a formatted 9x9 grid using slicing (board[i:i+9]).
• The function returns True to signal that a solution has been found.

Finding Excluded Numbers

excluded = {board[j] for j in range(81) if same_row(empty, j) or same_col(empty, j) or same_block(empty, j)}

For the currently empty cell (empty), the program builds a set of all numbers that are already present in the same row (same_row), column (same_col), and block (same_block). This helps determine which numbers cannot be placed in the empty cell.

Trying Possible Numbers

for num in '123456789':
    if num not in excluded and solve_sudoku(board[:empty] + num + board[empty+1:]):
        return True

The program iterates through all possible digits (1 to 9) and checks if each digit is not in the 'excluded' set. For each valid digit, it recursively calls 'solve_sudoku' with an updated board where the empty cell is replaced with the current digit (using board[:empty] + num + board[empty+1:]). If any of these recursive calls leads to a solution (returns True), the program returns True, indicating a valid solution has been found.

Backtracking

If none of the numbers result in a solution for the current configuration, the function returns False to backtrack and try a different number in a previous cell.

How the Algorithm Works

The Sudoku solver employs recursive backtracking combined with efficient constraint checking to solve the puzzle. For each empty cell (marked as '0'), it creates a set of excluded numbers by checking what's already present in the same row, column, and 3x3 block, then tries each valid remaining number (1-9) in that cell. When it places a number, it recursively attempts to solve the rest of the puzzle with that choice; if no solution is found, it backtracks and tries the next possible number. This process continues until either all cells are filled (success) or no valid numbers remain for a cell (requiring backtracking).

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 96

HackerRank Project Euler 96 i.

Last Word