Talk:Solve a Hidato puzzle: Difference between revisions
→On the algebra of Hidato and Knights's Tour
Line 147:
== On the algebra of Hidato and Knights's Tour ==
To clarify that the problem is mathmatically well understood lets consider Evil case 1. In the general case for
<pre>
a
b c d
e f g
</pre>
The problem is to find a solution for the following simultaneous equations:
<pre>
a1 .. g7 are binary variables.
a = a1*1 + a2*2 + a3*3 + a4*4 + a5*5 + a6*6 + a7*7
...
g = g1*1 + g2*2 + g3*3 + g4*4 + g5*5 + g6*6 + g7*7
a1 + a2 + a3 + a4 + a5 + a6 + a7 = 1
...
g1 + g2 + g3 + g4 + g5 + g6 + g7 = 1
a1 + b1 + c1 + d1 + e1 + f1 + g1 = 1
...
a7 + b7 + c7 + d7 + e7 + f7 + g7 = 1
b2 + c2 + d2 = a1
...
b7 + c7 + d7 = a6
a2 + c2 + e2 + f2 = b1
...
a7 + c7 + e7 + f7 = b6
a2 + b2 + d2 + e2 + f2 + g2 = c1
...
a7 + b7 + d7 + e7 + f7 + g7 = c6
a2 + c2 + f2 + g2 = d1
...
a7 + c7 + f7 + g7 = d6
b2 + c2 + f2 = e1
...
b7 + c7 + f7 = e6
b2 + c2 + d2 + e2 + g2 = f1
...
b7 + c7 + d7 + e7 + g7 = f6
c2 + d2 + f2 = g2
...
c7 + d7 + f7 = g6
</pre>
In the particular case:
<pre>
4
b 7 d
1 f g
</pre>
Which for this simple case can be resolved by inspection to:
<pre>
b = b2*2 + b3*3
d = d3*3 + d5*5
f = f2*2 + f6*6
g = g3*3 + g6*6
b3 + d3 = 1
b5 + d5 = 1
b2 + f2 = 1
b6 + d6 + f6 + g6 = 1
b3 + b5 = 1
d3 + d5 = 1
f2 + f6 = 1
g6 = 1
</pre>
Putting g6 into the model and resolving again solves the problem by hand.
It is apparent that the number of equations increases rapidly with probem size. A method exists which makes this increase linear see http://en.wikipedia.org/wiki/Tseitin-Transformation.
| |||