Comments (4)
  • Add a Comment
  • Edit
  • More Actions v
  • Quarantine this Entry

1 cumthsc commented Permalink

I take your point, but it does seem to take the fun out of puzzles like this to solve them by machine (at least once one has created the formulation--that in itself is fun, but just the first time). With a suitable CP or IP formulation, any properly constructed Sudoku is trivial for a machine. Once all the variables corresponding to cells with printed values are fixed and the formulation reduced accordingly, the cardinality of the solution set is precisely one.

 
The details of Inkala's assessment method aren't apparent, but the basic idea is this: what people do when solving these problems by hand amounts to constraint propagation, but with a subset of constraints with the property that the effects are tractable for human perception. (See, e.g., http://www.ams.org/notices/200904/tx090400460p.pdf.) For example, in this puzzle, the 8 in column 1, block 1 and the 8 in column 3, block 7 ensure that the 8 in block 4 must appear in column 2. The complexity measure essentially walks through a number of these manual constraint propagation rules and eliminates puzzle instances for which each such rule forces a variable to be fixed. So if column 2 had a printed value in row 5, the 8 would have to appear in row 6. Such a problem would be eliminated by the difficulty assessor.
 
Of course, in practical applications, the point is not to create a mental challenge for the problem solver for every instance--it's to save companies millions of dollars. The challenge in that case is to construct an appropriate model. If the appropriate model is easy to solve by machine, so much the better.

2 JeanFrancoisPuget commented Permalink

I fully agree. I think I could instrument our CP solver to report the number of constraint propagation steps required to solve the problem. Would that be consistent with perceived difficulty of problems? I don't know. But that's an interesting way of looking at it.

3 IrvLustig commented Permalink

One way of measuring the difficulty of a sudoku puzzle is to see if branching is required to solve the puzzle in either the CP and/or MIP formulation. For many puzzles, the CP optimizer can solve the problem just via constraint propagation and domain reduction, without branching, and the MIP optimizer can solve the problem in presolve, without requiring the solution of any LP relaxations. For the given puzzle above, branching is required in both cases in order to solve the problem, which in some sense indicates that a human may need to do some form of "branching" in order to find a solution.

4 JeanFrancoisPuget commented Permalink

Irv, I agree. It is how I interpreted Inkala's way of assessing hardness in the first place: search space size.