## 11195 - Another n-Queen Problem

**Moderator:** Board moderators

### 11195 - Another n-Queen Problem

http://acm.uva.es/p/problemstatnew.php?prob=11195

Hi, I have accepted in 14 seconds, but limit is 15s

How to improve speed ? It's strange problem. I have almost all in arrays and still high time...

Hi, I have accepted in 14 seconds, but limit is 15s

How to improve speed ? It's strange problem. I have almost all in arrays and still high time...

Well in that case please tell me what could i have done in this:

my code takes 14sec in my pc to evaluate 14*14 grid. (no block)

Code: Select all

```
#pragma warning(disable:4786)
#include<stdio.h>
#include<string.h>
#include<map>
using namespace std;
int col,CNT;
int dia1,dia2;
int n;
int row[20];
int cnt[20];
int XX;
int p2[30];
void PLACE(int at)
{
int i,ok,j,temp,x;
int prev,now;
int ff,kk;
if(at==n)
{
CNT++;
return;
}
for(i=0;i<n;i++)
if(!(col&(p2[i])) && !(row[at]&(p2[i])) && !(dia1&(p2[at+i])) && !(dia2&(p2[at-i+n-1])) )
{
col=col^p2[i];
dia1^=p2[at+i];
dia2^=p2[at-i+n-1];
ok=1;
for(j=at+1;j<n && ok;j++)
{
ff=((dia2>>(j))&(XX));
kk=0;
for(x=0;x<n;x++)
{
kk=(kk<<1) | (ff&1);
ff>>=1;
}
temp=col | row[j] | ((dia1>>(j))&(XX)) | kk;
if(temp==XX)
ok=0;
}
if(ok)
PLACE(at+1);
col=col^p2[i];
dia1^=p2[at+i];
dia2^=p2[at-i+n-1];
}
}
int main()
{
int ks=0;
int i,j;
char B[20][20];
int ok;
int x;
int p;
int ans[]={0,0, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184 };
p2[0]=1;
for(i=1;i<30;i++)
p2[i]=p2[i-1]<<1;
while(scanf("%d",&n)!=EOF && n)
{
XX=p2[n]-1;
dia1=dia2=0;
printf("Case %d: ",++ks);
for(i=0;i<n;i++)
scanf("%s",B[i]);
ok=1;
p=0;
for(i=0;i<n;i++)
{
cnt[i]=row[i]=0;
for(j=0;j<n;j++)
{
cnt[i]+=(x=(B[i][j]=='*'));
if(x)
row[i]|=p2[j];
p|=x;
}
if(cnt[i]==n) ok=0;
}
if(p==0)
{
printf("%d\n",ans[n]);
continue;
}
if(!ok)
{
printf("0\n");
continue;
}
CNT=col=0;
PLACE(0);
printf("%d\n",CNT);
}
return 0;
}
```

Self judging is the best judging!

Few points to change.

1. Your trying to prune, but its bringing about an adverse result. PLACE() could be simplized:

Code: Select all

```
void PLACE(int at)
{
if(at==n) {
CNT++;
return;
}
for(int i=0;i<n;i++)
if(!(col&(p2[i])) && !(row[at]&(p2[i])) && !(dia1&(p2[at+i])) && !(dia2&(p2[at-i+n-1])) ) {
col=col^p2[i];
dia1^=p2[at+i];
dia2^=p2[at-i+n-1];
PLACE(at+1);
col=col^p2[i];
dia1^=p2[at+i];
dia2^=p2[at-i+n-1];
}
}
```

2. Don't need p2[].

Code: Select all

```
...
if(!(col & b) && !(row[at] & b) && !(dia1 & (1 << (at+i))) && !(dia2 & (1 << (at-i+n-1))) ) {
...
```

3. Change variable col, dia1, and dia2 to argument.

Code: Select all

```
void PLACE(int at, int col, int dia1, int dia2)
{
if(at==n) {
CNT++;
return;
}
for(int i = 0, b = 1; i < n; i++, b <<= 1)
if(!(tmp & b) && !(row[at] & b) && !(dia1 & (1 << (at+i))) && !(dia2 & (1 << (at-i+n-1))))
PLACE(at+1, col ^ b, dia1 ^ (1 << (at+i)), dia2 ^ (1 << (at-i+n-1)));
}
```

The code become more simple and fast, but still not fast enough to avoid TLE.

Its remained for you. Good luck.

if n<14 then backtrack. but if n=14 then checked how many of the pre-stored solutions are valid for the given board.

it took 6.2xx secs.

rio,

i am really curious 2 know that how can it be done in less than 3 secs.

so if u dont mind can u pls pm me ur code.

OK. I'll send the code which runs at 3.4~ sec (Optimizing this code with a little dirty way runs at 2.7~ sec).

There's no comments in the code, but I think you could understand it easly (Its less than 50 rows).

I'm also interested with your precalculation way. Cound you send me your code ?

Mixing our ideas might make a faster program.

>> shanto86

I think you don't need special prune. Just be more efficient.

**Hint1:**

Code: Select all

```
void PLACE(int at, int col, int dia1, int dia2)
{
if(at==n) {
CNT++;
return;
}
int tmp = ( ??? operation with col, row[at], dia1, dia2 ...);
for(int i = 0, b = 1; i < n; i++, b <<= 1)
if(!(tmp & b))
PLACE(at+1, .....);
}
```

**Hint2:**(Progressing Hint1)

Code: Select all

```
-tmp & tmp
```

If there are many bad squares, the ordinary counting way (counting the solutions without using bad squares) is fast, but if there are only few bad squares, counting solutions with using at least one bad squares is faster.(without using bad squares) = (maximum) - (with using at least one bad square)

So I switched the counting way with the number of bad squares.

### nice problem :)

Hello!!!.. i did my program with backtracking, complementary sets, and a little more ideas...it was not very efficient (not at all )...so I got 10...seconds... I have been reading your posts, but i cant understand what is that of -tmp&tmp.... I also wonder if you could give me any link to any good place to read about this kind of optimizations ( in c, c++ ). Thank you very much. sonyckson.

### Re: nice problem :)

Write a little program that prints the bits and look how -tmp & tmp works. I think you could understand it.sonyckson wrote:Hello!!!.. i did my program with backtracking, complementary sets, and a little more ideas...it was not very efficient (not at all )...so I got 10...seconds... I have been reading your posts, but i cant understand what is that of -tmp&tmp....

Sory but I don't know any links.sonyckson wrote:I also wonder if you could give me any link to any good place to read about this kind of optimizations ( in c, c++ )