Sudoku Rules: Using A Decision Engine To Solve Sudoku
See the progress the author has made since last time, after setting themselves the challenge of solving Sudoku puzzles using an optimized inference engine, along with a few other advanced features of FICO® Blaze Advisor®.
By Fernado Donati Jorge, FICO
This blog is the second post in our Sudoku Series. In case you missed it, click here to catch up on part 1. For those of you already caught up, keep reading for more…
The History
Before developing my Sudoku addiction, I knew very little about the origins of Sudoku. I assumed it was an ancient Japanese tradition, probably created by a famous court mathematician in the middle ages to entertain a bored emperor.
In one of the famous chess origin legends, a mathematician in India is credited for inventing the game and teaching the king a valuable moral lesson about the value of small things. Sudoku, I assumed, must have been the Japanese equivalent, with some hidden moral about the perfect balance of all things in life.
Well, it turned out I was wrong. Very wrong.
Sudoku is actually from the 80s. And yes, I mean the 1980s. Although similar “Number Place” puzzles can be found in 19th century French newspapers, it turns out Sudoku, as we all know and love, is actually a millennial. The name comes from Sūji wa dokushin ni kagiru, which roughly translates to “the digits must be single”. Thankfully, it was later abbreviated to Sudoku.
Curiously, the game only really took off outside of Japan after Wayne Gould, a Hong Kong judge, developed a computer program to generate unique puzzles, which he then submitted to British and American newspapers in 2004. It took Mr. Gould six years to develop the program, but Sudoku’s rise in popularity was meteoric: by the summer of 2005, there was already a celebrity-studded TV show called “Sudoku Live” on British TV. And in 2006, a tribute song to Sudoku was nominated by the Japanese Embassy for an award. Here’s an excerpt of the “Sudoku” song:
I put the tv off and disconnect the phone
Just to clear my mind from worldly things to do.
My pad and pen start to set the tone
As I venture into that big unknown
Escaping, as I must, into my Sudoku.
(Sudoku, by Peter Levy)
In the first blog of this series, I set myself the challenge of using the optimized inference engine, along with a few other advanced features of FICO® Blaze Advisor®, to solve Sudoku puzzles. If it took Mr. Gould six years to develop his program to generate unique puzzles, I should probably get back to work if I intend to solve these puzzles any time soon.
The Half-Solved Puzzle
At the end of the previous episode, my attempt to solve a Medium-difficulty puzzle failed. The picture below shows how far my initial implementation could go:
Figure 1 Half-solved Medium Sudoku Puzzle
I stared at the half-solved puzzle for a long time. I then grabbed a pencil and solved it without too much difficulty, circling the right candidate in each unsolved cell. While it was not hard for me to solve it by hand, I struggled to understand why the engine had not been able to progress further...
To learn more about my progress on the “Medium” Sudoku puzzle, read the full post of Sudoku Episode 2 here and keep your eyes peeled for part 3 of our series.