Recursion problem - Graph theory - Algorithm needed

J

JimC

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?
 
V

Victor Bazarov

JimC said:
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
 
J

JimC

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,733
Messages
2,569,440
Members
44,829
Latest member
PIXThurman

Latest Threads

Top