10181 - 15-Puzzle Problem

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

10181 - 15-Puzzle Problem

Post by Miguel Angel » Mon Sep 16, 2002 6:24 am

can i know the following without doing full search????

If the given initial configuration is not solvable you just need to print the line “This puzzle is not solvable.”

Thanks 8)
:D Miguel & Marina :D

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Mon Sep 16, 2002 8:45 am

Read description for problem 652.
Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing `x' tile, of course).

uzioriluzan
New poster
Posts: 27
Joined: Thu Feb 14, 2002 2:00 am

Post by uzioriluzan » Tue Nov 05, 2002 4:17 pm

Hi, how can I use this information? I've implemented A* with the Manhattan Distance heuristic and it still gives time limit.
Your help is welcome :)
Regards!
Ivan Golubev wrote:Read description for problem 652.
Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing `x' tile, of course).

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Tue Nov 05, 2002 9:22 pm

Hi, uzioriluzan:
You would like this web page: "http://mathworld.wolfram.com/15Puzzle.html".
By the way, could you briefly introduce the heuristic method to me? :wink:
Thanks in advance.

uzioriluzan
New poster
Posts: 27
Joined: Thu Feb 14, 2002 2:00 am

Post by uzioriluzan » Wed Nov 06, 2002 3:52 pm

You could find a description at http://www.delphiforfun.org/Programs/15puzzle_2.htm or at AIMA
Regards!
LittleJohn wrote:Hi, uzioriluzan:
You would like this web page: "http://mathworld.wolfram.com/15Puzzle.html".
By the way, could you briefly introduce the heuristic method to me? :wink:
Thanks in advance.

laboni
New poster
Posts: 12
Joined: Sat Sep 14, 2002 9:22 pm
Location: India

10181 : 15 PUZZLE - HELP PLZ! PLZ!! PLZ!!!

Post by laboni » Thu Dec 05, 2002 12:31 am

Somebody told me that 15 puzzle is a very good program to learn IDA* Search.I read about IDA* Search in a book but found no way to code it.
Can somebody plz send me a solution of 15 puzzle using IDA* Search in C or C++?

My email address is <laboni_inobal@yahoo.com>

I would be very very grateful if anyone extends his/her helping hand.

Bye

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

10181 15-puzzle

Post by junjieliang » Tue Apr 01, 2003 11:47 am

Hi,

I know we have to use IDA* to solve this problem, but is there a way to find out if a starting state can be solved without searching through everything? I remember reading something about some invariant number or such...

Thanks.

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Wed Apr 02, 2003 4:27 am

yes, there's such a way. if you search the web.
if i remember correctly, i used the following:
let X = determine number of inversions + the row number of the empty square (numbered as row 1 to row 4)
if X is odd, no solution
if X is even, do the search

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Wed Apr 02, 2003 10:56 am

Thanks!
But I still can't pass the 10-second limit :( .
Here's what I'm doing:
First check if the starting configuration is solvable. Then run IDA* using a heap with Manhattan distance heuristic. I hash the states that's I've been to to make sure I don't repeat calculations.

Is there any way to speed the algorithm further? I can run up to 25 moves (WA in 1.687s), so there must be some input that requires at least > 25 moves.

I also noticed a lot of people who solved this problem used very little memory (compared to mine). Is there a different algorithm to solve this problem?

Thanks to anyone who can help me. :lol:

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Wed Apr 02, 2003 6:26 pm

I'm not sure about the speed either, as my program doesn't run fast.

but, for IDA*, i suppose a stack is enough, not a heap.
i used Manhattan distance heuristic too (quite standard?)
i guess if you adjust/tune your scoring functions, say F() = number of steps + 80* estimated steps, it may terminate faster, although with a less optimal solution, then can pass the 10s limit.

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan » Wed Apr 02, 2003 7:40 pm

Thanks a lot, wyvmak.

I got stuck with the TLE thing for this problem. And now after using F(x)=G(x)+4/3*H(x) I get AC. My solution took 5sec+ though.

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Mon Apr 07, 2003 6:16 am

First, I think I meant A* on my algorithm above (the one using heap) :oops:

Secondly, just to clarify, A* and IDA* should both run faster than BFS? I wrote 3 programs, using A*, IDA*, and BFS to solve the 8-puzzle (p652). The first 2 got TLE, BFS got AC in 6+ sec. Which is why I think I'm coding wrongly :cry: .

Does anyone have any good information on the internet on A* and IDA*?

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Mon Apr 07, 2003 7:16 am

[/b]i think the book of shahani(alg in c++) will work...
although i havn't enough time yet to solve it..
but i read it and think that it works very first...
what about your opinions???
--
anupam :oops: :oops: :oops:
"Everything should be made simple, but not always simpler"

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Tue Apr 08, 2003 5:07 am

I don't have that book. Could you maybe post a short paragraph from it? Oh does anyone have any reference online...

Thanks anyway :lol:

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Tue Apr 08, 2003 6:12 am

actually i do't have the book's reference online..
if anybody knows please help him...

----
i have the book..
it's one of the best books of alg..
if u can bye it..
thanks ...
--
anupam :oops: :oops: :oops: :oops:
"Everything should be made simple, but not always simpler"

Post Reply

Return to “Volume 101 (10100-10199)”