CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Manifesto: what CTK is about |Store| Search CTK Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot

CTK Exchange

Subject: "Question about a 15/16 sliding puzz..."     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange This and that Topic #83
Reading Topic #83
Bart Verhaeghe (Guest)
guest
Jan-30-01, 02:49 PM (EST)
 
"Question about a 15/16 sliding puzzle"
 
   Dear Sir,


I wonder if it is possible to solve a 15 sliding puzzle from a given starting position to the finishing position in a mimimum
movements.

Is it possible the solve this problem with mathematics? Or do you need a computer to solve the problem. Are there programs
available that can handle this problem?

Yours sincerely,

Verhaeghe Bart


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
alexb
Charter Member
672 posts
Jan-30-01, 03:05 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
1. "RE: Question about a 15/16 sliding puzzle"
In response to message #0
 
   LAST EDITED ON Jan-30-01 AT 03:06 PM (EST)

Bart Verhaeghe wrote:

> I wonder if it is possible to solve
> a 15 sliding puzzle from a given starting
> position to the finishing position in a
> mimimum movements.

Probably. Never worked on this. I would guess this is not trivial.

> Is it possible the solve this problem
> with mathematics?

Do not know what this may mean.

> Or do you need a computer
> to solve the problem.

Most likely.

> Are there programs available that
> can handle this problem?
>

I have no notion. Once I saw an M.S. thesis in Computer Science solving a smaller 8-9 puzzle. Can't recollect where it came from. In the Introduction it was said that that puzzle very often serves as a testbed for various algorithms because there is no easy way.

All the best,
Alexander Bogomolny


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
Don (Guest)
guest
Jul-19-01, 12:01 PM (EST)
 
2. "RE: Question about a 15/16 sliding puzzle"
In response to message #1
 
   Many years ago (I hate to think of how far back this has been) I took a computer science class (undergraduate course) in which the instructor assigned the 15-puzzle to be solved by computer given any random configuration which he would choose.

There was one word of warning...not all possible combinations can be solved in the 1 - 15 order. Of all permutations of the tile positions, half are solvable in the 1-15 order with the space in the bottom right corner, and the other half are solvable in the reverse (15-1) order with the space in the bottom right corner. There is a way of calculating which solvable format a given permutation is a member of. Many of the sit's show this, but only mention that the puzzle will end up with the 14 and 15 in the wrong order...none mention the reverse-order. Personally, I find it interesting that the solutions are in forward and reverse order for the two sets of permutations.

We were to use whatever computer system we had available. I wrote a Pascal program to solve it running on a CDC Cyber system. One classmate was able to complete the assignment in assembler on a 6502 processor system with 4KB of memory. Heuristic searches, tree searches and brute force methods were used...given the limited resources of the time, a combination of heuristic and tree searches were the most successful.

I am currently working on a Visual Basic version of the program and plan to use a breadth-first tree search to find the shortest path.



  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to visit the old CTK Exchange archive.

|Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

[an error occurred while processing this directive]
 Advertise

New Books
Second editions of J. Conway's classic On Numbers And Games and the inimitable Winning Ways for Your Mathematical Plays