Re: Recursion problem - Graph theory - Algorithm needed
From: Willem (willem_at_stack.nl)
Date: 01/22/04
- Next message: Jim: "Re: Response to Karen and to Willem on recursive proofs"
- Previous message: neodev: "www.preferitionline.com"
- In reply to: Allan W: "Re: Recursion problem - Graph theory - Algorithm needed"
- Next in thread: Sanyi Benczik: "Re: Recursion problem - Graph theory - Algorithm needed"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Thu, 22 Jan 2004 02:12:57 +0000 (UTC)
Allan wrote:
) "JimC" <jimc@cross-comp.com> 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
- Next message: Jim: "Re: Response to Karen and to Willem on recursive proofs"
- Previous message: neodev: "www.preferitionline.com"
- In reply to: Allan W: "Re: Recursion problem - Graph theory - Algorithm needed"
- Next in thread: Sanyi Benczik: "Re: Recursion problem - Graph theory - Algorithm needed"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
