Sudoku Solver

Overview

This program implements a Sudoku solver that reads a 9x9 Sudoku grid, verifies its legality, and systematically works through possible solutions. It first applies logical elimination techniques and, if necessary, resorts to a backtracking approach with increasing depth.

How It Works

1. Reading the Input

The program begins by reading a 9x9 matrix of numbers, where each number represents a Sudoku cell value. Empty cells are represented by 0.

2. Checking for Legality

Before solving, the program verifies that the given Sudoku grid is legal by ensuring:

• No duplicate numbers exist in any row, column, or 3x3 sub-grid.
• The initial puzzle configuration adheres to standard Sudoku rules.

3. Building the Possibilities Cube

A 9x9x9 cube of integers is created to track possible values for each cell:

• The first two dimensions represent the Sudoku grid (row, column).
• The third dimension represents possible values (1-9) that a cell might contain.
• Initially, all empty cells are assigned all possible values, while filled cells retain their given number.

4. Logical Elimination

The program iterates through the possibilities cube, eliminating values that conflict with known numbers. It applies:

• Row, Column, and Sub-grid Constraints: Removing numbers that already appear in the same row, column, or 3x3 box.
• Single Candidate Rule: If a cell has only one possible value, it is assigned that number.

5. Guessing and Backtracking

If logical elimination does not fully solve the puzzle:

• The program chooses a cell with multiple possibilities and makes a guess.
• It then recursively solves the puzzle under that assumption.
• If the guess leads to a contradiction, it backtracks and tries another value.

6. Multi-Level Guessing with Depth Control

If simple guessing does not yield a solution, the program increases the complexity:

• It explores multiple guesses simultaneously.
• The variable smax determines the maximum search depth.
• Higher values of smax allow for deeper searches but significantly increase computation time.

Performance Considerations

• The Sudoku solver performs well on most puzzles using elimination techniques.
• Harder puzzles require guessing, increasing computational effort.
• Increasing smax too much can lead to exponential runtime growth.

Usage

To run the Sudoku solver, provide a 9x9 matrix input and specify the maximum search depth (smax) if needed. The program will attempt to solve the puzzle and output the completed grid.

Notes

• This solver is designed for standard 9x9 Sudoku puzzles.
• It assumes a well-formed input with valid initial conditions.
• The program may struggle with extremely difficult or unsolvable puzzles if smax is too low.

---

Feel free to reach out or suggest improvements! 🎯