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

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:44 am

dreadlord wrote: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?
I coded it in Pascal and have no problem with reading the input. Here is reading part from my Pascal program:

Code: Select all

program pr932;

var tab:array[0..31,0..31]of char;
    n,i,j:longint;

begin
     while not eof(input) do
     begin
          readln(n);
          for i:=1 to n do
          begin
               for j:=1 to n do read(tab[i,j]);
               readln;
          end;
          { ... }
     end;
end.
I have AC in 0.000.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 932 - Checking the N-Queens Problem

Post by brianfry713 » Tue Apr 08, 2014 1:30 am

This was a red check problem. I just created a dataset for it. There is no need for a special judge, I didn't include any cases in my input that have multiple correct outputs. The problem statement is now correct, there are multiple test cases.
Check input and AC output for thousands of problems on uDebug!

lucastan
New poster
Posts: 10
Joined: Sat Jul 02, 2011 6:46 am

Re: 932 - Checking the N-Queens Problem

Post by lucastan » Thu Jun 19, 2014 8:44 am

Hi all, I'm pretty sure I got this right but I keep getting WA.. any hint?

Code: Select all

#include<iostream>
#include<cstring>
using namespace std;
int row[100];
int col[100];
int d1[100];
int d2[100];
int board[35][35];
int n;

inline void set(int i, int j){row[i]=col[j]=d1[i+j]=d2[i-j+31]=1;}
inline void clear(int i, int j){row[i]=col[j]=d1[i+j]=d2[i-j+31]=0;}
inline int isset(int i, int j){return row[i] || col[j] || d1[i+j] || d2[i-j+31];}

int check(){
    for (int i=0;i < n;i++)
        for (int j=0;j < n;j++){
            if(!board[i][j])continue;
            if (isset(i,j))return 0;
            set(i,j);
        }
        
    return 1;
}

int find(){
    for (int a=1; a <= n;a++){ 
        int found=1;
        int arow, acol;
        memset(row,0,sizeof row);
        memset(col,0,sizeof col);
        memset(d1,0,sizeof d1);
        memset(d2,0,sizeof d2);

        for (int i=0;i < n;i++){
            for (int j=0;j < n;j++){
                if (board[i][j]==a){arow=i;acol=j;}
                if(board[i][j]==a ||!board[i][j])continue;
                if (isset(i,j)){i=999;found=0;break;}
                set(i,j);
            }
        }
        if(found){
            for (int i=0;i < n;i++)
                for (int j=0;j < n;j++){
                    if(!isset(i,j)){
                        if(arow == i || acol == j || arow+acol == i+j || arow-acol==i-j){
                            board[arow][acol]=0;
                            board[i][j]=1;
                            return 1;
                        }
                    }
                }
        }
    }
    return 0;
}

int main(){
    while(cin>>n){
        memset(board, 0, sizeof board);
        memset(row,0,sizeof row);
        memset(col,0,sizeof col);
        memset(d1,0,sizeof d1);
        memset(d2,0,sizeof d2);
        int f=1;
        for (int i=0;i < n;i++)
            for (int j=0;j < n;j++){
                char c;
                cin>>c;
                if (c=='X'){
                    board[i][j]=f++;
                    
                }
            }
        if(check())cout<<"YES"<<endl;
        else{
            cout<<"NO"<<endl;
            if(find()){
                cout<<"YES"<<endl;
                for (int i=0;i < n;i++){
                    for (int j=0;j < n;j++){
                        cout << (board[i][j] ? 'X':'0') ;
                    }
                    cout<<endl;
                }
            }else cout<<"NO"<<endl;
        }
        cout<<endl;
    }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 932 - Checking the N-Queens Problem

Post by brianfry713 » Thu Jun 19, 2014 10:27 pm

Print a blank line between test cases. Don't print an extra blank line at the end.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 9 (900-999)”