-----------------------------------

A.J

Tue Jan 29, 2008 4:32 pm


Tower of Hanoi

-----------------------------------

I was thinking of holding a contest to see the most efficient tower of hanoi solver program (that outputs every move and states the number of moves) 
I finished it in turing in 13 lines, but I am pretty sure there are shorter and better ways to do it than what I did


-----------------------------------

MichaelM

Tue Jan 29, 2008 4:43 pm


Re: Tower of Hanoi

-----------------------------------

Well theres always wikipedia for an answer: http://en.wikipedia.org/wiki/Tower_of_Hanoi


-----------------------------------

zylum

Tue Jan 29, 2008 5:27 pm


RE:Tower of Hanoi

-----------------------------------

var i := 1
proc hanoi (n, f, t, u : int)
    if n > 0 then
        hanoi (n - 1, f, u, t)
        put "move ", i, ": ", f, " to ", t
        i += 1
        hanoi (n - 1, u, t, f)
    end if
end hanoi
hanoi (6, 1, 3, 2)

Straight from the wiki page..


-----------------------------------

A.J

Wed Jan 30, 2008 6:52 pm


Re: Tower of Hanoi

-----------------------------------

OOps!! 
i completely forgot about wikipedia

thanks for reminding me guys!!!

how about a sliding puzzle program puzzle???

I am currently trying to learn the heuristic method of solving it
if anyone who is reading this right now is able to help me, please write out an example in turing (i also have a topic on the turing help forum about this)

thanks a LOT


-----------------------------------

klopyrev

Fri Feb 01, 2008 4:43 pm


Re: Tower of Hanoi

-----------------------------------

Are you talking about the 15 puzzle?


-----------------------------------

A.J

Fri Feb 01, 2008 5:10 pm


Re: Tower of Hanoi

-----------------------------------

yes, but in this case it can be any defined size (hence the name n-puzzle)
if you can help me with the heuristic part, I'll be thankful (check out the turing help forum, 'Help neede regarding heuristic algorithms', or something like that)


-----------------------------------

klopyrev

Fri Feb 01, 2008 6:11 pm


Re: Tower of Hanoi

-----------------------------------

The 8 puzzle can be solved without using heuristics. However, the 15 puzzle can't. There are too many states. One of the heuristics I know of and have successfully used to solve the problem is sum of the distances of each of the pieces to their needed positions. If you need help with the actual algorithm, consider this:

http://en.wikipedia.org/wiki/A%2A


-----------------------------------

A.J

Sat Feb 02, 2008 10:41 am


Re: Tower of Hanoi

-----------------------------------

how do you assign each node the g(n) without visiting it ? (since it is the distance from the beginning node to that node)


-----------------------------------

Sane

Mon Mar 31, 2008 5:25 pm


Re: Tower of Hanoi

-----------------------------------

You guys might be interested to hear that this was the S5 question in Hong Kong's CCC for 2008:
http://www.cs.hku.hk/ccc2008/questions/Senior08.pdf

The only difference is it uses 4 polls instead of 3, which turns it into a very different problem. This problem is sometimes called "Reve's puzzle".

The official solution offered by Hong Kong's CCC is here:
http://www.cs.hku.hk/ccc2008/questions/Senior08_sol.zip

The funny thing is, according to Wikipedia, the CCC's official solution has not yet been proven to be optimal.

A solution for four (or more) pegs, which has not been proved to be optimal, is described below:

...

For some 1