JAVA course assignment impasse

TarfHead · 13-04-2015 5:48pm #1

I am working on an assignment for a Java course and have hit a wall. I believe I know how the solution should work, but cannot see a way to express it as an algorithm. I believe the best solution will be recursive, similar to the Tower of Hanoi example, but cannot apply that solution to this assignment. My proficiency with recursion is basic

. Very basic

.

A pegboard is given with 11 holes. The first 5 are contain black pegs, the 6th hole is empty, and the next 5 are white. The end state is to swap the black pegs from positions 1 through 5, to positions 7 through 11, with the white going in the opposite direction. A peg may be moved to the empty hole if it is adjacent, or if there is one peg between it and the empty hole.

I believe I should be able to represent this as an Array, and solve it using an algorithm. The solution should be scalable, i.e. should work for many number of holes, i.e. 3, 5, 7, etc.

To illustrate, a 5 hole board could be solved as;

[B] [B] [ ] [W] [W]
[B] [B] [W] [ ] [W]
[B] [ ] [W] [B] [W]
[ ] [B] [W] [B] [W]
[W] [B] [ ] [B] [W]
[W] [B] [W] [B] [ ]
[W] [B] [W] [ ] [B]
[W] [ ] [W] [B] [B]
[W] [W] [ ] [B] [B]

I have mapped out similar solutions for 7 and 9 holes boards, can see a pattern, but cannot see how to generate it based on the size of the board.

To repeat, this is a course assignment, and I am not looking to be handed a solution. What I hope is that someone could point me in the right direction. I know this can be solved iteratively, as a mate has done so, and that it can be done recursively.

Thanks

TarfHead · 25-04-2015 11:52am

Over 450 views and no replies.

Just wondering is it because it was for a college assignment, and asking such questions is frowned upon ?

Assignment was handed in on Thursday, so the original question is now moot.

colm_c · 25-04-2015 12:35pm

Generally you should post some code and let people know what issues you're having.

Even if it's sudo code and not java.

Talisman · 25-04-2015 4:57pm

Did you solve it? It looks like you only need a few simple steps to complete it.

Step 1 : Find the space.
Step 2 : Choose an element to the left or right.
Step 3 : Move the element as far as possible to the opposite side.
Step 4 : Choose the element on the other side of the space.
Step 5 : Go to Step 3.

TarfHead · 27-04-2015 5:31pm

Thanks for those replies.

My intention was to be able to generate a sequence of moves, dependent on the number of holes in the pegboard. There is, for each (uneven) number of holes, a minimum number of moves, so I was looking to generate that sequence.

For example, for a 3 hole board, the minimum number of moves is 3, in the sequence +1,-2, +1, where +1 means move the empty hole one space right, -2 means move it 2 holes to the left.

For a 5 hole board, the minimum number of moves is 8, in the sequence +1, -2, -1, +2, +2, -1, -2, +1.

For a 7 hole board, the minimum number of moves is 15. The first 4 values in this sequence are the same as the first 4 in the 5-hole sequence, and the last 4 values in the sequence are the same as the last 4 in the 5-hole sequence. The 'middle' 7 values in the sequence are +2, +1, -2, -2, -2, +1, +2.

Many others in the class were able to figure it out, some managed it recursively.

JAVA course assignment impasse

Comments