Sudoku Solver

Solves sudoku through a brute-force algorithm I designed myself, though its probably nothing novel.

Rules of Sudoku

Vocabulary

• Number: A base ten digit.
• Cell: One spot where a number can be written in.
• Square: One of nine 3x3 squares of numbers where each digit can only occur once.
• Potential: In an unfilled cell, the numbers that could be placed without conflict at this point in the game.
• Conflict: Two numbers block each other from being valid solution states due to the rules of the game.
• Vertical: All cells above/below a cell
• Horizonal: All cells left/right a cell

Game Rules

• The board is composed of a grid of 3x3 squares. Within each square is a grid of 3x3 cells.
• Each cell can be filled with one base ten digit (number) or be empty.
• The board starts with some amount of cells filled with valid and immutable numbers.
• The same number cannot occur in two cells along a vertical, a horizonal, or within the same square.
• You are allowed unlimited attempts at filling in any cell that is not immutable.
• The only measure of performance is time to completion.
• The puzzle is solved when the board has no empty cells and no conflicts.

Algorithm

1. Find all potential positions for each number

2. Fill in positions:
   2a) If any cells have one potential, fill one in.
   2b) Else if any number has only one potential within a square, fill it in.
   2c) Else if no guaranteed correct choices exist, save the state of the board, and pick a cell/number that does not cause conflict, and remember what cell/number was used.
   2c) Else no cells can be filled in without conflict, reload from most recent board state and pick a potential that has not been tried.

3. The new number will block other occurences of the same number - update potential positions accordingly.

4. Check puzzle status
   4a) If puzzle solved, exit
   4b) Else, goto step 2.