Anonymous user
Talk:Solve a Hidato puzzle: Difference between revisions
→Any good general algorithm?
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]]
| |||