Recursion problem - Graph theory - Algorithm needed

Discussion in 'C++' started by JimC, Jan 17, 2004.

  1. JimC

    JimC Guest

    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.

    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.

    Here is the problem. We have a matrix containing elements, represented here
    as single upper case letters, and one element with value x. To make this
    concrete, let this be the following 4 x 4 matrix in Figure 1:


    G B C J
    M E O L
    x A N D
    F H K I

    Figure 1

    We want to rearrange the elements so that they are ordered beginning with the x
    element, followed by the upper-case letters arranged alphabetically, as
    shown in Figure 2.


    x A B C
    D E F G
    H I J K
    L M N O

    Figure 2

    But we must use the following rule:

    An element can be moved only if it is next to the x element,
    in the same row or column, and it must be exchanged with the x element.

    So, a possible re-configuration of Figure 1 would be as shown
    in Figure 3:



    G B C J
    M E O L
    A x N D
    F H K I

    Figure 3

    where the element with value A in the third row has been exchanged with the
    x element to its left.

    Does anyone know of an efficient algorithm for producing the steps that
    lead to the ordered arrangement in Figure 2?
    JimC, Jan 17, 2004
    #1
    1. Advertising

  2. "JimC" <> wrote...
    > 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. [...]


    I strongly suggest comp.programming for questions of this sort.

    Victor
    Victor Bazarov, Jan 17, 2004
    #2
    1. Advertising

  3. JimC

    David Harmon Guest

    On Sat, 17 Jan 2004 03:55:15 GMT in comp.lang.c++, "JimC"
    <> was alleged to have written:
    >But we must use the following rule:
    >
    > An element can be moved only if it is next to the x element,
    > in the same row or column, and it must be exchanged with the x element.


    http://www.google.com/search?q="15 puzzle"
    David Harmon, Jan 17, 2004
    #3
  4. JimC

    JimC Guest

    "David Harmon" <> wrote in message
    news:...

    > On Sat, 17 Jan 2004 03:55:15 GMT in comp.lang.c++, "JimC"
    > <> was alleged to have written:
    > >But we must use the following rule:
    > >
    > > An element can be moved only if it is next to the x element,
    > > in the same row or column, and it must be exchanged with the x element.

    >
    > http://www.google.com/search?q="15 puzzle"
    >


    Thanks!

    Ah.... so then the problem is informally known as "the 15-Puzzle" and is
    solvable iff the sum of inversions in the initial layout is an even number. The
    puzzle seems to have been around at least since the 1870s.

    Of the many articles turned up by the preceding Google search, I thought
    the following following two were quite good:

    http://www.javaonthebrain.com/java/puzz15/
    http://mathworld.wolfram.com/15Puzzle.html
    JimC, Jan 17, 2004
    #4
    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:
    808
    Barak
    Aug 7, 2003
  2. student

    java graph theory

    student, Mar 11, 2006, in forum: Java
    Replies:
    3
    Views:
    2,814
    Roedy Green
    Mar 12, 2006
  3. Allan W
    Replies:
    4
    Views:
    524
    Jos A. Horsmeier
    Jan 22, 2004
  4. Emilio Mayorga
    Replies:
    6
    Views:
    329
    Martien Verbruggen
    Oct 8, 2003
  5. IRR
    Replies:
    2
    Views:
    398
Loading...

Share This Page