n_queen

queen1.c

#include <stdio.h>
#include <stdlib.h>

/*
 * 1マスあたり1bitなテーブルで管理しているのでメモリ消費は
 * 結構少ないと思われ。
 */

typedef	unsigned long	uint32;


uint32			board[32] = {0};
uint32			mask32 = ~((uint32)~0 << 32);

int				count = 0;


void			show_board(int n)
{
	int				i = 0;
	int				j;
	uint32			mask;
	printf("*** Answer #%d\n", count);
	for(; i<n; ++i) {
		mask = (uint32)(1) << 31;
		for(j=0; j<n; ++j, mask>>=1) {
			printf(board[i] & mask ? "Q " : ". ");
		}
		putchar('\n');
	}
}

// -1: invalid
// 0:  not invalid
int				check(int n)
{
	int				i;
	uint32			row_temp;
	uint32			row_temp2;
/*puts("checking...");*/
/*show_board(n);*/
	// check rows
	for(i=0; i<n; ++i) {
		// (x-1)&x : 0 if x is 0 or power of 2
		if((board[i]-1)&board[i]) {
			// more than two bits is set in the row
			return	-1;
		}
	}
	// check columns
	row_temp = 0;
	for(i=0; i<n; ++i) {
		if(row_temp & board[i]) {
			// 2度以上立った桁があった
			return	-1;
		}
		row_temp |= board[i];
	}
	// check ななめ
	row_temp = 0;
	row_temp2 = 0;
	for(i=0; i<n; ++i) {
		// 「/」方向、左上
		if(row_temp & (board[i] >> i)) {
			return	-1;
		}
		row_temp |= (board[i] >> i);
		// 「/」方向、右下
		if(row_temp2 & (board[i] << (n-i))) {
			return	-1;
		}
		row_temp2 |= (board[i] << (n-i));
	}
	row_temp = 0;
	row_temp2 = 0;
	for(i=0; i<n; ++i) {
		// 「＼」方向、右上
		if(row_temp & (board[i] << i)) {
			return	-1;
		}
		row_temp |= (board[i] << i);
		// 「＼」方向、左下
		if(row_temp2 & (board[i] >> (n-i))) {
			return	-1;
		}
		row_temp2 |= (board[i] >> (n-i));
	}
/*puts("ok!!");*/
	return	0;
}


void			nqueen(int n, int current)
{
	int				j;
	uint32			mask = (uint32)(1) << 31;
	// current行目(0オリジン)のビットを立てにいく
	for(j=0; j<n; ++j) {
		// for each bit
		board[current] |= mask;
		if(check(n) == 0) {
			if(current == n-1) {
				// this is it!
				++count;
				show_board(n);
			} else {
				// current < n-1
				// 可能性あり
				nqueen(n, current+1);
			}
		}
		board[current] &= ~mask & mask32;
		mask >>= 1;
	}
}


int				main(int argc, char **argv)
{
	int				n;
	if(sizeof(uint32) < 4) {
		fprintf(stderr, "insufficient long size: %ld (expected >=4)", sizeof(uint32));
	}
	if(argc < 2) {
		fprintf(stderr, "usage: nqueen <number>\n");
		return	1;
	}
	n = strtol(argv[1], NULL, 10);
	if(n < 1 || n > 32) {
		fprintf(stderr, "invalid argument: n=%d (expected 1-32)\n", n);
	}

	nqueen(n, 0);

	/*fprintf(stdout, "# of answers: %d", count);*/
	fprintf(stderr, "# of answers: %d\n", count);

	return	0;
}

queen2.c

#include <stdio.h>
#include <stdlib.h>

/*
 * queen1.cとは違い、素朴な実装。盤面を使わず、はじめから
 * Qの重複確認をしつつ試行する方針。queen1.cなど比較にならない
 * ほど速度でた。くやしい
 */

char			column[32] = {0};
// 「＼」方向, row+column
char			naname1[61] = {0};
// 「/」方向, row-column+31
char			naname2[61] = {0};

int				coords[32] = {0};
int				count = 0;

char			row_str[] = ". . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ";


void			show_board(int n)
{
	int				i, r;
	printf("*** Answer #%d\n", count);
	for(i=0; i<n; ++i) {
		r = (coords[i] << 1);
		row_str[r] = 'Q';
		puts(row_str);
		row_str[r] = '.';
	}
}


// n > level
void			nqueen(int n, int level)
{
	int				j;
	// level行目にQを入れることを試みる
	for(j=0; j<n; ++j) {
		if(!column[j]) {
			// (上下と)左右で重複無し
			// 斜めで確認
			if(!naname1[level+j] && !naname2[level-j+31]) {
				// 斜めも重複無し
				column[j] = 1;
				naname1[level+j] = 1;
				naname2[level-j+31] = 1;
				coords[level] = j;
				if(n == level+1) {
					// this is it!
					++count;
					show_board(n);
				} else {
					nqueen(n, level+1);
				}
				column[j] = 0;
				naname1[level+j] = 0;
				naname2[level-j+31] = 0;
			}
		}
	}
}


int				main(int argc, char **argv)
{
	int				n;
	if(argc < 2) {
		fprintf(stderr, "usage: nqueen <number>\n");
		return	1;
	}
	n = strtol(argv[1], NULL, 10);
	if(n < 1 || n > 32) {
		fprintf(stderr, "invalid argument: n=%d (expected 1-32)\n", n);
	}

	row_str[(n<<1) + 1] = '\0';
	nqueen(n, 0);

	/*fprintf(stdout, "# of answers: %d\n", count);*/
	fprintf(stderr, "# of answers: %d\n", count);

	return	0;
}