A puzzle game

Problem code: H1

All submissions for this problem are available.

Johnny has some difficulty memorizing the small prime numbers. So, his computer science teacher has asked him to play with the following puzzle game frequently.

The puzzle is a 3x3 board consisting of numbers from 1 to 9. The objective of the puzzle is to swap the tiles until the following final state is reached:

1 2 3
4 5 6
7 8 9

At each step, Johnny may swap two adjacent tiles if their sum is a prime number. Two tiles are considered adjacent if they have a common edge.

Help Johnny to find the shortest number of steps needed to reach the goal state.

Input

The first line contains t, the number of test cases (about 50). Then t test cases follow. Each test case consists of a 3x3 table describing a puzzle which Johnny would like to solve.

The input data for successive test cases is separated by a blank line.

Output

For each test case print a single line containing the shortest number of steps needed to solve the corresponding puzzle. If there is no way to reach the final state, print the number -1.

Example

Input:
2

7 3 2 
4 1 5 
6 8 9 

9 8 5 
2 4 1 
3 7 6  

Output:
6
-1

Output details

The possible 6 steps in the first test case are described in the following figure:

Date: 2009-09-15
Time limit: 2

s
Source limit: 50000
Languages: C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK CAML CLPS PRLG WSPC BF ICK TEXT


Comments

too difficult!!

Anuj Kumar - 2nd Oct,2009 06:30:04.

too difficult!!

hay any body have any idea of

K Marutikumar Naidu - 3rd Oct,2009 00:12:55.
hay any body have any idea of solution

Hmm.. I guess you must have

Anil Kishore - 3rd Oct,2009 02:23:33.

Hmm.. I guess you must have an idea too, just think over again and reverse things ;)

In the input, are the

sivaraman - 3rd Oct,2009 09:56:25.

In the input, are the adjacent numbers separated by a space or is every line given continuously like a string?

My java solution in my

Balraja Subbiah - 3rd Oct,2009 12:58:47.

My java solution in my eclipse is working fine but online judge is giving a compilation error. I have also set the class name as Main. Any suggestions ?

 

@sivaraman They are separated

Aniruddha (Codechef) - 3rd Oct,2009 14:18:00.

@sivaraman They are separated by a space

@balraja Please take a look at Sample Solutions

I am using recursion. But it

Prakhar Goel - 4th Oct,2009 17:57:26.

I am using recursion. But it overlimits the time of 2s. anyone idea? Can there be a non recursive solution?

This is a contest, you won't

Stephen Merriman - 5th Oct,2009 02:08:49.

This is a contest, you won't be given extra hints.

Hi Admin   My  code is

Jaydeep Singh - 5th Oct,2009 11:21:52.

Hi Admin

 

My  code is working perfect on compiler (g++ 4.0.08) on my system. Its showin run time error when i am submitting it

Could you please tell what  this error indicates

RUNTIME  ERROR (OTHER).

Is it abending  or  memory fault for some test case?

I am assuming you all grids have 1 2 3...9 and there are no zeros in the input

 

We can't check individual

Aniruddha (Codechef) - 5th Oct,2009 14:52:37.

We can't check individual solutions during the contest. The input is consistent with the problem statement specifications.

I' ve submit one solution

刘标勇 - 5th Oct,2009 17:46:08.

I' ve submit one solution successfully .

where can I find my score ?

or how long I have to wait for ?

or the score is zero ?

@Admin : Could you please

Arvind Giri - 7th Oct,2009 18:04:36.

@Admin : Could you please explain how the time is calculated for java programs. Does it include time taken to load jvm?

 

On my local, main method takes 1500-1600 ms for worse cases, but on codechef server, same program times out.

Shouldn't time limit vary

Arvind Giri - 7th Oct,2009 18:05:42.

Shouldn't time limit vary according to language?

Yes, the time limit does in

Aniruddha (Codechef) - 7th Oct,2009 18:29:22.

Yes, the time limit does in fact vary according to language. http://blog.codechef.com/2009/04/01/announcing-time-limits-based-on-prog... The time specified is not per test case, but for all the 50 test cases to be executed. Also, the system specifications of our server might be different compared to those of your machine. This information can be found at www.codechef.com/wiki

Hi Anirudha, What is time

Abhijeet Nagre - 7th Oct,2009 21:27:37.

Hi Anirudha, What is time limit for this program. Is it 50 secs for 50 test cases? What is time limit for C#?

My program is running in less than 0.5 secs on my machine.My machine has far lesser configuration than Enviornment. It as consumes hardly 30 Kbs so that also should not be issue.

Thanks,

Abhijeet

The time limit is 2 seconds,

Aniruddha (Codechef) - 7th Oct,2009 21:42:22.

The time limit is 2 seconds, not 50 seconds. The time limit for C# is 2 times the time specified. So, it would be 4 seconds.

Hi Anirudha, Thanks for your

Arvind Giri - 8th Oct,2009 09:27:26.

Hi Anirudha,

Thanks for your reply. The time mentioned in my previous mail was for 50 test cases, I don't want to discuss strategy here but time difference between best and worse case won't be much. So I was wondering if JVM loading time is taken into account.

I agree with you that time difference could be due to difference in configuration of machines.

 

Thanks

Arvind

Can somebody please post some

vipin Duleb - 8th Oct,2009 13:51:38.

Can somebody please post some sample Test cases with solutions.

No, this is a contest, nobody

Stephen Merriman - 8th Oct,2009 14:02:58.

No, this is a contest, nobody is going to give you extra hints.

So time limit is 2 secs for

Abhijeet Nagre - 8th Oct,2009 14:03:55.

So time limit is 2 secs for 50 test cases. correct?

So time limit (for C#) is 4

Abhijeet Nagre - 8th Oct,2009 14:09:35.

So time limit (for C#) is 4 secs for 50 test cases. Correct?

@Stephen I wasn't asking for

vipin Duleb - 8th Oct,2009 14:17:08.

@Stephen

I wasn't asking for hints.

@Abhijeet Yes  

Aniruddha (Codechef) - 8th Oct,2009 14:36:20.

@Abhijeet Yes

 

what is the error message i

pravinth - 9th Oct,2009 18:09:56.

what is the error message i get if memory limit exceeds?

is runtime error may mean memory limit exceed?

thanks

can i use pointers in my

pravinth - 9th Oct,2009 18:11:39.

can i use pointers in my program?

Yes

Aniruddha (Codechef) - 9th Oct,2009 18:37:05.

Yes

My program is running well

Deepika Bhansali - 10th Oct,2009 15:30:49.

My program is running well for given two test cases the only difference is that the method i have used is different from the method told above. Is that the reason my program is not successfully submitted.

The method that you use to

Stephen Merriman - 10th Oct,2009 16:02:56.

The method that you use to solve the problem is irrelevant. If you are told wrong answer, that means you are printing out the incorrect answer for one of the judge's test cases.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM: