932 - Checking the N-Queens Problem

All about problems in Volume 9. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

932 - Checking the N-Queens Problem

Post by adelar » Wed Dec 05, 2007 6:01 pm

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

thanks in advance.

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

Re: 932 - Checking the N-Queens Problem

Post by dreadlord » Sat Apr 19, 2008 11:38 pm

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
Any clue about this?

Thank you in advance.

User avatar
Carlos
System administrator
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Location: Valladolid, Spain
Contact:

Re: 932 - Checking the N-Queens Problem

Post by Carlos » Mon Apr 21, 2008 3:01 pm

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.

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

Re: 932 - Checking the N-Queens Problem

Post by dreadlord » Wed Apr 23, 2008 1:41 pm

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 *)
    readln (TC);
    i := 1;
    repeat
        j := 1;
        repeat
            car := '.';
            repeat
                if eoln then
                    readln
                else
                    read (car)
            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

Post by RC's » Tue May 20, 2008 3:33 pm

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

Post by RC's » Tue May 20, 2008 4:26 pm

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...

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

Re: 932 - Checking the N-Queens Problem

Post by dreadlord » Tue May 20, 2008 6:28 pm

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

Post by RC's » Wed May 21, 2008 3:07 am

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 ?

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

Re: 932 - Checking the N-Queens Problem

Post by dreadlord » Wed May 21, 2008 10:49 am

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

Post by RC's » Wed May 21, 2008 4:53 pm

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 :D

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

Re: 932 - Checking the N-Queens Problem

Post by dreadlord » Wed May 21, 2008 7:19 pm

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

Code: Select all

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

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

Re: 932 - Checking the N-Queens Problem

Post by dreadlord » Thu May 22, 2008 1:10 pm

RC's wrote: Hope you'll get AC soon :D
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... :x

I shall complain about this.

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

Post by RC's » Thu May 22, 2008 5:55 pm

Congratulations, dreadlord...
Now you should try another problems.
Good luck :D :wink:

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

Re: 932 - Checking the N-Queens Problem

Post by dreadlord » Fri May 23, 2008 12:03 am

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

thanks in advance.
Hi, adelar.

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

Post by jurajz » Thu Jun 26, 2008 8:39 am

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...

Post Reply

Return to “Volume 9 (900-999)”