## 932 - Checking the N-Queens Problem

Moderator: Board moderators

New poster
Posts: 35
Joined: Wed May 02, 2007 11:48 pm
Location: Brasil

### 932 - Checking the N-Queens Problem

Hi friends,
someone have inputs and outputs AC to this problem?

New poster
Posts: 19
Joined: Sat Apr 19, 2008 11:19 pm

### Re: 932 - Checking the N-Queens Problem

Hello.

I wonder what corrected position should be given as output when there are more than one way to make the wrong input position to become correct.

For example, consider the following input:
8
00000000
000000X0
0000X000
0000000X
XX000000
000X0000
00000X00
00X00000
Which is not a valid position as there are two queens in the 5th row (starting from top). First row is free, and moving any of these two queens to the first row would give a valid position, so the following two outputs would be right:

Output #1:
NO
YES
X0000000
000000X0
0000X000
0000000X
0X000000
000X0000
00000X00
00X00000
Output #2:
NO
YES
0X000000
000000X0
0000X000
0000000X
X0000000
000X0000
00000X00
00X00000

Carlos
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Contact:

### Re: 932 - Checking the N-Queens Problem

if the description doesn't ask for a particular solution, you can output any of them.
DON'T PM ME --> For any doubt, suggestion or error reporting, please use the "Contact us" form in the web.

New poster
Posts: 19
Joined: Sat Apr 19, 2008 11:19 pm

### Re: 932 - Checking the N-Queens Problem

WARNING:

Don't try to solve this problem with a Pascal program. I believe there is some problem with the I/O in Pascal with the input file. I tried the following extremely simple program:

Code: Select all

``````program hang932;

var
TC, i, j : Integer;
car : Char;

begin
while eoln and not eof do readln; (* skip leading newlines *)
i := 1;
repeat
j := 1;
repeat
car := '.';
repeat
if eoln then
else
until (car = '0') or (car = 'X');
if j = TC then break;
inc (j);
until False;
if i = TC then break;
inc (i);
until False;
writeln ('NO');
writeln ('NO')
end.
``````
, which of course may not expect to get AC, but definitely shouldn't ever get Time Limit Exceeded, as it does. I get no problems when using this loops structure in my computer.

I believe this' something to do with the first readln(TC), as I get WA (as expected) when replacing the two outermost repeat-until loops by "for [ i | j ] := 1 to TC do". Maybe it gets zero for TC for some reason? Might this happen because the input text file contains some stranger line terminators, kind of DOS or so?

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

### Re: 932 - Checking the N-Queens Problem

Is there only one test case for this problem ?
Does anybody have some I/Os ? I'm getting WA.

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

### Re: 932 - Checking the N-Queens Problem

I just got AC...
It was because my program only handles one test case.. I don't know if we must read until end of file...

New poster
Posts: 19
Joined: Sat Apr 19, 2008 11:19 pm

### Re: 932 - Checking the N-Queens Problem

RC's wrote:I just got AC...
It was because my program only handles one test case.. I don't know if we must read until end of file...
Do you mean that you got AC because you sent a version of your program that considers more that one input case??

If so, the problem description should be revised, because it says clearly that there is only one input case.

That could be a good explaination of why there are so few AC's...

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

### Re: 932 - Checking the N-Queens Problem

I just change my program to handle more than one test case and I got AC..
If I'm not mistaken, it was the only change I made.
How about you ? Have you got AC as well ?

New poster
Posts: 19
Joined: Sat Apr 19, 2008 11:19 pm

### Re: 932 - Checking the N-Queens Problem

RC's wrote:I just change my program to handle more than one test case and I got AC..
If I'm not mistaken, it was the only change I made.
Then, definitely the problem description is wrong and confusing.
RC's wrote: How about you ? Have you got AC as well ?
Nope. So far I haven't modified my program to handle more than one test case, because I was (incorrectly) assuming that the problem description was right, as it usually is. I gave up with the problem when I made sure that my program was correct but still got WA (I supposed there were some kind of problem related to wrong text format in the input file). Now that you gave a reasonable explanation for this, I'll come back to this problem and will try it again but don't know when... Time is gold and I'm poor.

For the moment, could you please tell me how to find the end of the input? You stop when yo find zero, or something like that, for the board size, or you find EOF after the last test case with no further data afterwards?

Thank you,

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

### Re: 932 - Checking the N-Queens Problem

I use like this to handle the input

Code: Select all

``````while (scanf("%i\n", &size) != EOF)
{
......
......
for(i = 0; i < size; i++)
{
scanf(" %s ", board[i]);
........
........
}
......
......
}
``````
Hope you'll get AC soon

New poster
Posts: 19
Joined: Sat Apr 19, 2008 11:19 pm

### Re: 932 - Checking the N-Queens Problem

RC's wrote:I use like this to handle the input

Code: Select all

``...``
Hope you'll get AC soon
Thank you for the tip and your good wishes.

New poster
Posts: 19
Joined: Sat Apr 19, 2008 11:19 pm

### Re: 932 - Checking the N-Queens Problem

RC's wrote: Hope you'll get AC soon
Well, after modifying my program to consider more than one test case, I got AC.

It's certainly annoying to get stuck in one problem just because its description is clearly incorrect and confusing...

Regards, and thank you again for the tip, Robin.

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

### Re: 932 - Checking the N-Queens Problem

Now you should try another problems.
Good luck

New poster
Posts: 19
Joined: Sat Apr 19, 2008 11:19 pm

### Re: 932 - Checking the N-Queens Problem

someone have inputs and outputs AC to this problem?

It's not a very large set of I/O, but could be helpful, so I drop them right here.

Input:

Code: Select all

``````8
0000X000
X0000000
0000X00X
00000X00
00000000
000000X0
0X000000
000X0000

8
X0000000
000000X0
0000X000
0000000X
0X000000
000X0000
00000X00
00X00000

8
X0000000
000000X0
0000X000
0000000X
000X0000
000X0000
00000X00
00X00000

5
0X000
X0000
000X0
0X000
0000X

1
X

5
00X00
X0000
000X0
0X000
0000X

8
X0000000
000000X0
0000X000
0000000X
000X0000
000X000X
00000000
00X00000

8
X0000000
000000X0
0000X000
0000000X
000X0000
000X0000
00000X00
00X00000
``````
Output:

Code: Select all

``````NO
YES
0000X000
X0000000
0000000X
00000X00
00X00000
000000X0
0X000000
000X0000
YES
NO
YES
X0000000
000000X0
0000X000
0000000X
0X000000
000X0000
00000X00
00X00000
NO
YES
00X00
X0000
000X0
0X000
0000X
YES
YES
NO
NO
NO
YES
X0000000
000000X0
0000X000
0000000X
0X000000
000X0000
00000X00
00X00000
``````
Hope it helps.

Regards,

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

### Re: 932 - Checking the N-Queens Problem

Thanks to RC's for his notice about more test cases. I have lot of WA's and when I made only one change - assuming more test cases, I have AC. The problem description should be revised for real...