## 11513 - 9 Puzzle

Moderator: Board moderators

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

### 11513 - 9 Puzzle

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

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

### Re: 11513 - 9 Puzzle

Use precalculation.

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

### Re: 11513 - 9 Puzzle

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

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

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

### Re: 11513 - 9 Puzzle

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

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

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

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

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

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

Thanks