11513 - 9 Puzzle

[Estigma88]

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

[Leonid]

Use precalculation.

[slxst]

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]

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

[outsbook]

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

[afruizc]

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]

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]

You were printing null characters.

[just_yousef]

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

Code: Select all

AC :D 

[brianfry713]

Swap lines 49 and 50 and lines 60 and 61. Since you're working backwards from the solution, the moves should also be reversed.

[just_yousef]

Thanks