![:cry:](./images/smilies/icon_cry.gif)
11513 - 9 Puzzle
Moderator: Board moderators
11513 - 9 Puzzle
Someone can help me, not like solve 9 Puzzle, goes out for me one Time Limit ![:cry:](./images/smilies/icon_cry.gif)
![:cry:](./images/smilies/icon_cry.gif)
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
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
Re: 11513 - 9 Puzzle
This solving method is right.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
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
http://bleed1979.myweb.hinet.net
Re: 11513 - 9 Puzzle
try this
Input:
Output:
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
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
Re: 11513 - 9 Puzzle
I took a different approach.
I run bfs at the beginning from the state
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.
I run bfs at the beginning from the state
Code: Select all
1 2 3
4 5 6
7 8 9
Notes:
- The printing of the moves is slightly different.
- The moves are done the opposite way because we are starting from the target state.
Re: 11513 - 9 Puzzle
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"
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"
-
- 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!
-
- 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.
-
- 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!