Sudoku Solver Assignment

Overview

In this assignment, you will implement a search algorithm to solve Sudoku puzzles. The starter code provides a mechanisim to load in a board using .sdk files and can display it. Your task is to implement an efficient algorithm that can solve Sudoku puzzles of varying difficulty. Note that I have given you only one example of an easy puzzle, so you will need to find additional more difficult cases to evaluate your approach on.

Sudoku is a 9x9 grid-based logic puzzle where each row, column, and 3x3 subgrid must contain all digits from 1 to 9 without repetition. This assignment will test your understanding of constraint satisfaction problems (CSPs) and backtracking search algorithms.

Assignment Goals

• Apply backtracking and constraint propagation techniques to solve Sudoku puzzles
• Implement heuristic functions to improve search efficiency
• Understand constraint satisfaction problems in practice
• Analyze and compare algorithm performance for puzzles of different difficulty levels

Setup

1. Clone the repository and change into its directory

2. Run pip install -r requirements.txt to install necessary dependencies from requirements.txt

3. Define puzzles in JSON file according to format described in puzzles/samples.json

4. Run test.py from the terminal to assess performance of different solver configurations on puzzles

   • Run test.py -h to see what positional/optional arguments script takes
   • If you defined any metadata key-value pairs in the JSON puzzles file and want to record them in the resulting CSV, specify the --record-puzzle-metadata parameter followed by the key name(s).

   Example usage:

   test.py puzzles/nyt.json --var-order-heuristic rand --val-order-heuristic rand --propagation-algo fwd_chk --seed 101 --record-puzzle-metadata difficulty --solver-timeout 60 --output-dir results/