11513 - 9 Puzzle

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

Moderator: Board moderators

Post Reply
Estigma88
New poster
Posts: 2
Joined: Sun Oct 12, 2008 9:51 pm

11513 - 9 Puzzle

Post by Estigma88 » Sun Oct 12, 2008 10:10 pm

Someone can help me, not like solve 9 Puzzle, goes out for me one Time Limit :cry:

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11513 - 9 Puzzle

Post by Leonid » Mon Oct 13, 2008 12:37 am

Use precalculation.

slxst
New poster
Posts: 23
Joined: Mon Oct 16, 2006 2:18 am

Re: 11513 - 9 Puzzle

Post by slxst » Mon Oct 13, 2008 8:55 pm

This is what I did in my AC code:

Do a BFS-like algorithm:
Have a cache of solutions and a queue.
Put in the queue the initial state "123456789" which has solution "" and moves=0
While there are states in the queue:
Process the actual state
Create all 6 neighbors states
If the neighbor is not in the cache, put it (the neighbor has the solution of its parent + some move H1, H2, H3, V1, V2, or V3 and moves+1) and
put it also in the queue.

Read the case, look in the cache if is not in the cache is not solvable, otherwise print the info in the cache.

The algorithm runs in ~4.5 seconds enough to be accepted but is very slow given that the best solution runs in 0,2

bleed1979
New poster
Posts: 8
Joined: Thu Oct 08, 2009 5:34 am

Re: 11513 - 9 Puzzle

Post by bleed1979 » Sat Oct 31, 2009 3:51 am

slxst wrote:This is what I did in my AC code:

Do a BFS-like algorithm:
Have a cache of solutions and a queue.
Put in the queue the initial state "123456789" which has solution "" and moves=0
While there are states in the queue:
Process the actual state
Create all 6 neighbors states
If the neighbor is not in the cache, put it (the neighbor has the solution of its parent + some move H1, H2, H3, V1, V2, or V3 and moves+1) and
put it also in the queue.

Read the case, look in the cache if is not in the cache is not solvable, otherwise print the info in the cache.

The algorithm runs in ~4.5 seconds enough to be accepted but is very slow given that the best solution runs in 0,2
This solving method is right.
But if you use hash table to search states in the cache, you can AC about ~0.400s
Judge World - problem solving is a routine.
http://bleed1979.myweb.hinet.net

User avatar
outsbook
New poster
Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

Re: 11513 - 9 Puzzle

Post by outsbook » Sat Nov 26, 2011 9:23 pm

try this
Input:

Code: Select all

9 8 7
6 5 4
3 2 1
7 8 9
4 5 6
1 2 3
1 9 2
3 8 4
5 7 6
3 2 1
4 5 6
7 8 9
1 2 3
6 5 4
7 8 9
1 3 2
7 9 8
4 6 5
7 9 8
4 6 5
1 2 3
7 9 8
4 6 5
1 3 2
7 9 8
1 3 2
4 6 5
1 2 3
4 5 6
7 8 9
0
Output:

Code: Select all

11 H2V3V3V1H3H3H2V2V1V1H1
Not solvable
8 V1H3V2H3V2H2H1H1
Not solvable
Not solvable
11 H3V3V2V2H3H1H1V2V1V1H1
Not solvable
11 H2V2V1V1H3H1H1V2V1V1H1
Not solvable
0
"Learning to love yourself is the greatest love of all" - Michael Masser and Linda Creed

afruizc
New poster
Posts: 15
Joined: Sat Oct 13, 2012 2:04 am

Re: 11513 - 9 Puzzle

Post by afruizc » Tue Dec 04, 2012 1:31 am

I took a different approach.

I run bfs at the beginning from the state

Code: Select all

1 2 3
4 5 6
7 8 9
Then, When reading the cases I looked them up if there was solution.

Notes:
- The printing of the moves is slightly different.
- The moves are done the opposite way because we are starting from the target state.

m.shawkey
New poster
Posts: 9
Joined: Tue Jun 11, 2013 2:58 pm

Re: 11513 - 9 Puzzle

Post by m.shawkey » Thu Aug 01, 2013 7:18 pm

I am getting wrong answer, can anyone help me,please?
my code http://ideone.com/6RT3AS
I tested my program with this input
http://repo.or.cz/w/and.git/blob_plain/ ... /puzzle.in
output
http://repo.or.cz/w/and.git/blob_plain/ ... puzzle.out
it generated the correct results for the 5118 test cases in this file.

EDIT:
the code was accepted after replacing "printf" with "cout"

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11513 - 9 Puzzle

Post by brianfry713 » Wed Aug 07, 2013 3:57 am

You were printing null characters.
Check input and AC output for thousands of problems on uDebug!

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 11513 - 9 Puzzle

Post by just_yousef » Wed Jul 16, 2014 4:55 pm

Can any one tell me why this code is printing wrong result for the sample input :/

Code: Select all

AC :D 
Last edited by just_yousef on Thu Jul 17, 2014 12:30 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11513 - 9 Puzzle

Post by brianfry713 » Wed Jul 16, 2014 11:28 pm

Swap lines 49 and 50 and lines 60 and 61. Since you're working backwards from the solution, the moves should also be reversed.
Check input and AC output for thousands of problems on uDebug!

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 11513 - 9 Puzzle

Post by just_yousef » Thu Jul 17, 2014 12:30 am

Thanks :D :D

Post Reply

Return to “Volume 115 (11500-11599)”