How can I reduce this problem to the Tower of Hanoi (or solve it in the least number of iterations)?

In the optimal solution, no pieces are moved backwards. Thus the total steps is given by n²+2n (proof left to the reader) The solution is fairly simple Move one 0 right. Jump 1x1 over.

Move one 1 left. Jump 2x0 over. Move one 0 right.

Jump 3x1 over. Move one 1 left. Jump 4x0 over.

Move one 0 right. ... (assumes n is even. For odd, switch 0/1 and L/R) Jump nx0 over.

Move one 1 left. Jump n-1x1 over. Move one 0 right.

Jump n-2x0 over. ... Move one 1 left. Jump 1x1 over.

Move one 0 right Here's the solution for n=4 for example 0000_1111 000_01111 #1 00010_111 #2 000101_11 #3 0001_1011 #4 00_101011 #5 0_0101011 #6 010_01011 #7 01010_011 #8 0101010_1 #9 01010101_ #10 010101_10 #11 0101_1010 #12 01_101010 #13 _10101010 #14 1_0101010 #15 110_01010 #16 11010_010 #17 1101010_0 #18 110101_110 #19 1101_1000 #20 11_101000 #21 111_01000 #22 11110_000 #23 1101_112 #24.

In the optimal solution, no pieces are moved backwards. Thus the total steps is given by n²+2n (proof left to the reader). The solution is fairly simple.

Move one 0 right. Jump 1x1 over. Move one 1 left.

Jump 2x0 over. Move one 0 right. Jump 3x1 over.

Move one 1 left. Jump 4x0 over. Move one 0 right.... (assumes n is even.

For odd, switch 0/1 and L/R) Jump nx0 over. Move one 1 left. Jump n-1x1 over.

Move one 0 right. Jump n-2x0 over.... Move one 1 left. Jump 1x1 over.

Move one 0 right. Here's the solution for n=4 for example. 0000_1111 000_01111 #1 00010_111 #2 000101_11 #3 0001_1011 #4 00_101011 #5 0_0101011 #6 010_01011 #7 01010_011 #8 0101010_1 #9 01010101_ #10 010101_10 #11 0101_1010 #12 01_101010 #13 _10101010 #14 1_0101010 #15 110_01010 #16 11010_010 #17 1101010_0 #18 110101_110 #19 1101_1000 #20 11_101000 #21 111_01000 #22 11110_000 #23 1101_112 #24.

1 Please don't hand solutions to homework problems on a platter. – Aryabhatta Jul 12 '10 at 6:07.

I've played this game before in several places. For instance, there is an example in the game Machinarium by Amanita Design. But I don't see where you came up with the idea that it reduces to the Tower of Hanoi.It's true that it requires lateral thought - going left to get right - in order to solve, but that doesn't mean an algorithm for solving one game will also solve the other.

This is a search problem. There are only a finite number of board states you can have, and you are searching for the one that maximizes some value (specifically, number of black pegs on the left and number of white pegs on the right). I'm going to give you some useful terms to look up.

For small problems (or big problems with relatively fast hardware), a Breadth-First-Search (BFS) might be an appropriate way to solve. This has the advantage of guaranteeing you get the minimal-depth solution (in other words, the one with the fewest moves). If higher performance (lower time for your solver to run) is a concern, implementing A-Star Search might get you an answer faster.

Make sure to implement pruning to avoid searching the same subtree multiple times (or getting into an infinite loop, although that cannot happen with BFS). To implement a search, the steps you should follow are (vaguely): Come up with an internal representation of your board Write a function that will return all possible moves given a certain board Start with a list ("to_check") containing only the initial state While the to_check list is not empty, take its first element ("cur_board"), see if it is a solution, and if not, insert all the boards that result from making one move from cur_board (keeping a history of moves made with each board). Where you insert these subsequent boards into to_check, and in what order, determines what type of search you will be performing.

This will keep going until either your to_check list is empty (which won't happen in this game if you correctly implemented everything - there are no unsolvable initial states! ) or you find the solution. If you have too much difficulty writing the above algorithm, it might be easier to write a recursive one.

But, honestly, I'd recommend against it; it's easy to do Depth-First Search with recursion but it makes it much harder to change to another algorithm. Also, a recursive version is limited by your stack size. If and only if your search takes too long to run (or you love a challenge), you can make it better by making it look at "likely" boards first.

In other words, make it like a human player, who explores promising possibilities and only looks at less-promising ones when desperate. In this case, this means you have a heuristic which prioritizes boards more likely to "win". A greedy heuristic would always try to get as many black pegs to the left of white pegs as possible.

But many different heuristics are possible, and which one is best is for you to evaluate.

It seems to me that arbitrary search is gonna take a lot longer than finding a straight forward way to solve it. The ordering of the steps in the solution is deterministic, so I don't think what you're suggesting is necessary or would be the optimal solution. I'm not sure if it can be reduced to the tower of hanoi though, I just thought it seemed similar – it prints money Jul 12 '10 at 4:48 @it prints money: Writing a search-based solver takes a matter of minutes, once you know how to write one.

When you come across another search problem (of which there are many, many, many examples), you will be able to write a solver for that problem in a few more minutes. Finding a domain-specific solution can take hours, or days, or weeks - and sometimes, it's not possible. There is such a thing as an unsolvable game.

But so long as your space is finite and you can know when you have a solution, a search program will always work. – Borealid Jul 12 '10 at 4:52 @it prints money: About the "optimal solution": in general, what we are interested in is the optimality of the solver's output, not the run time of the solver itself. A BFS will produce an optimal solution for this game.It might not run as quickly as a domain-specific solver, but its answers are just as good.

– Borealid Jul 12 '10 at 4:53 you don't understand. I don't need to implement a solution to the problem, I need to find the most efficient answer to this because it is an exercise. Anything that takes longer than the necessary minimum won't be accepted.

If I was just looking to solve the problem your solution would be fine. But that isn't the case. I don't agree to those terms mind you - I think I should just need to solve it normally, but I can't argue with the teacher – it prints money Jul 12 '10 at 4:54 @it prints money: all right then, here's your magic: never put two pegs of the same color next to each other unless they are already on the "destination" side of all pegs of the opposite color.

Try to get the white and black pegs interspersed. Then zipper them through. – Borealid Jul 12 '10 at 5:03.

For the future, remember: you don't reduce a problem to a known solution, you reduce a known solution to your problem.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.