«

"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 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

"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 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

"Allan W" <> wrote in message news: om...
> "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.