11195 - Another n-Queen Problem

Spykaj · Post by **Spykaj** » Sat Mar 31, 2007 11:18 pm

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 · Post by **shanto86** » Sun Apr 01, 2007 3:13 am

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?

rio · Post by **rio** » Sun Apr 01, 2007 3:33 am

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 · Post by **shanto86** » Sun Apr 01, 2007 3:44 am

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)

rio · Post by **rio** » Sun Apr 01, 2007 8:37 pm

I runned your code with my PC and got runtime 11.7~ sec with some testcase.
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];
      }
}

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 · Post by **sunny** » Sun Apr 01, 2007 10:02 pm

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 · Post by **shanto86** » Mon Apr 02, 2007 3:17 am

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?

rio · Post by **rio** » Mon Apr 02, 2007 5:02 am

>> 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 · Post by **shanto86** » Mon Apr 02, 2007 9:11 am

thats great! by -tmp & tmp u seeing which is the next available spot right?

rio · Post by **rio** » Mon Apr 02, 2007 2:21 pm

>> shanto86
Yes.

----
Another idea found.

Now the codes runs at 1.8~ sec.
Hint: Complementary Set

shanto86 · Post by **shanto86** » Mon Apr 02, 2007 3:06 pm

what kinda complementary?

rio · Post by **rio** » Tue Apr 03, 2007 4:59 pm

(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 · Post by **shanto86** » Tue Apr 03, 2007 8:05 pm

interesting!

sonyckson · Post by **sonyckson** » Wed Apr 04, 2007 3:27 am

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 · Post by **rio** » Wed Apr 04, 2007 9:27 am

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.

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++ )

Sory but I don't know any links.

OJ Board

11195 - Another n-Queen Problem

11195 - Another n-Queen Problem

nice problem :)

Re: nice problem :)