Sudoku.exe

Overview

Objectives/Goals Sudoku is an NP-complete puzzle, meaning that it is in a group of puzzles of great importance to mankind. So, I pose the question, "What heuristics are most efficient in helping to solve a Sudoku puzzle?" There are many heuristics to use: I tested a specific four: the Single-Possibility Rule (SPR), Apparent Twin Rule (ATR), Hidden Twin Rule (HTR), the Sub-Group Exclusion Rule (SGXR). I saw the HTR occurring in many situations in puzzles, thus I saw it eliminating many possible values for each spot in a puzzle. Hence, I hypothesized that if I test all those heuristics with a depth-first search as control, then the hidden twin rule would be most efficient. Methods/Materials For a test group, I used a list of 1000 randomly generated puzzles. I had two different computers, one cutting-edge, one nearly antique, both solve all 1000 puzzles with first no heuristics then each one, one at a time. The program cataloged times as it proceeded, and then computed some summary statistics. Results The heuristics ranked in a clear order by average time: SPR (0.01 sec), ATR (0.07), none (control) (0.24), SGXR (0.30), HTR (35.75). Conclusions/Discussion HTR was clearly the least efficient, so I reject my hypothesis. I attribute this to the amount of looping that was required to implement it. However, there are better implementations. It would be interesting to extend the project and re-try it with better implementations.

Competition history

• CSEF 2012 Mathematics & Software · Entry J1410

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2012 project