Conference rusure::math

1034.0. "More fun with beads and poles" by 4GL::GILBERT (Ownership Obligates) Tue Feb 28 1989 13:10

	Consider a child's abacus, with balls of n colours sliding on n+1
poles each capable of holding n+1 balls.  Start with n horizontal stripes
of n+1 balls, and move one ball at a time from one pole to another on which
there is room, to the rotated position in which n poles are full of balls of
one colour.  Eg, for n == 4 and Red, Green, Yellow and Blue balls, you have
to get from
 
      |	    |	  |	|     |		      [R|R] [G|G] [Y|Y] [B|B]	|
    [B|B] [B|B] [B|B] [B|B] [B|B]	      [R|R] [G|G] [Y|Y] [B|B]	|
    [Y|Y] [Y|Y] [Y|Y] [Y|Y] [Y|Y]    to	      [R|R] [G|G] [Y|Y] [B|B]	|
    [G|G] [G|G] [G|G] [G|G] [G|G]	      [R|R] [G|G] [Y|Y] [B|B]	|
    [R|R] [R|R] [R|R] [R|R] [R|R]	      [R|R] [G|G] [Y|Y] [B|B]	|
    -----------------------------	      -----------------------------.
 
How many moves are needed?  For n == 1, 2, 3, 4 the answer appears to be
1, 7, 17, 31 resp., suggesting that the answer is 2 n^2 - 1;  but for n == 5,
we haven't yet improved on 50.  There is an obvious O(n^3) algorithm, in
which each ball in turn is manoeuvred to the right place, but an O(n^2)
algorithm isn't quite so apparent.
 
	Generalisations to n+p poles of size n+q, q >= p >= 1, left as an
exercise for the reader.
 
	Any ideas?  There are obvious similarities with Towers of Hanoi,
with the 14-15 puzzle, and with the matrix rotation puzzle, but the theory
doesn't seem to carry over.  Is this a "new" problem?  [Surely not!  But
my colleague's informant claimed to have thought of it himself.]
 
-- 
Andy Walker, Maths Dept., Nott'm Univ., UK.
[email protected]

Newsgroups: sci.math
Path: decwrl!ucbvax!agate!helios.ee.lbl.gov!ncis.llnl.gov!lll-winken!uunet!mcvax!ukc!dcl-cs!nott-cs!anw
Subject: Abacus rotation
Posted: 20 Jan 89 15:17:37 GMT
Organization: Department of Mathematics, The University, NOTTINGHAM, NG7 2RD, UK.

    With an upper limit of 50 moves, this looks to be something that can be
    solved by a backtracking programming language.  Possibly with a bit of
    help from the Easynet...
    
      John

    Re .1:
    
    A depth of 50 moves, with only two choices on each move, is 2^50
    possibilities.  That's about a quadrillion.  How do we detect errant
    paths early?
    
    
    				-- edp

     re .2    How do we detect errant paths early?
     
     Rule 1)  Do not undo the move just made.
     
     Dan

    There are several thousand loops involving only the Blue beads.
    I think you will have better luck with a Finite State Machine approach.
    
    Lynn 

>    A depth of 50 moves, with only two choices on each move, is 2^50
>    possibilities.  That's about a quadrillion.  How do we detect errant
>    paths early?
    
    A chess model does not seem all that farfetched.  To wit:  generate
    all possible moves of 10 steps (or 8 or 5 or ...) and evaluate the
    top N "most promising".  One could try a simple evaluation function,
    such as 5 points for every bead correctly placed at the base, 4 for
    every one correctly placed on top of that, etc.  There are many such
    evaluations.  By solving the smaller problems manually, you can make
    a stab at how to evaluate a position.
    
    Once the "top N" have been selected, one repeats the process and comes
    up with the most promising after 20 steps (or 16 or 10 or ...), etc.,
    until you've gone past 50 steps.
    
    If no good solution is found after 50 steps you re-examine your
    evaluation functions and try to come up with one that works better.
    
      John