You have a 9 square horizontial board.  On the first four boxes on the
left you have tokens marked "A" and on the last four boxes you have
tokens marked "B." This means there is an empty square in the middle.

________________________________________________________________

A       |         A        |         A         |        A       |     
            |           B    |      B    |      B   |     B    |

________________________________________________________________

The object of the puzzle is to move the "A" tokens to the "B" chips
position, and vice versa, using only two types of moves: slides and
jumps.

Slide -- A move of one square to the right for A or to the left for B.
 You must end up in an empty square.

Jump -- A move in which A moves to the right by jumping over one B and
lands on an empty square or B moves to the left by jumping over one A
and landing on an empty square.

Restrictions:  You can NOT move backwards.  So "A" cannot move left or
B cannot move right.  You must always land on an empty square.  Two
tokens can not occupy the same square.

QUESTION:  How many total moves does it take for the tokens to change
positions?  What is the sequence of events?

---

Clarification of Question by alexinia-ga on 19 Sep 2004 09:44 PDT

Please cancel this request.  We have the answer.

---

Request for Question Clarification by leapinglizard-ga on 19 Sep 2004 10:56 PDT

Well, I had already done the work. It took me about two hours. The
answer I was about to post is below. Would you consider accepting it?




Dear alexinia,

I solved this problem by writing a Python script that simulates every possible s
equence of moves. If you'd like to run the script, you'll have to download and i
nstall a recent version of the Python interpreter, unless you have one already.

python.org: Download Standard Python Software
http://www.python.org/download/

It turns out that exactly 24 moves are required to swap the a's and b's. There a
re two ways to do so, one of which is the following.

    aaaa bbbb    initial state
    123456789

    aaa abbbb    1. 'a' slides from 4 to 5
    123456789

    aaaba bbb    2. 'b' jumps from 6 to 4
    123456789

    aaabab bb    3. 'b' slides from 7 to 6
    123456789

    aaab babb    4. 'a' jumps from 5 to 7
    123456789

    aa bababb    5. 'a' jumps from 3 to 5
    123456789

    a abababb    6. 'a' slides from 2 to 3
    123456789

    aba ababb    7. 'b' jumps from 4 to 2
    123456789

    ababa abb    8. 'b' jumps from 6 to 4
    123456789

    abababa b    9. 'b' jumps from 8 to 6
    123456789

    abababab     10. 'b' slides from 9 to 8
    123456789

    ababab ba    11. 'a' jumps from 7 to 9
    123456789

    abab baba    12. 'a' jumps from 5 to 7
    123456789

    ab bababa    13. 'a' jumps from 3 to 5
    123456789

     babababa    14. 'a' jumps from 1 to 3
    123456789

    b abababa    15. 'b' slides from 2 to 1
    123456789

    bba ababa    16. 'b' jumps from 4 to 2
    123456789

    bbaba aba    17. 'b' jumps from 6 to 4
    123456789

    bbababa a    18. 'b' jumps from 8 to 6
    123456789

    bbabab aa    19. 'a' slides from 7 to 8
    123456789

    bbab baaa    20. 'a' jumps from 5 to 7
    123456789

    bb babaaa    21. 'a' jumps from 3 to 5
    123456789

    bbb abaaa    22. 'b' slides from 4 to 3
    123456789

    bbbba aaa    23. 'b' jumps from 6 to 4
    123456789

    bbbb aaaa    24. 'a' slides from 5 to 6
    123456789

The Python script follows below.

Cheers,

leapinglizard



#------ begin slider.py
import sys, os, string, re

