11195 - Another n-Queen Problem

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11195 - Another n-Queen Problem

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 :D

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

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?
Self judging is the best judging!

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

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 :D )

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

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)
Self judging is the best judging!

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

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
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Mon Apr 02, 2007 3:17 am

wow! I am reallu surprised :oops:

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!

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

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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Mon Apr 02, 2007 9:11 am

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

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

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

>> shanto86
Yes.

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

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

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

what kinda complementary?
Self judging is the best judging!

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

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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

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

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.

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

Re: nice problem :)

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.

Post Reply

Return to “Volume 111 (11100-11199)”