Neonira
by Neonira

Categories

  • games
  • EN

Tags

  • sudoku
  • computer
  • R

Unsolvable sudoku?

As stated in previous article about sudokus sudoku solver, I experimented my solver on really hard to solve sudokus. Consider the following, taken from The Weekly Extreme 'Unsolveable' Sudoku Puzzle #154
sudoku #1
Before I enter into analysis, you should try to solve it by hand. Get ready to face some trouble.
Sincerely, I believe I would have give up before finding final solution, if I had to do so.

Let's look closer. Nearly one on three figures of the sudoku are already set. From that point of view starting position does not seem so tough. Moreover, no figure is missing. If you except the 9, given 5 times, all other figures are really sporadic. So, why is it so difficult to solve ?

Quite difficult to say at first glance. Post resolution analysis, provides some hints.
  1. the total number of inferences to cover the full resolution path ends up to be 205. This is tied to the resolution algorithm - probably not so smart apparently - that could be optimized.
  2. The key point is that many inferences do not allow to deduce anything and to progress towards solution or to backtrack on error. I mean resolution path, whatever the path considered is long.


As text is not so informative, let's see an image of the resolution path open it on a new tab for zooming features
resolution path
So, information provided is now clearer
  1. inference reaches 10 levels of depth for resolution
  2. inference reaches 55 levels of breadth for resolution
  3. did you notice, the number of nodes with 2 or 3 arrows ?
Solution scope reduction starts at depth 7. Prior to this level, there are so many possibilities without enough constraints to reduce possible figures. This is where resides complexity from my point of view. Solution required 16 passes, each of them compound of positive and negative logic deduction.
If you want to see the resolution ...

Final solution grid is therefore

sudoku #1
Note

All calculus and image have been produced using R language.
Some image format transformation done with GIMP.
Film montage executed with tool external to R.