To test my code, you have 1 of two options. Either change list1 on line 286 or add your own sudoku puzzles to the puzzles.txt file. The puzzles are stored as 81 line strings, where blank spaces are represented by dots (.). when run, my code goes through each board in the puzzles.txt file(unless you change list1 on line 286 of course)
A bruteforce method for solving the board would be as follows: try 1 in the first available square and see if the board is still valid. If so , continue to the next square and try a 1. If a 1 doesn't work, try a 2 and continue. Keep doing that until either the puzzle is solved or all 1-9 don't work. If the latter is the case, this means you have made an error earlier on and need to go back to an earlier setting of a number. This is very slow however, and so my code involves some techniques that make it faster than this naive implementation.
My techniques used to make faster code are as follows:
Whenever I try a new number in a sudoku board, instead of checking the whole board to make sure that it is stll valid, I only check the ~27 spots directly affected by the new number being added
I keep a dictionary that stores information about which spots on the sudoku board have the least amount of possibilities given a current board state. Every time a try a new number that is valid, the next number that I try to check is the one with the least amount of possibilities after that change.
for every additional number I check, I see if there are any squares that are immediately solvable. Instead of recurring my whole method, I fill in that new square right away and checking to see if there are any MORE squares immediately solvable. I do this until I cannot anymore.
-
Notifications
You must be signed in to change notification settings - Fork 0
maxwelljones14/Sudoku
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
About
Code to solve sudoku, using smart techniques
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published