OK, I'm new at this as will be obvious.
Anybody can help directing me as to where I can find the
algorithm or lisp code to solving a traditional Sliding Tiles
puzzle game? Mine is an *s puzzle.
I have found a good heuristic function, but I need a better one.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
RockWell wrote:
> OK, I'm new at this as will be obvious.
> Anybody can help directing me as to where I can find the
> algorithm or lisp code to solving a traditional Sliding Tiles
> puzzle game? Mine is an *s puzzle.
>
> I have found a good heuristic function, but I need a better one.
Principles of Artificial Intelligence by Nils Nilsson covers this
subject in depth.
Le Hibou (ma propre opinion)
--
"There are two ways of constructing a software design: One way is to
make it so simple that there are obviously no deficiencies and the
other way is to make it so complicated that there are no obvious
deficiencies." -- CAR Hoare
In article <·················@inthan.be>,
Donald Fisk <···········@inthan.be> wrote:
> RockWell wrote:
> > algorithm or lisp code to solving a traditional Sliding Tiles
> > puzzle game? Mine is an *s puzzle.
> Principles of Artificial Intelligence by Nils Nilsson covers this
> subject in depth.
Is there a proof that sliding tiles puzzles preserve some kind of parity
- that there are two different sets of arrangements that are exclusive?
It seems that there is, but I can't find it - the nearest I've got is
some kind of sum of rotation vectors orthogonal to the puzzle (I know
this sounds very vague - I'm just hoping it will ring a bell with
someone).
Thanks, and apologies for it being somewhat off-topic.
Andrew
http://www.andrewcooke.free-online.co.uk
Sent via Deja.com http://www.deja.com/
Before you buy.
Andrew Cooke wrote:
> Is there a proof that sliding tiles puzzles preserve some kind of parity
> - that there are two different sets of arrangements that are exclusive?
> It seems that there is, but I can't find it - the nearest I've got is
> some kind of sum of rotation vectors orthogonal to the puzzle (I know
> this sounds very vague - I'm just hoping it will ring a bell with
> someone).
Yes.
Draw a path through the cells of your grid that goes once
through each cell, thus:
+----+----+----+----+
| ,__|____|____|__ |
| | | | | |
+----+----+----+----+
| |__|____|____|__. |
| | | | | |
+----+----+----+----+
| ,__|____|____|__| |
| | | | | |
+----+----+----+----+
| |__|____|____|__ |
| | | | |
+----+----+----+----+
Given any state of the tiles, write down the labels on
the tiles along the path. Just pass over the empty space
without doing anything.
It's now true that every sliding move induces an even
permutation on the labels. Slides along the path don't
do anything, obviously. A slide between two adjacent
bits of path produces a 3-cycle, 5-cycle or 7-cycle,
all of which are even.
(Of course, this works whatever the size of the grid.)
--
Gareth McCaughan ················@pobox.com
sig under construction
Damn! - why are these things always so obvious in hindsight?! :-)
Thanks,
Andrew
In article <··············@g.local>,
Gareth McCaughan <················@pobox.com> wrote:
> Andrew Cooke wrote:
>
> > Is there a proof that sliding tiles puzzles preserve some kind of
parity
> > - that there are two different sets of arrangements that are
exclusive?
> > It seems that there is, but I can't find it - the nearest I've got
is
> > some kind of sum of rotation vectors orthogonal to the puzzle (I
know
> > this sounds very vague - I'm just hoping it will ring a bell with
> > someone).
>
> Yes.
>
> Draw a path through the cells of your grid that goes once
> through each cell, thus:
[zig-zag picture snipped as spacing lost in quoting]
> Given any state of the tiles, write down the labels on
> the tiles along the path. Just pass over the empty space
> without doing anything.
>
> It's now true that every sliding move induces an even
> permutation on the labels. Slides along the path don't
> do anything, obviously. A slide between two adjacent
> bits of path produces a 3-cycle, 5-cycle or 7-cycle,
> all of which are even.
>
> (Of course, this works whatever the size of the grid.)
Sent via Deja.com http://www.deja.com/
Before you buy.