Re: Recursion problem - Graph theory - Algorithm needed

Discussion in 'C++' started by Allan W, Jan 22, 2004.

  1. Allan W

    Allan W Guest

    "JimC" <> wrote (in comp.lang.c++.moderated):
    > I pose a question here concerning what I think is a classic computer
    > problem, but I don't know of an algorithm for solving it. It resembles
    > the Towers of Hanoi prolem.


    I don't see how.

    > A few matrices follow. In order to make them more easily understood,
    > it would be helpful if the reader can disable proportional spacing,
    > although this is not essential.


    Not helpful at all, the way you originally formatted it.

    > Here is the problem.

    [He describes the classic plastic toy with pictures or symbols, where
    here are 15 square tiles arranged in a 4x4 grid, leaving one cell open.
    You slide tiles horizontally or vertically into the open cell, and
    thereby rearrange the tiles to correctly form the picture or put the
    symbols in order. His original ordering is
    > G B C J
    > M E O L
    > x A N D
    > F H K I

    with x marking the empty square, and he wants to arrange them like this:
    x A B C
    D E F G
    H I J K
    L M N O
    ]

    Presumably, JimC can create a program that performs an exhaustive search;
    first it would try every combination (all 3 of them!) of single moves,
    then every combination of 2 moves, and so on until it eventually finds
    the correct answer, or until the sun burns out, whichever comes first.

    (Just for yucks, I wrote a program to do exactly this in VB. As I
    write this, it's running on a dual-processor Intel Xeon 2.8Ghz. After
    4 hours, it's processed 1.2 Billion possibilities, which includes all
    of the combinations of 1 to 17 moves, and ALMOST all of the 18-move
    combinations. My algorithm specifically avoids immediate backtracks
    (slide square 2->3, then next move slide square 3->2) but does not
    attempt to avoid cyclic problems (i.e. slide squares 1, 2, 5, 6 around
    in a circle until you end up where you started). I'll leave it running
    overnight, but I don't expect it to be finished in the morning -- and
    I'll need the computer for other things then.)

    I know about "tree-pruning" techniques, but I don't have a lot of
    experience with them. The obvious example for this problem would be
    to assign 1 point value for every tile that is in its correct place.
    When trees start exhibiting significant point differences, chuck the
    low-point trees.

    The problem with this approach (it seems to me) is that just before the
    puzzle is solved, it would have a pretty LOW point value -- in this
    game, pieces are moved by sliding others out of the way, and they
    eventually move back where they belong.

    Would a different scoring algorithm improve this? Maybe score 3 points
    for a piece in the right position, and 2 points for a piece right next
    to where it belongs? It seems to me that this would help the algorithm
    get the pieces in generally the right area, without causing the points
    to drop just because we're sliding another piece past some already-
    placed pieces (temporarily moving them).

    Again, I don't have a lot of experience with these types of algorithms
    (just book learnin'), so I'm probably not saying it right, maybe even
    making an ass out of myself, but I'd like to learn. I don't know about
    the OP, but I'd be interested in any suggestions anyone could offer,
    from anyone with experience.
     
    Allan W, Jan 22, 2004
    #1
    1. Advertising

  2. Allan W

    Willem Guest

    Allan wrote:
    ) "JimC" <> wrote (in comp.lang.c++.moderated):
    )> I pose a question here concerning what I think is a classic computer
    )> problem, but I don't know of an algorithm for solving it. It resembles
    )> the Towers of Hanoi prolem.
    )
    ) I don't see how.
    )
    )> A few matrices follow. In order to make them more easily understood,
    )> it would be helpful if the reader can disable proportional spacing,
    )> although this is not essential.
    )
    ) Not helpful at all, the way you originally formatted it.
    )
    )> Here is the problem.
    ) [He describes the classic plastic toy with pictures or symbols, where
    ) here are 15 square tiles arranged in a 4x4 grid, leaving one cell open.
    ) You slide tiles horizontally or vertically into the open cell, and
    ) thereby rearrange the tiles to correctly form the picture or put the
    ) symbols in order. His original ordering is
    )> G B C J
    )> M E O L
    )> x A N D
    )> F H K I
    ) with x marking the empty square, and he wants to arrange them like this:
    ) x A B C
    ) D E F G
    ) H I J K
    ) L M N O
    ) ]
    )
    ) Presumably, JimC can create a program that performs an exhaustive search;
    ) first it would try every combination (all 3 of them!) of single moves,
    ) then every combination of 2 moves, and so on until it eventually finds
    ) the correct answer, or until the sun burns out, whichever comes first.

    Can't you just use a basic 'intelligent' solving algorithm ? You won't get
    the shortest solution, of course, but you can basically calculate the moves
    as needed.

    If you absolutely want to do a search, I have some suggestions as well..

    - You can halve the tree depth by searching from the starting and finishing
    positions in parralel.
    - It's well known that 50% of all positions are unsolvable. This is easy
    to check for.


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Jan 22, 2004
    #2
    1. Advertising

  3. "Allan W" <> wrote in message >

    [He describes the classic plastic toy with pictures or symbols, where
    > here are 15 square tiles arranged in a 4x4 grid, leaving one cell open.
    > You slide tiles horizontally or vertically into the open cell, and
    > thereby rearrange the tiles to correctly form the picture or put the
    > symbols in order. His original ordering is
    > > G B C J
    > > M E O L
    > > x A N D
    > > F H K I

    > with x marking the empty square, and he wants to arrange them like this:
    > x A B C
    > D E F G
    > H I J K
    > L M N O
    > ]
    >
    > Presumably, JimC can create a program that performs an exhaustive search;
    > first it would try every combination (all 3 of them!) of single moves,
    > then every combination of 2 moves, and so on until it eventually finds
    > the correct answer, or until the sun burns out, whichever comes first.
    >
    > I know about "tree-pruning" techniques, but I don't have a lot of
    > experience with them. The obvious example for this problem would be
    > to assign 1 point value for every tile that is in its correct place.
    > When trees start exhibiting significant point differences, chuck the
    > low-point trees.
    >
    > The problem with this approach (it seems to me) is that just before the
    > puzzle is solved, it would have a pretty LOW point value -- in this
    > game, pieces are moved by sliding others out of the way, and they
    > eventually move back where they belong.
    >
    > Would a different scoring algorithm improve this? Maybe score 3 points
    > for a piece in the right position, and 2 points for a piece right next
    > to where it belongs? It seems to me that this would help the algorithm
    > get the pieces in generally the right area, without causing the points
    > to drop just because we're sliding another piece past some already-
    > placed pieces (temporarily moving them).


    I kindly doubt that this would help a lot. For example, imagine the
    situation that almost everything is in place, except that O and N (or N & K)
    are switched. Its point value is very high, just 2 point shy of the maximum,
    yet it would be a pain somewhere to solve it.

    > Again, I don't have a lot of experience with these types of algorithms
    > (just book learnin'), so I'm probably not saying it right, maybe even
    > making an ass out of myself, but I'd like to learn. I don't know about
    > the OP, but I'd be interested in any suggestions anyone could offer,
    > from anyone with experience.


    I played a lot with these toys, so I dare to propose a not very elegant,
    albeit workable algorithm. If you play around a little with the toy, you
    will see that in general there is no problem arranging the last two lines.
    1. So start backwards: put O,N in place. Get M next to L, then send them
    together to their place.
    2. Do the same with the third row: first K, then J, then H & I together.
    3. For the first two rows you can apply brute force: there are only ~40000
    possibilities, so you can avoid cyclicity by explicit checking. Or better
    yet, move them all around in a circle (1->2->3->4->8->7->6->5->1) and
    sometimes push a piece in the middle up or down until you get them in the
    order (A->B->C->G->F->E->D).

    It won't be the fastest solution (I estimate ~100 moves) and you will need 3
    different routines (one for O, N, K, J; second for M,L and H,I pairs, third
    for the first two lines) but it definitely will end before the Sun.

    Sanyi
     
    Sanyi Benczik, Jan 22, 2004
    #3
  4. Allan W

    Willem Guest

    Sanyi wrote:
    ) I played a lot with these toys, so I dare to propose a not very elegant,
    ) albeit workable algorithm. If you play around a little with the toy, you
    ) will see that in general there is no problem arranging the last two lines.
    ) 1. So start backwards: put O,N in place. Get M next to L, then send them
    ) together to their place.
    ) 2. Do the same with the third row: first K, then J, then H & I together.
    ) 3. For the first two rows you can apply brute force: there are only ~40000
    ) possibilities, so you can avoid cyclicity by explicit checking. Or better
    ) yet, move them all around in a circle (1->2->3->4->8->7->6->5->1) and
    ) sometimes push a piece in the middle up or down until you get them in the
    ) order (A->B->C->G->F->E->D).

    For the first two rows, you can apply the 'C next to G' and then the
    'B next to F' algorithm, after which you simply need to cycle the three
    remaining blocks until they're in the right position. No brute force
    required whatsoever.

    For larger puzzles, I think it's best to always do the shortest side (away
    from the final position of the blank), so the sides stay as long as
    possible, and your working area as square as possible. But that's just a
    gut feeling, nothing solid.

    ) It won't be the fastest solution (I estimate ~100 moves) and you will need 3
    ) different routines (one for O, N, K, J; second for M,L and H,I pairs, third
    ) for the first two lines) but it definitely will end before the Sun.

    If you want to cut down on routines, use the 'next' to routine for the
    first two letters as well. Of course, technically speaking, getting one
    letter next to another is roughly the same as getting it into position...


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Jan 22, 2004
    #4
  5. "Allan W" <> wrote in message news:...
    > "JimC" <> wrote (in comp.lang.c++.moderated):


    > > I pose a question here concerning what I think is a classic computer
    > > problem, but I don't know of an algorithm for solving it. It resembles
    > > the Towers of Hanoi prolem.

    >
    > I don't see how.


    Neither do I ...

    > [He describes the classic plastic toy with pictures or symbols, where
    > here are 15 square tiles arranged in a 4x4 grid, leaving one cell open.
    > You slide tiles horizontally or vertically into the open cell, and
    > thereby rearrange the tiles to correctly form the picture or put the
    > symbols in order. ] ...


    > (Just for yucks, I wrote a program to do exactly this in VB. As I
    > write this, it's running on a dual-processor Intel Xeon 2.8Ghz. After
    > 4 hours, it's processed 1.2 Billion possibilities, which includes all
    > of the combinations of 1 to 17 moves, and ALMOST all of the 18-move
    > combinations. My algorithm specifically avoids immediate backtracks
    > (slide square 2->3, then next move slide square 3->2) but does not
    > attempt to avoid cyclic problems (i.e. slide squares 1, 2, 5, 6 around
    > in a circle until you end up where you started). I'll leave it running
    > overnight, but I don't expect it to be finished in the morning -- and
    > I'll need the computer for other things then.)


    You should check for board configurations that have occured before;
    it prunes zillions of branches in your game tree. A BFS method would
    create a huuuuge queue, while a DFS simply uses a stack for the
    previously reached board configurations.

    A simple observation -- on average there are (4*2+8*3+4*4)/16 == 3 possible
    moves given a board configuration. One move results in a previous board
    configuration. So, (sloppy math alert) a game tree without storing
    repeating configurations has a branching factor equal to 2.

    There are 16! different board configurations, only half of them are
    solvable. At most log(16!/2)/log(2) ~ 44 moves are necessary to solve
    the puzzle for any (solvable) configuration.

    A simple DFS with a recursion depth bound of ~ 44 should do the job;
    Of course repeating board configuration should be avoided.

    kind regards,

    Jos

    ps. I'll settle for 50 instead of 44, just because of the sloppy math.
     
    Jos A. Horsmeier, Jan 22, 2004
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Barak
    Replies:
    0
    Views:
    837
    Barak
    Aug 7, 2003
  2. student

    java graph theory

    student, Mar 11, 2006, in forum: Java
    Replies:
    3
    Views:
    2,842
    Roedy Green
    Mar 12, 2006
  3. JimC
    Replies:
    3
    Views:
    535
  4. Emilio Mayorga
    Replies:
    6
    Views:
    375
    Martien Verbruggen
    Oct 8, 2003
  5. IRR
    Replies:
    2
    Views:
    454
Loading...

Share This Page