The N Queens Puzzle RevisitedProblem code: J3 |
All submissions for this problem are available.
Johnny, a computer science student from the Bytelandian Technological University (BTU), has finally managed to write a program to solve the N queens problem. However, his version of the N queens problem is not really all that similar to the classical one.
Recall that in the N queens problem, there is a square chessboard of size NxN. The goal is to put N queens on the chessboard so that no two queens would be able to attack each other.
In Johnny's version of the problem (which he states to be "much harder" than the original one), there are K "blocked" squares given on the chessboard. The goal is still the same: to put N queens on the chessboard such that no two queens would be able to attack each other. However, there are some differences due to the existence of blocked squares. First, a queen cannot be put on a blocked square. Secondly, two queens are considered to be able to attack each other only if there is no blocked square between them. Finally, there must be exactly one queen on every column of the board.
Johnny claims that his program solves the above problem very effectively. He generates some test cases (which his program can solve within minutes) to challenge you. You know the method Johnny used to generate the test case. For a given N, Johnny randomly picks a number K between 1 and N2/2 with equal probability. After that, Johnny picks K blocked squares on the chess board. Any combinations of K squares can be picked with equal probability.
Write a program that can solve Johnny's test cases within seconds.
Input
The first line contains t, the number of test cases (about 5). Then t test cases follow. Each test case has the following form:
- The first line contains two integers N and K (8 <= N <= 500, 1 <= K <= N2/2)
- Each line in the next K lines contains two integers i, j which are the row and the column number of a blocked square (1 <= i, j <= N)
Each test case's input is separated by a blank line. The rows and the columns of the chessboard are numbered from 1 to N. There is always a solution for each test case.
Output
For each test case, print a single line containing N integers a1, a2, ..., aN in which ai is the row number of the queen in column i. Any correct solution will be accepted.
Example
Input
1
8 15
7 7
3 1
7 1
4 8
8 3
6 5
4 4
2 1
8 2
6 3
3 7
7 6
2 3
1 2
6 4
Output
4 2 7 5 2 4 6 8
| Author: | admin |
| Date Added: | 15-10-2009 |
| Time Limit: | 1 - 3 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
is there a blank line after
is there a blank line after the no. of testcases t i.e 1 here
blank line after 1 or not
Yes.
Yes.
How can i take randomly n and
How can i take randomly n and k values
Kola: you don't have to. Let
Kola: you don't have to. Let Johnny worry about that part :^)
can anyone tell me the format
can anyone tell me the format of the input and out of many test cases because each time I submit a working solution it gives me wrong submition. Does the follwing format correct?
<Test Cases Number>
<Empty Line>
<Case1>
<Empty Line>
<Case2>
<Empty Line>
<Case3>
<Empty Line>
<Answer Case1>
<Answer Case2>
<Answer Case3>
Wassim: I can see you are
Wassim: I can see you are using C++. IMO you don't have to worry about stuff line blank lines if you use scanf/cin.
so why it gives me wrong
so why it gives me wrong answer? I have tried my code on the above sample and it gave me different solution but also valid.Aslo, I ve tried it on other random solutions and it worked to. Therefore, I thought tht the problem may be beacause of the format of the output
Yeah, It wouldn't really kill
Yeah, It wouldn't really kill them to give TWO test cases.
Are there any special cases,
Are there any special cases, or boundary conditions involved ? I know it is not wise to ask for test cases, but I am stuck at wrong answer :(.
I'm afraid you won't get
I'm afraid you won't get hints until after the contest.
My error message says that
My error message says that the program ran for 0.00 seconds using 1.8 MiB but produced the wrong result! Why is the time 0.00 seconds ? What does this imply ?
It implies you got a wrong
It implies you got a wrong answer very quickly :P
^^Haha! But seriously, all
^^Haha!
But seriously, all this question has done is make me feel very, very stupid. :|
This question on Topcoder
This question on Topcoder would have caused either reaalllyyyy low submissions or reallllyyyyyy high challenge cases.. :)
@Rajat - this kind of problem
@Rajat - this kind of problem cant be given in topcoder. Specially when they guarantee that all the testcases are randomly generated, so the question of challenge doesnt arise.
its really tough to analyse
its really tough to analyse these kind of problems, i hope somebody would put a nice tutorial in wiki for solving constraint satisfaction problem like sudokux, nqueens in polynomial time and different algorithms to solve these like dancing links, forward search or min conflict heuristic after the contest gets over.
I saw the solutions in the
I saw the solutions in the successful submissions, and it seemed pretty straight forward.. I mean take a col, place a queen, update the board, and move to next col. Roll back if necessarsy and so on!
Can anyone tell if there are some cornor cases which I left, or *challenges* which were specific to this problem ?
I don't think there is any
I don't think there is any corner cases, it's a pretty straightforward as you mentioned.