Sudoku Solver


Backtracking and AC-3 to solve 9×9 Sudoku

GitHub  ■  Methodology Blog  ■  Run in Browser »

Algorithmic Overview
This program uses constraint reasoning to solve 9×9 Sudoku puzzles. Specifically, I implemented the arc-consistency algorithm, AC-3, along with backtracking. The arc-consistency algorithm minimizes the search space to the point where backtracking is computationally in-expensive enough to solve the problem. The output describes the performance of each algorithm.

Check out main.py and helper.py for the source code. Feel free to play with it and save your own copy! The handy embedded interpreter is provided by repl.it 

Sudoku Rules

Given a 9×9 grid, each row and column should contain each digit from 1-9. In addition, dividing the grid into 9, 3×3 square grids, each grid should contain each digit from 1-9 as well. An example of one such grid is the upper left-most one, with coordinates: {A1, A2, A3, B1, B2, B3, C1, C2, C3}
 

Running Instructions

Click the Run Code button below. Register or close the modal. Click Play.
To input, either:
1) Press ‘Enter’ for a randomly selected puzzle from puzzles.txt
2) Copy and paste your own puzzle from puzzles.txt
3) Input your own puzzle (Format: 81 digits, 0 for blank, rest of digits 1-9)
Invalid inputs result in option 1)

 

X


Leave a Reply

Your email address will not be published. Required fields are marked *