class Coins:
    def __init__(self, start_state):
        self.start_state = start_state
        self.end_state = ''
        for i in range(len(start_state)-1, -1, -1):
            self.end_state += start_state[i]
        self.best = -1
        self.seek(start_state, 0, [])

    def disp_board(self, board, comment):
        tab = 4*' '
        label = 10*'1234567890'
        print '%s%s%s%s' % (tab, board, tab, comment)
        print '%s%s' % (tab, label[:len(board)])
        print

    def swapped(self, board, a_pos, b_pos):
        if a_pos == b_pos:
            return board
        if a_pos > b_pos:
            (a, b) = (b_pos, a_pos)
        else:
            (a, b) = (a_pos, b_pos)
        ac = board[a]
        bc = board[b]
        return board[:a] + board[b] + board[a+1:b] + board[a] + board[b+1:]

    def seek(self, board, depth, history):
        if board == self.end_state:
            if self.best == -1 or depth < self.best:
                print 'found a solution in %d moves' % depth
                self.best = depth
                board = self.start_state
                self.disp_board(board, 'initial state')
                i = 0
                for code in history:
                    (action, from_pos, to_pos) = code
                    i += 1
                    move = '%d. \'%s\' %ss from %d to %d' % (
                            i, board[from_pos], action, from_pos+1, to_pos+1)
                    board = self.swapped(board, from_pos, to_pos)
                    self.disp_board(board, move)
            return
        for i in range(len(board)):
            c = board[i].lower()
            if c == 'a' and i < len(board)-1 and board[i+1] == ' ':
                self.seek(self.swapped(board, i, i+1), depth+1,
                        history+[('slide', i, i+1)])
            elif c == 'a' and i < len(board)-2 and board[i+1:i+3] == 'b ':
                self.seek(self.swapped(board, i, i+2), depth+1,
                        history+[('jump', i, i+2)])
            elif c == 'b' and i > 0  and board[i-1] == ' ':
                self.seek(self.swapped(board, i, i-1), depth+1,
                        history+[('slide', i, i-1)])
            elif c == 'b' and i > 1 and board[i-2:i] == ' a':
                self.seek(self.swapped(board, i, i-2), depth+1,
                        history+[('jump', i, i-2)])

if __name__ == '__main__':
    Coins('aaaa bbbb')

#------ end slider.py

---

Request for Question Clarification by leapinglizard-ga on 19 Sep 2004 11:00 PDT

Please take into consideration that while I locked the question and
was working on it, I couldn't see your Clarification. This only
appeared when I attempted to post my answer. Please let me know if I
may post the answer officially so that I am compensated for my
efforts.

leapinglizard

---

Clarification of Question by alexinia-ga on 19 Sep 2004 14:44 PDT

I am so sorry.  I should have waited before I posted the question.  I
just had no idea that it would be answered so quickly!  You all are
great.  So, I just want to do what's fair.  I'll let you judge what
you think is right.  This mixup is entirely my fault.  Take out up to
$35 but if you feel that you can accept less I'd greatly appreciate
it.  I won't refute anything you decide.  Just let me know.  Thanks
for your help!

---

Request for Question Clarification by leapinglizard-ga on 19 Sep 2004 16:00 PDT

I'm just a humble Researcher and I have no administrative powers here,
but tell you what. Since you're being reasonable with me, I'll make a
concession to you. If you edit the question price, changing it from
$35 to $20, then I'll officially post the answer I gave in the
Clarification Request above, and you'll be charged the lower fee. I
really would like some compensation for my labor, but I think I would
have tackled your question even at $20. Does this sound like a fair
deal?

leapinglizard

---

Clarification of Question by alexinia-ga on 19 Sep 2004 17:10 PDT

Posted it at $20.  Thank you so much!  All the best.

I'm glad we could work out a compromise. Below is my answer as I
originally intended to post it.




Dear alexinia,

I solved this problem by writing a Python script that simulates every possible
sequence of moves. If you'd like to run the script, you'll have to download and
install a recent version of the Python interpreter, unless you have one already.

python.org: Download Standard Python Software
http://www.python.org/download/

