Page **2** of **2**

### great!

Posted: **Thu Apr 05, 2007 12:20 am**

by **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.

### Re: great!

Posted: **Thu Apr 05, 2007 9:38 am**

by **rio**

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.

Posted: **Sat Sep 29, 2007 12:51 pm**

by **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

Posted: **Sat Dec 08, 2007 5:07 am**

by **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.

### Re: 11195 - Another n-Queen Problem

Posted: **Sun Jul 17, 2011 7:27 am**

by **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;
}
```

### Re: 11195 - Another n-Queen Problem

Posted: **Sat Feb 02, 2013 11:17 am**

by **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;
}
```

### Re: 11195 - Another n-Queen Problem

Posted: **Mon Feb 04, 2013 11:00 am**

by **tiendaotd**

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[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) .

### Re: 11195 - Another n-Queen Problem

Posted: **Wed Feb 06, 2013 7:05 pm**

by **Scarecrow**

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

### Re: 11195 - Another n-Queen Problem

Posted: **Tue Feb 19, 2013 8:51 am**

by **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.

### Re: 11195 - Another n-Queen Problem

Posted: **Fri Sep 09, 2016 6:28 am**

by **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;
}
```