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

No comments:

Post a Comment