11195 - Another n-Queen Problem

[sonyckson]

Thanks rio.... i did the program, and after some tests i realized which was the main idea... i also think its an incredible idea.. did you realized your self about that?? i suppose the code will be much faster after implementing that trick. thanks. sonyckson.

[rio]

did you realized your self about that??

No. Its a technique writen in book "Hacker's Delight"
http://www.amazon.com/Hackers-Delight-H ... 0201914654
Contents are mainly about low level hack.
If you haven't read it, I thinks its worth reading for study and fun.

[luishhh]

Does anybody know a trick to compute n from a mask of the form (1<<n)? I suppose it will speedup my program because now I have a loop to compute it

[CMG]

To find n for 1<<n just minus 1 from the number and count the number of set bits in the number. Counting the number of set bits can be done in 6 steps using bitwise operations. I suggest you search for it on the web.

Im excited I finally got AC after trying 3 times being this is my first attempt at submitting code to the judge acm problems. Took a few tries to get the formatting right and fix a few input/output bugs. Im amazed Rio that you got 0.610s on your code. I had started this problem a little before submitting it, and was basically like the others in this thread my program in java had a time of 13.8s to do the 14x14 square with no blocks and reading through this thread the first time i got it down to 9.8s then with some more optimazation and the use of bit masking I got the 14x14 down to 0.4s which was a huge improvement. I don't think the submition time I got of 1.080s will be improved upon.

[k9119911]

Hi all

I used bitmask and backtracking to solve this problem and same for problem 750.
For problem 750, I got AC. Unfortunately, I got many WAs when solving this problem.
Below is my code, can anybody help me? Thanks in advance.

Code: Select all

#include <stdio.h>
#include <string.h>

unsigned int board[20];
unsigned int iniBoard[20];
int size;
int sols;

int isSafe(int row, int col)
{
	unsigned int posMask = (0x1 << (31 - col));

	if (iniBoard[row] & posMask)
		return 0;

	if (board[row] & 0xFFFFFFFF)
		return 0;

	int i, j;

	for (i=row, j=posMask; i>=0 && j!=0; i--, j<<=1) {
		if (board[i] & j)
			return 0;
	}

	for (i=row, j=posMask; i<size && j!=0; i++, j<<=1) {
		if (board[i] & j)
			return 0;
	}
}
/*
void output()
{
	int i;

	for (i=0; i<size; i++) {
		printf("%X\n", board[i]);
	}
}*/

void putQueens(int colPos)
{
	if (colPos == size) {
		sols++;
		return;
	}

	int i;

	for (i=0; i<size; i++) {
		if (isSafe(i, colPos)) {
			board[i] |= (0x1 << (31 - colPos));
			putQueens(colPos + 1);
			board[i] &= ~(0x1 << (31 - colPos));
		}
	}
}

int main()
{
	int caseN = 1;

	freopen("a.in", "r", stdin);

	while (scanf("%d\n", &size) != EOF && size != 0) {
		int i, j;
		memset(board, 0, sizeof(unsigned int) * 16);
		memset(iniBoard, 0, sizeof(unsigned int) * 16);
		sols = 0;
		for (i=0; i<size; i++) {
			for (j=0; j<size; j++) {
				char tmp;

				scanf("%c\n", &tmp);
				if (tmp == '*') {
					iniBoard[i] |= 1 << (31 - j);
				}
			}
		}
		putQueens(0);
		printf("Case %d: %d\n", caseN++, sols);
	}

	return 0;
}

[Scarecrow]

I used bitmasking and backtracking for the solution. And getting TLE. In my PC, the program runs for about 4s for n = 14. And for n<14, runs fast. So, a bit of pruning may get it AC. Someone can help me speeding up the program a bit?

Code: Select all

#include<cstdio>
using namespace std;

int n, r, ld, rd, soln;
char B[16][16];

bool placable(int col, int row)
{
    if(B[row][col]=='*' || (r & (1<<(row-1))) || (ld & (1<<(n-row+col-1))) || (rd & (1<<(2*n-row-col-1))))
        return false;
    return true;
}

void backtrack(int col)
{
    for(register int row = 1; row<=n; ++row)
        if(placable(col, row))
        {
            int r = 1<<(row-1), ld = 1<<(n-row+col-1), rd = 1<<(2*n-row-col-1);
            ::r |= r;
            ::ld |= ld;
            ::rd |= rd;

            if(col==n)
                soln++;
            else
                backtrack(col+1);

            ::r &= ~r;
            ::ld &= ~ld;
            ::rd &= ~rd;
        }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int t = 1;
    register int i;

    while(scanf("%d", &n), n)
    {
        while(getchar()!='\n');
        for(i = 1; i<=n; ++i)
            gets(&B[i][0]+1);

        soln = 0;
        backtrack(1);
        printf("Case %d: %d\n", t++, soln);
    }

    return 0;
}

[tiendaotd]

I used bitmasking and backtracking for the solution. And getting TLE. In my PC, the program runs for about 4s for n = 14. And for n<14, runs fast. So, a bit of pruning may get it AC. Someone can help me speeding up the program a bit?

Code: Select all

#include<cstdio>
using namespace std;

int n, r, ld, rd, soln;
char B[16][16];

bool placable(int col, int row)
{
    if(B[row][col]=='*' || (r & (1<<(row-1))) || (ld & (1<<(n-row+col-1))) || (rd & (1<<(2*n-row-col-1))))
        return false;
    return true;
}

void backtrack(int col)
{
    for(register int row = 1; row<=n; ++row)
        if(placable(col, row))
        {
            int r = 1<<(row-1), ld = 1<<(n-row+col-1), rd = 1<<(2*n-row-col-1);
            ::r |= r;
            ::ld |= ld;
            ::rd |= rd;

            if(col==n)
                soln++;
            else
                backtrack(col+1);

            ::r &= ~r;
            ::ld &= ~ld;
            ::rd &= ~rd;
        }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int t = 1;
    register int i;

    while(scanf("%d", &n), n)
    {
        while(getchar()!='\n');
        for(i = 1; i<=n; ++i)
            gets(&B[i][0]+1);

        soln = 0;
        backtrack(1);
        printf("Case %d: %d\n", t++, soln);
    }

    return 0;
}

Instead of loop all row for each column , you can use a "mask" of used row and quick "jump" to the row that has no queen. For this you will not have to change your backtracking much, but the run time is bad ( mine is ~4.8 s) .

[Scarecrow]

Thanks tiendaotd for your reply! But can you please explain a bit more?

[tiendaotd]

Consider using a "mask" to check whether a row already has a queen or not ( available ) . This mask can be like this :

Code: Select all

1010100 // length = 7 for 7 row, index from 0 to 6

Bit 0 for "not available".
Bit 1 for "available" .

Here you placed queens in row 0, 1, 3 and 5 ( from right to left ) . It's obvious that the next available row to check is row 2, 4, 6. So in this recursion you have to "jump" to these 3 row quickly, by extract the index of the first bit 1 of this mask.

Remember that in the next backtrack recursion, the mask must turn off only the next bit 1 . So the mask for using in next backtrack recursion will be :

Code: Select all

1010000 // turn off ONLY bit 2
1000100 // turn off ONLY bit 4, release bit 2
0010100 // turn off ONLY bit 6, release bit 4

To extract the next bit 1 in a mask, you may want to use an array id[1<<n] with id[k] = p mean k = (1<<p) . If you still not AC, I'll provide some code brief.

[deepakaggarwal]

Hello !
I am not able to identify the error I am making. I have read most web resources and spent 4 days on one problem. Please help.and see to it. Judge give WA verdict.

Code: Select all

#include <cstdio>
#include <cmath>
#include <cstring>
#include <bitset>
#include <iostream>
using std::abs;
using std::bitset;
using namespace std;

bool bad[15][15];
bitset<30> prevRow, rd, ld;
int row[16], N, sol;
int d;
#define rcd(r,c,d) r - c + N - 1
//#define rcd(r,c,d) (r - c + d)%d

bool place(int r, int c){
	// return !(prevRow[r] || rd[rcd(r,c,d)] || ld[r + c]);
	return (!prevRow[r] && !rd[rcd(r,c,d)] && !ld[r + c]);
}

void print(int arr[]){
	for (int i = 0; i < N; ++i)
		printf("%d ", arr[i]);
	printf("\n");
}

void queen(int c){
	if (c == N) {
		++sol;
		return;
	}

	for (int r = 0; r < N; ++r){
		if (bad[r][c]) continue;	//bad cell
		if (place(r,c)){
			prevRow[r] = rd[rcd(r,c,d)] = ld[r + c] = 1;
			queen(c + 1);
			prevRow[r] = rd[rcd(r,c,d)] = ld[r + c] = 0;
		}
	}
}

void print2d(bool arr[][16]){
	for (int i = 0; i < N; ++i){
		for (int j = 0; j < N; ++j)
			printf("%d ", arr[i][j]);
		printf("\n");
	}
}

int main(){
	char c;
	int cnt = 0;

	while (scanf("%d", &N) && N != 0){
		getchar(); 	//consumes linefeed
		std::memset(bad, false, sizeof N*N);
		sol = 0;
		d = 2 * N - 1;		//no of either right or left diagonals
		//reading input cells
		for (int i = 0; i < N; ++i){
			for (int j = 0; j < N; ++j){
				c = getchar();
				if (c == '*') bad[i][j] = true;
			}
			getchar(); 	//consumes line feed
		}
		queen(0);
		printf("Case %d: %d\n", ++cnt, sol);
		// cout << rd << endl << ld << endl << prevRow << endl;
	}
	return 0;
}