Overview
| module url | N/A |
| git repository | https://bitbucket.org/arrizza-public/game-sudoku |
| git command | git clone git@bitbucket.org:arrizza-public/game-sudoku.git |
| verification report | https://arrizza.com/web-ver/game-sudoku-report.html |
| version info | N/A |
- repo status: Repo Information
- installation: Common Setup
Summary
Solves Sudoku puzzles and calculates two complexity ratings.
I had been playing Sudoku and noticed that newspaper ratings didn't always align with the difficulty I had in finishing the game. I wrote this project to solve the game and rank it. It uses similar techniques to ones a human would use to ensure the complexity rating is accurate.
Then I used these ratings and compared them to the "star" ratings given in the newspapers that I was doing the Sudoku's in.
Complexity
To compare the newspaper's rating (n out of 5 stars) vs my Complexity and Complexity2, see "complexity vs stars.xls".
This shows there is corroboration between the three ratings, but there are exceptions.
For example, Game 20 was rated 5 out of 5 stars by the newspaper, but Complexity ranked it at 125 which is closer to 2 out of 5 stars. Complexity2 ranked Game20 at 1620 which is also equivalent to 2 out of 5 stars. It also ranked Game 36 (another newspaper 5 out of 5) at 1574 which is also 2 out of 5.
Both complexity ratings had a more subtle ranking than a simple stars. For example Complexity ranged from 15 to 82 for those games that ranked 1 out of 5 stars. Complexity ranged from 301 to 797 for the same games.
How to run
There are 55 sample puzzles in src/app.rb.
There are also text based on in the games directory.
./doit 1 # solves puzzle number 1.
./doit p5_hard.txt # see games directory
The board is evaluated once to get the candidates in each cell and then it is printed out. If a cell has been solved, the solution is placed bottom center in the cell. Otherwise, a "*" is printed and the possible values for the cell are printed above it.
# ./doit 1
#########################################################################
# 3 | 12 | 1 3 # 1 3 | 1 34 | # | 2 4 | #
# | 6 | # 8 | 8 | # | 6 | #
# * | * | * # * | * | 7 # 9 | * | 5 #
#-------+-------+-------#-------+-------+-------#-------+-------+-------#
# | 2 5 | 3 5 # 3 5 | 3 5 | 5 # | | #
# | 6 | 7 # | | 9 # 67 | | #
# 4 | * | * # * | * | * # * | 8 | 1 #
#-------+-------+-------#-------+-------+-------#-------+-------+-------#
# | 1 5 | # | 1 45 | # 4 | 4 | #
# | | # | | # 7 | 7 | #
# 9 | * | 8 # 2 | * | 6 # * | * | 3 #
#########################################################################
# | | 1 4 # 1 | 12 4 | 12 4 # | 12 4 | #
# 7 | | 7 9 # 7 | 7 | # | 67 | #
# * | 3 | * # * | * | * # 5 | * | 8 #
#-------+-------+-------#-------+-------+-------#-------+-------+-------#
# | 1 45 | 1 45 # | | # 1 4 | 12 4 | 2 4 #
# 78 | 8 | 7 # | | # 7 | 7 | 7 #
# * | * | * # 6 | 9 | 3 # * | * | * #
#-------+-------+-------#-------+-------+-------#-------+-------+-------#
# | 1 45 | # 1 5 | 1 45 | 1 45 # 1 34 | | 4 #
# | 8 | # 78 | 78 | # 7 | | 7 #
# 2 | * | 6 # * | * | * # * | 9 | * #
#########################################################################
# | | 3 # | 3 5 | # | 3 5 | #
# | 9 | 9 # | 7 | # | 7 | #
# 1 | * | * # 4 | * | 8 # 2 | * | 6 #
#-------+-------+-------#-------+-------+-------#-------+-------+-------#
# | | 34 # 1 3 | 123 | 12 # 1 34 | 1 34 | #
# | | # | 6 | # 8 | | #
# 5 | 7 | * # * | * | * # * | * | 9 #
#-------+-------+-------#-------+-------+-------#-------+-------+-------#
# | 4 | # | 1 3 5 | 1 5 # 1 34 | 1 345 | 4 #
# | 8 | # | 7 | # 78 | 7 | 7 #
# 6 | * | 2 # 9 | * | * # * | * | * #
#########################################################################
There will then be a series of lines indicating an ongoing complexity calculation and the characteristics of the puzzle that are contributing to the complexity.
# samples of these lines from varous puzzles
Unique - row : 5 7
Singleton - row : 1 10
Subrow - row : 20 42
Subcol - col : 20 67
Unique - row : 5 78
Unique - row : 5 90
Singleton - row : 1 99
Singleton - row : 1 109
Unique - row : 5 124
Subrow - row : 20 190
hidden_pair- blk : 40 244
Unique - col : 5 264
Singleton - row : 1 412
Singleton - row : 1 436
And finally, the solved puzzle is presented and the complexity rating is displayed.
A check is made to verify that the solved puzzle does have values 1-9 in rows, columns and blocks.
#########################################################################
# | | # | | # | | #
# | | # | | # | | #
# 3 | 6 | 1 # 8 | 4 | 7 # 9 | 2 | 5 #
#-------+-------+-------#-------+-------+-------#-------+-------+-------#
# | | # | | # | | #
# | | # | | # | | #
# 4 | 2 | 7 # 5 | 3 | 9 # 6 | 8 | 1 #
#-------+-------+-------#-------+-------+-------#-------+-------+-------#
# | | # | | # | | #
# | | # | | # | | #
# 9 | 5 | 8 # 2 | 1 | 6 # 7 | 4 | 3 #
#########################################################################
# | | # | | # | | #
# | | # | | # | | #
# 7 | 3 | 9 # 1 | 2 | 4 # 5 | 6 | 8 #
#-------+-------+-------#-------+-------+-------#-------+-------+-------#
# | | # | | # | | #
# | | # | | # | | #
# 8 | 4 | 5 # 6 | 9 | 3 # 1 | 7 | 2 #
#-------+-------+-------#-------+-------+-------#-------+-------+-------#
# | | # | | # | | #
# | | # | | # | | #
# 2 | 1 | 6 # 7 | 8 | 5 # 3 | 9 | 4 #
#########################################################################
# | | # | | # | | #
# | | # | | # | | #
# 1 | 9 | 3 # 4 | 7 | 8 # 2 | 5 | 6 #
#-------+-------+-------#-------+-------+-------#-------+-------+-------#
# | | # | | # | | #
# | | # | | # | | #
# 5 | 7 | 4 # 3 | 6 | 2 # 8 | 1 | 9 #
#-------+-------+-------#-------+-------+-------#-------+-------+-------#
# | | # | | # | | #
# | | # | | # | | #
# 6 | 8 | 2 # 9 | 5 | 1 # 4 | 3 | 7 #
#########################################################################
Complexity : 15
Complexity2: 292
Verified
If everything checks out, "Verified" is printed.