Skip to content

Solve expert level Sudoku using only logical techniques (in other words no brute forcing or guessing). Outputs a detailed description of the techniques and moves required at each step. In-depth analysis of difficulty, technique use, and processing times.

Notifications You must be signed in to change notification settings

KyleGough/sudoku

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Logical Sudoku Solver

Logical Sudoku solver written in Python that can solve expert level 9x9 Sudoku using only logical techniques and reasoning (in other words no brute forcing, guessing or backtracking). The program outputs a detailed description of the techniques and moves required at each step to solve unique solution Sudoku. The solver reads CSV files where each puzzle can be separated by newline characters to allow batch solving. In-depth analysis is provided regarding techniques, difficulty and processing time.

View additonal information on the logical techniques used here.

Table of Contents

Screenshot

combined

Techniques

  • Solo Candidate
  • Hidden Candidate
  • Subset Cover
  • Pointing Pairs/Triples
  • Box/Line Intersection
  • X-Wing
  • Singles Chain
  • Y-Wing
  • Unique Rectangles
  • Swordfish
  • Jellyfish
  • Bi-Value Universal Grave
  • XYZ-Wing
  • WXYZ-Wing

Benchmarking and Testing

Accuracy is determined by applying the corresponding technique and all previous techniques across all 49,151 17-clue Sudokus.

Technique Tests Passed ( /49,151) Tests Passed (%)
Solo Candidate 0 0
Hidden Candidate 21,905 44.6
Subset Cover 34,269 69.7
Pointing Pairs 41,376 84.2
Box/Line Reduction 41,628 84.7
X-Wing 41,643 84.7
Singles Chain 44,597 90.7
Y-Wing 45,798 93.2
Unique Rectangles 45,885 93.3
Swordfish 45,907 93.4
Jellyfish 45,912 93.4
Bi-Value Universal Grave 46,118 93.8
XYZ-Wing 46,174 93.9
WXYZ-Wing 46,265 94.1

Technique Coverage and Occurrences

This table demonstrates the percentage of test puzzles that feature at least one of each technique. Note that some harder techniques could be employed instead of multiple uses of easier techniques in certain Sudoku, however the solver has been implemented to ensure that easier techniques are prioritised over the more difficult techniques.

Technique Coverage (%) Occurrences
Solo Candidate 98.6 384,825
Hidden Candidate 100.0 271,095
Subset Cover 49.0 58,202
Pointing Pairs 25.3 14,211
Box/Line Reduction 2.7 1,416
X-Wing 0.8 412
Singles Chain 8.1 4,752
Y-Wing 3.0 1,279
Swordfish 0.2 138
Jellyfish 0.0 7
BUG 0.4 204
XYZ-Wing 0.8 419
WXYZ-Wing 0.7 359

Datasets

Datasets of different Sudoku puzzles were tested against the solver in order to test completeness, speed and efficiency.

  • Gordon Royle's list of all currently known 17-clue minimal Sudoku puzzles
    Used as the primary benchmark as contains a wide range of puzzle difficulties. 17 clues (initial numbers on the grid) is the minimum number of clues any Sudoku can have such that it has a unique solution. Testing all 49,151 puzzles repeatedly is time-consuming, so a subset of 1000 of these puzzles are used for continual testing purposes. Testing of all 49,151 is performed when relevant milestones are reached.
  • 1 million Simple Sudoku games
    The solver successfully solves 100% of the Sudoku in this dataset. A subset of 1000 of these puzzles are used to check for errors during development.

Running

The solver will run on .csv files where each 81-character line can represent one puzzle. 0's represent missing/unknown cells and the order of the cells goes from top to bottom, left to right. This project provides some example .csv files to test the program, for example to test the program on some Sudoku which require the use of the x-wing technique to solve, run:

./sudoku -om tests/xwing.csv
  • Use the -m flag to display the techniques used at each stage of solving.
  • Use the -o flag to display the initial grid and solved grid.

About

Solve expert level Sudoku using only logical techniques (in other words no brute forcing or guessing). Outputs a detailed description of the techniques and moves required at each step. In-depth analysis of difficulty, technique use, and processing times.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published