1543 views

Skip to first unread message

May 1, 2000, 3:00:00 AM5/1/00

to

What kind of an algorithm can be used to solve a standard tile sliding

puzzle ? Or what is the idea behind such an algorithm ? I don't mean a

solving program - I know Balmoral Software has one - I'd like to know the

general principle for finding a solution. Thanks for help.

puzzle ? Or what is the idea behind such an algorithm ? I don't mean a

solving program - I know Balmoral Software has one - I'd like to know the

general principle for finding a solution. Thanks for help.

May 1, 2000, 3:00:00 AM5/1/00

to

Here is the way I have learned to solve 3X3 sliding puzzles. It works very

well for me. I am sure there are more complete solutions out there but this

works fine.

For explanation sake let's suppose you have a 3X3 puzzle with pieces

numbered 1-8. The upper left corner is 1 then below it is 2 and then 3.

The next column is of course 4,5,6 and the rightmost column is is 7,8 with

the lower right being empty. Now you scramble the pieces.

It is easy to put the first piece any place you want. You are going to try

to put 1,2,3 (one column) in place. The trick is you put 2 in where 3

should be (lower left corner) and then put 1 above it. Now move 3 into

position just to the right of 2. Finally you slide 1 and 2 up and then 3

moves into place.

Now you are left with a very small puzzle (only 2 X 3). You do not disturb

the column which you have just completed. Leave it alone and randomly move

around the 5 remaining pieces. If you do it in a very random manner (zig

zaging the tiles around as wildly as possible you will suddenly come upon

the solution. The only way it could take a long time is if you fall into

the trap of repeating the same few moves over and over again.

Now if you have a very large puzzle it is not hard to solve it column by

column and then row by row, each time reducing the large puzzle to a smaller

puzzle until you only have a 2X3 puzzle.

Try this and let me know if it works for you,

May 3, 2000, 3:00:00 AM5/3/00

to

Thanks for the suggestion. But there is a little problem in trying to reduce

the size in this way. It may happen the the reduced puzzle has a wrong

parity and hence may be unsovable without disturbing the already solved row

or column. This happens to me by trying to reduce 4x4 puzle to 3x3. Although

I think that among several ways to arrange the first column or row in the

correct sequence there is always one for which the reduced puzzle has the

correct parity it is not always clear how to find it in a systematic way.

the size in this way. It may happen the the reduced puzzle has a wrong

parity and hence may be unsovable without disturbing the already solved row

or column. This happens to me by trying to reduce 4x4 puzle to 3x3. Although

I think that among several ways to arrange the first column or row in the

correct sequence there is always one for which the reduced puzzle has the

correct parity it is not always clear how to find it in a systematic way.

Presto <presto...@hotmail.com> wrote in message

news:8elioj$2lgc$1...@newssvr04-int.news.prodigy.com...

May 5, 2000, 3:00:00 AM5/5/00

to

BSvK <bshu...@redshift.com> wonders:

> What kind of an algorithm can be used to solve a standard tile sliding puzzle

?

I am not quite sure what you mean by "standard". I am going to take it to be

fairly general in the sense that the tiles need not all be unit squares. (Eg..,

there can be a 2x2, a 1x2, or a 2x1 tile in the 'box'.)

A more tractable abstraction of the puzzle is a graph in which the vertices

correspond to possible arrangements of the tiles and the edges connect pairs of

vertices such that the arrangement corresponding to one of the vertices can be

transformed into that of the other by one simple 'move'. Now, in graph

theoretic terms, we are simply looking for a shortest path between specified

vertices (or sets of vertices). There is a sizable body of literature on this

subject. In general, it is hard, especially if you insist on the very best

answer. However, there are often heuristics arising from the geometry of the

original puzzle than can help focus the search.

If the search space is small enough, you can just brute force it by inductively

generating all positions reachable in N moves. (When generating the (N+1)-move

set, just avoid generating anything that is already in the (N-1)-move or N-move

sets.) Note a precursor of each generated position, and stop when the generated

set contains a target position.

Regards,

David V.

May 8, 2000, 3:00:00 AM5/8/00

to

)Thanks for the suggestion. But there is a little problem in trying to reduce

)the size in this way. It may happen the the reduced puzzle has a wrong

)parity and hence may be unsovable without disturbing the already solved row

)or column. This happens to me by trying to reduce 4x4 puzle to 3x3. Although

)I think that among several ways to arrange the first column or row in the

)correct sequence there is always one for which the reduced puzzle has the

)correct parity it is not always clear how to find it in a systematic way.

)the size in this way. It may happen the the reduced puzzle has a wrong

)parity and hence may be unsovable without disturbing the already solved row

)or column. This happens to me by trying to reduce 4x4 puzle to 3x3. Although

)I think that among several ways to arrange the first column or row in the

)correct sequence there is always one for which the reduced puzzle has the

)correct parity it is not always clear how to find it in a systematic way.

HUH?

Is there something I'm missing ? You can only change the parity of the

remaining bit by changing the parity of the already solved bit. Which you

can only do by exchanging two tiles in the solved bit. Which kind of makes

'solved' a misnomer.

In other words: if subpuzzle-plus-solved-bit has even parity, then the

subpuzzle will have even parity, because the solved bit has parity zero.

The only situation I can imagine where this happens is if there is more than

one solution, I.E. tiles are interchangeable.

SaSW,

--

Willem (at stack dot nl)

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

Mar 17, 2021, 11:15:21 AM3/17/21

to

Is there 8 slider puzzle related project?

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu