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

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

great!

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

Re: great!

sonyckson wrote: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
New poster
Posts: 26
Joined: Mon Oct 25, 2004 8:11 pm
Location: Spain
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
"From lost to the river" --> Spanish quote

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...
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
New poster
Posts: 1
Joined: Sun Jul 17, 2011 7:21 am

Re: 11195 - Another n-Queen Problem

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;
unsigned int iniBoard;
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
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11195 - Another n-Queen Problem

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;

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]+1);

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

return 0;
}
Do or do not. There is no try.

tiendaotd
New poster
Posts: 12
Joined: Mon Jan 14, 2013 12:21 pm

Re: 11195 - Another n-Queen Problem

Scarecrow wrote: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;

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]+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
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11195 - Another n-Queen Problem

Thanks tiendaotd for your reply! But can you please explain a bit more?
Do or do not. There is no try.

tiendaotd
New poster
Posts: 12
Joined: Mon Jan 14, 2013 12:21 pm

Re: 11195 - Another n-Queen Problem

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
New poster
Posts: 1
Joined: Fri Sep 09, 2016 5:38 am

Re: 11195 - Another n-Queen Problem

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;

bitset<30> prevRow, rd, ld;
int row, 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 (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[]){
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