CodeChef is a non-commercial competitive programming community
Login
Username (New User? Signup) Password (Forgot Password?)
Signup
Login or
Signup with
Connect
Note
  • Publicize your achievements on your Facebook Wall.
  • Challenge your friends or ask them for help.

Site Navigation

  • PRACTICE
    • Easy
    • Medium
    • Hard
    • Challenge
    • Peer
  • COMPETE
    • February CookOff
    • February Long Contest
    • January CookOff
  • DISCUSS
    • Wiki
    • Forums
    • Blog
    • Twitter
  • COMMUNITY
    • CodeChef Meetups
    • Campus Chapters
    • Host your Contest
    • User Groups
    • CodeChef TechTalks
    • All Educational Initiatives
    • Event Calendar
  • HELP
    • Frequently Asked Questions
    • FAQ for problem setters
    • Problem Setting
    • Ranks
    • Tutorials
  • ABOUT
    • About CodeChef
    • Team CodeChef
    • Press Room
    • CodeChef Financials
    • CodeChef Sponsorships
    • CEO's Corner
    • Contact Us
    • About Directi
Home » Compete » October 2009 (Contest IX) » A puzzle game

A puzzle game

Problem code: H1

  • All Submissions

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


  • Submit

Comments

  • Login or Register to post a comment.

too difficult!!

kumar.anujsjc @ 2 Oct 2009 06:30 AM

too difficult!!

hay any body have any idea of

marutinaidu @ 3 Oct 2009 12:12 AM
hay any body have any idea of solution

Hmm.. I guess you must have

flying_ant @ 3 Oct 2009 02:23 AM

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

In the input, are the

sivaraman @ 3 Oct 2009 09:56 AM

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

elupi @ 3 Oct 2009 12:58 PM

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

admin @ 3 Oct 2009 02:18 PM

@sivaraman They are separated by a space

@balraja Please take a look at Sample Solutions

I am using recursion. But it

hiprakhar @ 4 Oct 2009 05:57 PM

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

triplem @ 5 Oct 2009 02:08 AM

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

Hi Admin   My  code is

jaydeep @ 5 Oct 2009 11:21 AM

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

admin @ 5 Oct 2009 02:52 PM

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

I' ve submit one solution

liubiaoyong @ 5 Oct 2009 05:46 PM

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 @ 7 Oct 2009 06:04 PM

@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 @ 7 Oct 2009 06:05 PM

Shouldn't time limit vary according to language?

Yes, the time limit does in

admin @ 7 Oct 2009 06:29 PM

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

Aby @ 7 Oct 2009 09:27 PM

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,

admin @ 7 Oct 2009 09:42 PM

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 @ 8 Oct 2009 09:27 AM

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

Duleb @ 8 Oct 2009 01:51 PM

Can somebody please post some sample Test cases with solutions.

No, this is a contest, nobody

triplem @ 8 Oct 2009 02:02 PM

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

So time limit is 2 secs for

Aby @ 8 Oct 2009 02:03 PM

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

So time limit (for C#) is 4

Aby @ 8 Oct 2009 02:09 PM

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

@Stephen I wasn't asking for

Duleb @ 8 Oct 2009 02:17 PM

@Stephen

I wasn't asking for hints.

@Abhijeet Yes  

admin @ 8 Oct 2009 02:36 PM

@Abhijeet Yes

 

what is the error message i

javasoul @ 9 Oct 2009 06:09 PM

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

javasoul @ 9 Oct 2009 06:11 PM

can i use pointers in my program?

Yes

admin @ 9 Oct 2009 06:37 PM

Yes

My program is running well

Deepika Bhansali @ 10 Oct 2009 03:30 PM

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

triplem @ 10 Oct 2009 04:02 PM

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:

Programming Competition Fetching successful submissions
Directi Go for Gold
CodeChef is a global programming communityCodeChef hosts online programming competitions
CodeChef is a non-commercial competitive programming community
  • About CodeChef
  • About Directi
  • CEO's Corner
  • C-Programming
  • Programming Languages
  • Contact Us
© 2009 Directi Group. All Rights Reserved. CodeChef uses SPOJ © by Sphere Research Labs
In order to report copyright violations of any kind, send in an email to copyright@codechef.com
CodeChef a product of Directi
The time now is:
CodeChef - A Platform for Aspiring Programmers

CodeChef was created as a platform to help programmers make it big in the world of computer programming. At CodeChef we work hard to revive the geek in you by hosting programming contests on a monthly basis. We also aim to have training sessions and events related to online programming for programmers around the world. Apart from providing a platform for programming competitions, CodeChef also has various tutorials and forum discussions to help those who are new to the world of computer programming.

Practice Section - A Place to hone your 'Computer Programming Skills'

Try your hand at one of our many practice problems and submit your solution in a language of your choice. Our judge accepts solutions in over 35+ programming languages. Online programming was never this much fun! Receive points, and move up through the CodeChef ranks. Use our practice section to better prepare yourself for the multiple programming competitions that take place through-out the month on CodeChef.

Compete - Monthly Programming Contests and Cook-offs

Here is where you can show off your computer programming skills. Take part in our 10 day long monthly programming contests and the shorter format Cook-off programming contests. Put yourself up for recognition and win great prizes. Prizes worth up to Rs.20,000 and $700 are up for grabs every month along with lots more CodeChef goodies.

Discuss

Are you new to computer programming? Do you need help with algorithms? Then be part of CodeChefs Forums and interact with all our programmers love helping out other programmers and share their ideas.

CodeChef Community

As part of our Educational initiative, we give institutes the opportunity to associate with CodeChef in the form of Campus Chapters. Hosting online programming competitions is not the only feature on CodeChef. Be a part of the CodeChef community through CodeChef meetups and techtalks. You can also host a programming contest for your institute on CodeChef and be a guest author on our blog.

Domain Name Registration, Web hosting, and Website Design provided by BigRock.com