It turns out that exactly 24 moves are required to swap the a's and b's. There a
re two ways to do so, one of which is the following.

    aaaa bbbb    initial state
    123456789

    aaa abbbb    1. 'a' slides from 4 to 5
    123456789

    aaaba bbb    2. 'b' jumps from 6 to 4
    123456789

    aaabab bb    3. 'b' slides from 7 to 6
    123456789

    aaab babb    4. 'a' jumps from 5 to 7
    123456789

    aa bababb    5. 'a' jumps from 3 to 5
    123456789

    a abababb    6. 'a' slides from 2 to 3
    123456789

    aba ababb    7. 'b' jumps from 4 to 2
    123456789

    ababa abb    8. 'b' jumps from 6 to 4
    123456789

    abababa b    9. 'b' jumps from 8 to 6
    123456789

    abababab     10. 'b' slides from 9 to 8
    123456789

    ababab ba    11. 'a' jumps from 7 to 9
    123456789

    abab baba    12. 'a' jumps from 5 to 7
    123456789

    ab bababa    13. 'a' jumps from 3 to 5
    123456789

     babababa    14. 'a' jumps from 1 to 3
    123456789

    b abababa    15. 'b' slides from 2 to 1
    123456789

    bba ababa    16. 'b' jumps from 4 to 2
    123456789

    bbaba aba    17. 'b' jumps from 6 to 4
    123456789

    bbababa a    18. 'b' jumps from 8 to 6
    123456789

    bbabab aa    19. 'a' slides from 7 to 8
    123456789

    bbab baaa    20. 'a' jumps from 5 to 7
    123456789

    bb babaaa    21. 'a' jumps from 3 to 5
    123456789

    bbb abaaa    22. 'b' slides from 4 to 3
    123456789

    bbbba aaa    23. 'b' jumps from 6 to 4
    123456789

    bbbb aaaa    24. 'a' slides from 5 to 6
    123456789

The Python script follows below.

Cheers,

leapinglizard



#------ begin slider.py
import sys, os, string, re

class Coins:
    def __init__(self, start_state):
        self.start_state = start_state
        self.end_state = ''
        for i in range(len(start_state)-1, -1, -1):
            self.end_state += start_state[i]
        self.best = -1
        self.seek(start_state, 0, [])

    def disp_board(self, board, comment):
        tab = 4*' '
        label = 10*'1234567890'
        print '%s%s%s%s' % (tab, board, tab, comment)
        print '%s%s' % (tab, label[:len(board)])
        print

    def swapped(self, board, a_pos, b_pos):
        if a_pos == b_pos:
            return board
        if a_pos > b_pos:
            (a, b) = (b_pos, a_pos)
        else:
            (a, b) = (a_pos, b_pos)
        ac = board[a]
        bc = board[b]
        return board[:a] + board[b] + board[a+1:b] + board[a] + board[b+1:]

    def seek(self, board, depth, history):
        if board == self.end_state:
            if self.best == -1 or depth < self.best:
                print 'found a solution in %d moves' % depth
                self.best = depth
                board = self.start_state
                self.disp_board(board, 'initial state')
                i = 0
                for code in history:
                    (action, from_pos, to_pos) = code
                    i += 1
                    move = '%d. \'%s\' %ss from %d to %d' % (
                            i, board[from_pos], action, from_pos+1, to_pos+1)
                    board = self.swapped(board, from_pos, to_pos)
                    self.disp_board(board, move)
            return
        for i in range(len(board)):
            c = board[i].lower()
            if c == 'a' and i < len(board)-1 and board[i+1] == ' ':
                self.seek(self.swapped(board, i, i+1), depth+1,
                        history+[('slide', i, i+1)])
            elif c == 'a' and i < len(board)-2 and board[i+1:i+3] == 'b ':
                self.seek(self.swapped(board, i, i+2), depth+1,
                        history+[('jump', i, i+2)])
            elif c == 'b' and i > 0  and board[i-1] == ' ':
                self.seek(self.swapped(board, i, i-1), depth+1,
                        history+[('slide', i, i-1)])
            elif c == 'b' and i > 1 and board[i-2:i] == ' a':
                self.seek(self.swapped(board, i, i-2), depth+1,
                        history+[('jump', i, i-2)])

if __name__ == '__main__':
    Coins('aaaa bbbb')

#------ end slider.py

Thanks!!