Anonymous user
Talk:Solve a Hidato puzzle: Difference between revisions
m
→solved it using constraint programming
| (25 intermediate revisions by 6 users not shown) | |||
Line 84:
:::Exponential increase is bad when you increase the problems size, so we avoid it --[[User:Nigel Galloway|Nigel Galloway]] 13:47, 5 May 2012 (UTC)
:::I have added an example in Ruby which shows that no time problem exists if the path length between hints is reasonable. The new C version could check the length of the path it is looking for and not adopt the new strategy if it is reasonably short, hence not slowing down normal puzzles.--[[User:Nigel Galloway|Nigel Galloway]] 13:26, 5 May 2012 (UTC)
:::: Even though I noted about slowdowns at the front of the C code, I'm not really all that concerned about it. The code uses a flood fill to check connectivity, which is O(n) because there's no backtracking, n being number of cells. For puzzles that are simple (i.e. brute force would have been more on the polynomial side without this check), it adds another polynomial term to run time, which could be relatively big but in absolute terms is not an issue (you can't see, but I'm making violent handwaving gesture here). The 3x3 example requires 8 tries at filling cells with or without the checks, so it's definitely faster without, but it won't be noticeable. For exponentially backtracking puzzles, the hope is it will kill off some (most?) long fruitless searches early (without check, the 50x3 example tries to fill values to cells 27962062 times before finding solution; with it, 85). I could do fancier checks, but not before I see a good example that demands it. --[[User:Ledrug|Ledrug]] 20:10, 5 May 2012 (UTC)
:::The following graph shows an example where if the path 1 2 5 6 etc is chosen, everything thinks it has reasonable connectivity, but they are kidding themselves. Graphs like this have efficient general solutions, they occur for instance in garbage collectors and glpk.--[[User:Nigel Galloway|Nigel Galloway]] 13:26, 5 May 2012 (UTC)
[[File:Snake2.PNG|centerHidato problem]]
Line 97 ⟶ 99:
: Heeey, who you callin' evil?
: I was curious if anyone has a good heuristic method that's reasonably simple and works for most cases, like the one used in knight's tour, but I guess it's a bit asking for much. It's just that a task with only an exponential brute force general solution is somewhat disappointing -- oh well. --[[User:Ledrug|Ledrug]] 11:35, 3 May 2012 (UTC)
:: “Evil” is actually quite complimentary.
:: The reason this is [[wp:NP-complete|hard]] is that it is really the finding of a [[wp:Hamiltonian path|Hamiltonian path]] (on a graph with a bound on the number of links per node); you just add in a (possibly non-planar) link between start and finish to see that this must be the case. I don't really feel like putting lots of effort into cracking very hard problems like this other than by simple brute force. Moreover, because it ''is'' finding a Hamiltonian path, there must be cases which are not easy for either computers or humans to solve. (Do I know what they are? No, but an easy solution to arbitrary Hidato would have tremendous application to many other problems like cryptography.)
:: (I'd have written about this earlier, but there's some kind of weird proxy stopping me from posting to RC from home.) –[[User:Dkf|Donal Fellows]] 16:33, 6 May 2012 (UTC)
::: I'm not sure Hidato is really equiv to a general Hamiltioian path problem -- is it known to be NP-complete? Hidato is much more constrained in that it has a unique solution requirement; its nodes can have only up to eight neighbors; and more importantly, spatial proximity between nodes are tightly related to the connectivity between them. Although I do agree that if a problem isn't mathematically well understood (as in, having a known effective algorithm), it's generally not worth putting too much effort into it. --[[User:Ledrug|Ledrug]] 17:49, 6 May 2012 (UTC)
:::: I'm also not ''sure'' that is HP, but the suspicion remains. I couldn't find anything in WP on requirements on connectivity for graphs doing HP; maybe there is something, but I couldn't find it. (Graph theory isn't my specialty, not at all.) –[[User:Dkf|Donal Fellows]] 08:55, 7 May 2012 (UTC)
== Short C version ==
Line 119 ⟶ 126:
For the computer cell 2 must complain when it becomes orphaned and prevent that selection asap.
--[[User:Nigel Galloway|Nigel Galloway]] 15:36, 4 May 2012 (UTC)
== On the application of Warnsdorff to Hidato ==
This task's origional premise was that the Knights Tour and Hidato are the same problem requiring only a change of adjacency list.
Normal Hidato are simpler than the Knight's Tour. But considering that Mathprog can solve the Knight's Tour without being commited to Intensive Care for emergency minisat due to induced numerical instability, we must conclude that it is possible to create Hidato's more difficult than Knight's Tours.
If they are the same problem then that which is truth for Knigh't Tour is truth for Hidato. Therfore it seems appropriate to Warnsorff Hidato.
Evil1 and the task's example indicate this does little harm (if only C programmers trained as doctors!). And now we snake it in 16 hunredths of a second.
Finally can we also do the Knight's Tour?
: Warnsdorf is truth for Knight's Tour, but it's not truth for Hidato, hence they are not the same problem (your logic). Warnsdorff this:
1 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 82
-1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1
-1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1 0 -1 0 -1 -1
0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 -1
:--[[User:Ledrug|Ledrug]] 17:29, 6 May 2012 (UTC)
== 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 problem size. A method exists which makes this increase linear see http://en.wikipedia.org/wiki/Tseitin-Transformation.
--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 14:12, 30 December 2013 (UTC)
: if a1 = 0, the equation b2 + c2 + d2 = a1 means "Non of a's neighbors is 2" which is not necessarily true. so this solution does not work. --[[User:Ak|Ak]] ([[User talk:Ak|talk]]) 17:10, 21 March 2014 (UTC)
==extra credit suggestion==
How about adding an extra credit for this task: support Numbrix puzzles as well as Hidato puzzles. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 04:50, 18 December 2013 (UTC)
The REXX programming example only needed a couple of '''if''' statements to solve Numbrix puzzles in addition to Hidato puzzles. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 04:50, 18 December 2013 (UTC)
::Two points. First I think it would be better to add a related task Solve Numbrix Puzzles. I know what Numbrix is but only from external servlets and the press. Explaining it to them what be's satisfaction would further complicate this task. Secondly I had an extra credit for showing that the same logic could solve the Knight's Tour, but them what be made me remove it. The Knight's Tour is exactly the same as Hidato, only the Knight has a different view of which cells are adjacent. Numbrix has only 4 adjacent cells whereas Knight's Tour and Hidato have 8.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 13:35, 30 December 2013 (UTC)
::: Numbrix puzzles (in my thinking) are just a simpler Hidato puzzle, in the manner of having less possible moves (i.e., being more restrictive). But I have no qualms of someone creating a Rosetta Code task just for Numbrix puzzles. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 16:20, 30 December 2013 (UTC)
::: As regarding the Knights Tour: in fact, I used the same code in the REXX example, I just tweaked/optimized the code a bit for speed. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 16:20, 30 December 2013 (UTC)
== solved it using constraint programming ==
Behold: http://hidoku-solver.appspot.com/
| |||