Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Recursion problem - Graph theory - Algorithm needed

Reply
Thread Tools

Recursion problem - Graph theory - Algorithm needed

 
 
JimC
Guest
Posts: n/a
 
      01-17-2004
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?









 
Reply With Quote
 
 
 
 
Victor Bazarov
Guest
Posts: n/a
 
      01-17-2004
"JimC" <(E-Mail Removed)> 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


 
Reply With Quote
 
 
 
 
David Harmon
Guest
Posts: n/a
 
      01-17-2004
On Sat, 17 Jan 2004 03:55:15 GMT in comp.lang.c++, "JimC"
<(E-Mail Removed)> 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=%2215+puzzle%22

 
Reply With Quote
 
JimC
Guest
Posts: n/a
 
      01-17-2004

"David Harmon" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...

> On Sat, 17 Jan 2004 03:55:15 GMT in comp.lang.c++, "JimC"
> <(E-Mail Removed)> 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=%2215+puzzle%22
>


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





 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
perl graph theory (using Graph::Directed) IRR Perl Misc 2 07-27-2004 03:08 AM
Re: Recursion problem - Graph theory - Algorithm needed Allan W C++ 4 01-22-2004 02:42 PM
New book on Information Theory and State-of-the-art Coding Theory David MacKay VOIP 0 11-05-2003 10:42 PM
GD::Graph: "mixed" graph doesn't recognize "area" graph type Emilio Mayorga Perl Misc 6 10-08-2003 02:14 AM
JGraphT - a free Java library of graph-theory objects and algorithms Barak Java 0 08-07-2003 10:07 AM



Advertisments