C++Talk.NET

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?

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Francis Glassborow · Guest

In message <Co2Ob.2376$IZ1.127 (AT) newssvr29 (DOT) news.prodigy.com>, JimC
<jimc (AT) cross-comp (DOT) com> writes

Jack Klein · Guest

On 17 Jan 2004 06:05:09 -0500, "JimC" <jimc (AT) cross-comp (DOT) com> wrote in
comp.lang.c++.moderated: