Sudoku Solver and Omniscient debugging

Let me make an analogy between debugging a program and solving a Sudoku. Sudoku is a number-crossword type of game where you fill in numbers in a 9x9 grid such that each row, column, and 3x3 box contain each of the numbers 1...9. The grid is pre-initialized with some of the numbers, and then you're supposed to use deduction to fill in the remaining numbers. In my upcoming analogy, that's similar to using deduction to debug programs. 

The game has become very popular (your local newspaper very likely caries a daily one), and so naturally Sudoku Solver software has popped up all over the web. This is a natural task for a computer. Most solvers that I've seen are search-based,  which means they have the following limitations:
1) they either find a 100% complete answer or give you nothing.
2) even if they do solve it, they can't explain how they solved it.
3) they only find one possible solution, but they can't guarantee that it's the only solution. Now in practice, a well-formed Sudoku puzzle is only supposed to have 1 solution, but you may encounter a bad initial puzzle.

This is like the state of debuggers today. Today's production debuggers can show you that a variable X has value 5, but it can't explain why it does.  (I know there's research going on here; but last I checked, none of it had really been productized yet).

Now compare that to the solvers that can explain how it solved the puzzle. Tim writes about a rule-based solver that solves with deduction instead of search. (He focuses on the java-script behind the web version; I'm more interested in the debugging analogy 🙂 ) This means:
1) if you enter an initial puzzle and have the Solver solve it, the Solver can provide a reason for every cell that was filled in. On the more complex puzzles, some of these reasons are pretty elaborate.
2) you can ask it for a hint, in which case it will solve just the next square, and then explain why that square was solvable.  Then you can read the explanation, smack yourself in the head, and say "Oh, I should have gotten that".
3) if it can't solve the whole puzzle (perhaps because it has multiple solutions), it will solve as much as it can. 

The download version exposes the solving engine through additional UI. For example, it lets you inspect a solved square and ask questions like "Why is this 4?":

Or inspect an open square and ask "Why can't this be 2?"

And then the app will give you the reason and supporting sub reasons. You can then navigate through the reasons until your thoroughly satisfied.

This is where I want to see debuggers heading. Imagine if your debugger would let you right click on a pointer and ask "Why P1 is this null?", and then it would give you back a series of reasons like "because it was assigned that value from variable Y on line 1234 on thread 3", and then you could continue the interrogation with questions like "Why was Y null", or "Why did thread 3 execute line 1234" until eventually you got something that made sense. 

Or imagine if you could ask it "Why is the application spinning?", and it could tell you "because it is deadlocked" and then do the lock analysis for you. Or it may say "because it is live-locked", and explain that thread 2 is stuck in an infinite loop, and you can ask why the loop exit condition is never met, and so on ....

This is called Omniscient debugging, and there is some cool research in the area, and even some academic prototypes floating around. I hope someday VS will have features like this (and I say this without any knowledge of VS's future feature set, so don't think I'm implying something here). At least doing it on Sudokus gives you a preview for how great it will be when you can eventually do stuff like this while debugging in Visual Studio.

Comments (4)

  1. Rolf Huisman says:

    This kind of behavior for a debugger is more in line with a validator. Validators like state explorers give a complete deduction wy something happens that way.

  2. Mike says:

    hrm… too bad it’s not open source, i would like to build off of that for my puzzle generator… it would help my program to better understand complexity for humans and thus allow me to fine tune my puzzles for difficulty.

Skip to main content