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

Question

Suppose there are 2n+1 holes and 2 sets of n sticks, one set white and another black.

The sticks are initially organized so that the white sticks are left, there is a hole in the middle and the black sticks are right.

A stick can move by either:
1) being placed on the hole next to it, if empty
2) jump the neighboring stick iff the neighbor stick is of different color and the next hole is empty

Find an algorithm that minimizes the number of movements to switch the sides of all sticks.

Here's some examples I've done - not sure if they're optimal though.

1. 0_1
2. 01_
3. _10
4. 1_0

1. 00_11
2. 0_011
3. 010_1
4. 01_01
5. 0110_
6. 011_0
7. 01_10
8. _1010
9. 1_010
10. 110_0
11. 11_00

1. 000_111
2. 00_0111
3. 0010_11
4. 001_011
5. 00110_1
6. 0011_01
7. 001_101
8. 0_10101
9. 01_0101
10. 0110_01
11. 011010_
12. 01101_0
13. 011_100
14. 01_1100
15. _101100
16. 1_01100
17. 110_100
18. 11_0100
19. 111_000

1. 0000_1111
2. 000_01111
3. 0001_0111
4. 00_100111
5. 001_00111
6. 0010_0111
7. 001010_11
8. 00101_011
9. 001_10011
10. 0011_0011
11. 001_10011
12. 0_1010011
13. 01_010011
14. 0110_0011
15. 01100_011
16. 0110010_1
17. 011001_01
18. 0110_1001
19. 01101_001
20. 011_10001
21. 0111_0001
22. 011_10001
23. 01_110001
24. _10110001
25. 1_0110001
26. 110_10001
27. 11_010001
28. 1110_0001
29. 11100_001
30. 111000_01
31. 11100010_
32. 1110001_0
33. 11100_100
34. 1110_0100
35. 111010_00
36. 11101_000
37. 111_10000
38. 1111_0000

It seems to me this is the Tower of Hanoi disguised, but I'm not really sure how to do the mapping/conversion and write the algorithm. Any ideas?

Assuming this thing isn't the tower of hanoi, would the best approach be to solve it little by litte? ie 0000_1111 -> 0001_0111 -> 0011_0011 -> etc.

Answer 1

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.

Answer 2

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_00 #19
1101_1000 #20
11_101000 #21
111_01000 #22
11110_000 #23
1111_0000 #24

Answer 3

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