## 932 - Checking the N-Queens Problem

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

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?
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
for i:=1 to n do
begin
for j:=1 to n do read(tab[i,j]);
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

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

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;
int col;
int d1;
int d2;
int board;
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

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!