## 11195 - Another n-Queen Problem

Moderator: Board moderators

Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

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

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
i was getting tle. i used bitmap to store the column, and two diagonal status so that at any step i can check whether any row is already covered.

can any one tell me how to improve this process?
Self judging is the best judging!

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
I did the same thing. Backtrack + Bitmap. No other (algorithm level) tricks.
I think this problem is an implementaion hack problem.
Rujia Liu's Present 1: A Tiny Contest of Brute Force
(I love these kind of problems. Thanks to Rujia Liu )

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
Well in that case please tell me what could i have done in this:

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;
}
``````
my code takes 14sec in my pc to evaluate 14*14 grid. (no block)
Self judging is the best judging!

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
I runned your code with my PC and got runtime 11.7~ sec with some testcase.
Few points to change.

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];
}
}
``````
runtime -> 7.8~ sec.

2. Don't need p2[].

Code: Select all

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

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)));
}
``````
runtime -> 6.9~ sec.

The code become more simple and fast, but still not fast enough to avoid TLE.
Its remained for you. Good luck.

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
i just precalculated all possible solutions for n=14 with a very naive backtracking.
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.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
wow! I am reallu surprised

but one think i could not understand, why using p2[] should be slower? i thought 1<<k should be slower.

anyway, i dont have any idea how to prune more while my beforehand pruning consumed too much time any hint?
Self judging is the best judging!

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
>> sunny
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
``````

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
thats great! by -tmp & tmp u seeing which is the next available spot right?
Self judging is the best judging!

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
>> shanto86
Yes.

----
Another idea found. Now the codes runs at 1.8~ sec.
Hint: Complementary Set

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
what kinda complementary?
Self judging is the best judging!

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
(without using bad squares) = (maximum) - (with using at least one bad square)
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.
So I switched the counting way with the number of bad squares.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
interesting!
Self judging is the best judging!

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

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

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

### Re: nice problem :)

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....
Write a little program that prints the bits and look how -tmp & tmp works. I think you could understand it.