Talk:Solve a Hidato puzzle: Difference between revisions
Content added Content deleted
Line 147: | Line 147: | ||
== On the algebra of Hidato and Knights's Tour == |
== 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. |