/sudoku-solver

Solve Sudoku as a Constraint Satisfaction Problem

Primary LanguagePython

Sudoku AI Solver

This program uses Constraint Propagation, Backtracking Search, Forward Checking, MRV and Degree Heuristics to solve 9 x 9 Sudoku puzzles.
This program will do:

  1. Read Sudoku problems from file
  2. Solve problem via:
    • Constraint Propagation (use AC-3 algorithm)
      Remove all non-valid domain values given the initial sudoku layout
    • Backtracking Search (BT) extended by Forward Checking (FC) + MRV and Degree Heuristics
      Traverse blank cells to assign possible value in its domain. After a blank cell is assigned a value, verify the validity by forward checking. If the one conflicts with another value, go back to previous state and try another possible value. Heuristics are used to determine which blank cell to assign next.
  3. Display solution to the terminal

Build Instructions

Prepare Input File

  • Name input file as sudoku-puzzles.csv
  • 9 x 9 sudoku board is represented as 81 consecutive numbers
  • Format sudoku puzzles as [puzzle] {[puzzle solution]}
    • 0 represents an empty cell
    • puzzle solution is optional (if solution is provided, program will display solution at the end)
    • multiple puzzles can be added to input file (in that case, program will select puzzle randomly) 

Example with solution
030604250200300100009250008000700090902005031740100006090070604001060000526800903 837614259254398167619257348183726495962485731745139826398572614471963582526841973


Example without solution
008605010000000420010700000000010530000000080300800009040900000097001600030024000

Run Program
Type command python3 solver.py to start program

Output Example

output-example