Can the Dancing Links implementation of Knuth's Algorithm X be used to solve this CSP? In this game the first and last number are always already in the board and I belive there's only one solution to each well formulated problem.
A:
No.
A constraint solver could certainly solve this kind of problem, but it seems unlikely to be the fastest way to do it. Offhand it seems like it would be hard to tell the solver "the path can't cross itself", which is a useful hint.
Jason Orendorff
2009-11-30 17:10:49
+1
A:
Yes.
Suppose we want to solve this Hidato:
+---+ +---+
| | | 6 |
+---+---+---+
| | |
+---+---+
| 1 | |
+---+---+
First, let's name the empty cells with the letters a, b, c, d:
+---+ +---+
| d | | 6 |
+---+---+---+
| b | c |
+---+---+
| 1 | a |
+---+---+
We need to express 3 kinds of constraints for each solution line of the X Algorithm:
- A number is used (so that the same number is not used twice)
- A cell is used (so that the same cell is not used twice)
- The next cell is constrained (so that the next cell can only be chosen among adjacent ones). This last constraint does not require exact cover, so it should only be used as secondary columns in DLX terminology.
The resulting problem matrix is then:
1 2 3 4 5 6 a b c d 2a 2b 2c 2d 3a 3b 3c 3d 4a 4b 4c 4d 5a 5b 5c 5d
1 1
1 1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1 1
1 1 1
1 1 1
1 1 1 1
1 1 1
Where, for example, the second line (without counting the title line) can be read as: this line sets number 2 (first 1) in cell a (second 1). It is also constrained by the 2a light constraint. And it also constrains 3 not to be on 3a and 3d, because they are not adjacent to cell a.
All the lines read this way, except:
- The first line which only states constraints on number 2.
- The 5 lines (4 last ones), which also embed the constraint for being adjacent to 6.
The implementation is left as an exercise for the reader...
Jerome
2009-12-02 17:18:49