teez brainbuster

[GENE SIMON HUH]

Dear puzzlers,

I have a puzzle at my house called "Teez Brainbuster". It consists of
nine holes in a block of plastic, all lined up. The initial setup of the
puzzle consists of four blue pegs in holes #1 thru #4 and four red pegs in
holes #6 thru #9, like this:

B B B B O R R R R

where B = blue peg
R = red peg
and O = empty hole

The object is to switch the positions of the blue and red pegs, i.e.,

R R R R O B B B B

The allowable moves are:
a) move one blue peg into an adjacent empty hole
b) move one red peg into an adjacent empty hole
c) a peg may "jump" over one (and only one) peg of either color, provided
that the hole that the peg "jumps" into is empty
d) blue pegs can only be moved to the right; red pegs can only be moved to
the left

The solution is NOT to turn the plastic block around 180 degrees. :-)

Normally I'm all right at puzzles, but I can't figure this one out. I
didn't see it in the FAQ, so here it is. Has anybody got the solution handy?
If so, are my rules (for allowable moves) incorrect?

Thanks in advance,

Gene Huh
h...@wccf.mit.edu or huh@mitwccf

[Spyros Potamianos]

A small C program revealed the following 2 answers:
bRrBBbRRRrBBBBrRRRbBBrRb
rBbRRrBBBbRRRRbBBBrRRbBr
where r/b means "move a red/blue peg in an adjacent empty hole"
and R/B means "a red/blue peg jumps over another peg to land on the empty
hole". As you can see the solutions are symmetrical, palindromes,
and remain so even if you change the size of the board.
If you have a board with 2*N+1 holes, N red and N blue pegs,
the answer will be:
b
Rr
BBb
RRRr
......
BBBB....B (N times)
......
rRRR
bBB
rR
b

I tried to for a more "theoretical" analysis, but I had no luck.
The only interesting things I could find was that this solution
is "greedy" (moving a peg by 2 holes (i.e. jumping) is always better
than a plain move to the adjacent empty hole)
The other interesting thing is that near the middle of these moves you will
end up with the board looking like:
BRBRBRBRO
(this is where you do these 4 'B's). From that point on all your moves
are forced (if you take into account that you must always "jump" if you
can) and a mirror image of your previous moves.

Spyros Potamianos
pota...@hpl.hp.com

[David G Radcliffe]

Here's another way of thinking of the puzzle.
You start with a string of O's, R's, and B's.
You are allowed to do the following transformations:

1. BOR ---> OBR
2. BOR ---> BRO
3. BRO ---> ORB
4. OBR ---> RBO

The problem is then to transform (B^n)O(R^n) to (R^n)O(B^n).

I think a proof by induction will work here, but I haven't worked it out.

--
David Radcliffe
radc...@csd4.csd.uwm.edu

[Richard Harter]

In article <11OCT199...@wccf.mit.edu> h...@wccf.mit.edu (GENE SIMON HUH) writes:
>Dear puzzlers,

> I have a puzzle at my house called "Teez Brainbuster". It consists of
>nine holes in a block of plastic, all lined up. The initial setup of the
>puzzle consists of four blue pegs in holes #1 thru #4 and four red pegs in
>holes #6 thru #9, like this:

> B B B B O R R R R

>where B = blue peg
> R = red peg
> and O = empty hole

>The object is to switch the positions of the blue and red pegs, i.e.,

> R R R R O B B B B

>The allowable moves are:
> a) move one blue peg into an adjacent empty hole
> b) move one red peg into an adjacent empty hole
> c) a peg may "jump" over one (and only one) peg of either color, provided
>that the hole that the peg "jumps" into is empty
> d) blue pegs can only be moved to the right; red pegs can only be moved to
>the left

> The solution is NOT to turn the plastic block around 180 degrees. :-)

I cheated and wrote a quick program to solve the puzzle. There are
two solutions, which are symmetrical with respect to read and blue.
The solutions are:

A: 4 6 7 5 3 2 4 6 8 9 7 5 3 1 2 4 6 8 7 5 3 4 6 5
B: 6 4 3 5 7 8 6 4 2 1 3 5 7 9 8 6 4 2 3 5 7 6 4 5

In the above solutions the peg positions are 1 through 9 with the empty
hole initially in hole 5. Each number in a solution series is the number
of the peg that that moves into the empty hole. For example, in line A
the first four moves are:
Blue peg in hole 4 moves right to hole 5
Red peg in hole 6 jumps left to hole 4
Red peg in hole 7 moves left to hole 6
Blue peg in hole 5 jumps right to hole 7
....

Nice puzzle.
--
Richard Harter: SMDS Inc. Net address: r...@smds.com Phone: 508-369-7398
US Mail: SMDS Inc., PO Box 555, Concord MA 01742. Fax: 508-369-8272
In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.