`/*`

* Fast N Queens solution using bits.

* Copyright (C) 2008 Pete M.

*

* This program is free software: you can redistribute it and/or modify

* it under the terms of the GNU Affero General Public License as published by

* the Free Software Foundation, either version 3 of the License, or

* (at your option) any later version.

*

* This program is distributed in the hope that it will be useful,

* but WITHOUT ANY WARRANTY; without even the implied warranty of

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

* GNU Affero General Public License for more details.

*

* You should have received a copy of the GNU Affero General Public License

* along with this program. If not, see <http://www.gnu.org/licenses/>.

*/

#include <stdio.h>

#include <sys/types.h>

#define MAXN 12

#define N (MAXN - 1)

#define MARK(a,bit) (a | (1 << bit))

#define TEST(a,bit) (a & (1 << bit))

static void placeQueen(u_int32_t y, u_int32_t x, u_int32_t dx, u_int32_t dy);

static void printSolution();

static int solution[MAXN];

int main() {

placeQueen(0, 0, 0, 0);

return 0;

}

void placeQueen(u_int32_t y, u_int32_t x, u_int32_t dx, u_int32_t dy) {

u_int32_t xpos;

u_int32_t dxpos;

u_int32_t dypos;

for(xpos = 0; xpos <= N; xpos++) {

dxpos = xpos + y;

dypos = N + xpos - y;

if(!(TEST(x, xpos) ||

TEST(dx, dxpos) ||

TEST(dy, dypos))) {

solution[y] = xpos;

if(y == N) {

printSolution();

}

else {

placeQueen(y+1, MARK(x, xpos),

MARK(dx, dxpos),

MARK(dy, dypos));

}

}

}

}

void printSolution() {

u_int32_t i;

for(i = 0; i <= N; i++) {

printf("(%d,%d)", i, solution[i]);

}

printf("\n");

}

Of course there are other solutions as well using arrays, pointers, etc...
## Monday, September 8, 2008

### N Queens Implmented With Bits...

Here is a pretty fast nQueens implementation I wrote about 5 years back. It uses bits to keep track of each queen's lanes of attack. This approach limits the size of the board you can use to n <= (b + 1)/2 where b is the number of bits in the data type used for the bit arrays. This particular implementation uses 3 separate bit arrays one each for the x, diagonal x and diagonal y axis. I've seen solutions that are even faster than this one which squeeze all of the bits into a single 64-bit type. The basic idea here is that each queen in addition to having an x and a y coordinate also has a dx and dy coordinate. For there to be no conflicts no two queens can share a coordinate in any of the 4 axises.

Subscribe to:
Posts (Atom)