Dumb Eight Queen Solution in C

eightqueen.c

/*
 *		8-Queen problem solution in C
 *		written by Asad ur Rehman <asad.rehman@gmail.com>
 *
 *		gcc -O3 -fomit-frame-pointer -fstrict-aliasing -momit-leaf-frame-pointer -fno-tree-pre -falign-loops -funroll-loops queen.c -o queen
 *
 *		real	0m0.445s
 *		user	0m0.279s
 *		sys	0m0.165s
 *
 *		Mon Feb 20 17:44:45 PKT 2012
 *
 */

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

#define X_FROM_I(i) (i / 8)
#define Y_FROM_I(i) (i % 8)
#define I_FROM_XY(x,y) ((y*8)+x)

static unsigned char *cache;

static long long cache_hit;
static long long cache_miss;

// mark horizontal, vertical and both diagonal kill zones for the queen
// (also mark the queen's location)
void mark_killzone(char *board, int index)
{
	int i;
	int x, y;

	x = X_FROM_I(index);
	y = Y_FROM_I(index);

	// '.' means the place is empty
	// 'X' means there's a queen there
	// 'O' means it's in some queen's kill zone
	for(i = 0; i < 64; i++)
		if( X_FROM_I(i) == x && Y_FROM_I(i) == y )
			board[i] = 'X';
		else if( X_FROM_I(i) == x || Y_FROM_I(i) == y || (x-y) == (X_FROM_I(i)-Y_FROM_I(i)) || (x+y) == (X_FROM_I(i)+Y_FROM_I(i)) )
			board[i] = 'O';
}

// returns a unique 32 bit hash for each board configuration
// groups of 4 bits, each group specifying position of the queen
// at that row 0=not present, 1=0'th index, 2=1st index, etc.
uint32_t board_hash(char *board)
{
	int i, j;

	uint32_t hash = 0;

	for( i = 0; i < 8; i++ )
	{
		unsigned char f = 0x0;

		for( j = 0; j < 8; j++ )
		{
			if(board[I_FROM_XY(i,j)] == 'X')
			{
				f = j+1;
				break;
			}
		}
		
		hash <<= 4;
		hash |= (f & 0xF);
	}

/*	for(i = 0; i < 64; i++)
		printf("%c%c", board[i], ((i+1)%8)?' ':'\n');
	printf("hash: %X\n", hash); */

	return hash;
}

int check_cache(char *board)
{
	uint32_t hash = board_hash(board);	// use this as a bit index
	uint32_t cache_byte_offset = hash / 8;
	uint32_t bit_offset = hash % 8;

	unsigned char b = cache[cache_byte_offset];
	if(b & (0x1 << bit_offset)) {
		cache_hit++;
		return 1;
	}
	
	b |= (0x1 << bit_offset);
	cache[cache_byte_offset] = b;

	cache_miss++;
	return 0;
}

void try_inserting_queens(char *board)
{
	if(check_cache(board))
		return;

	int i;
	int q = 0;
	for(i = 0; i < 64; i++)
	{
		char c = board[i];
		switch(c)
		{
			char *board_copy;

			case '.':	// is empty location
				board_copy = malloc(64);
				memcpy(board_copy, board, 64);
				mark_killzone(board_copy, i);
				try_inserting_queens(board_copy);
				free(board_copy);
				break;

			case 'X':	// there's a queen already here
				q++;
				break;

			case 'O':	// some queen's killzone is here
				break;

			default:
				break;
		}
	
		if(q == 8)
		{
			printf("8 queens solution found:\n");
			for(i = 0; i < 64; i++)
				printf("%c%c", board[i], ((i+1)%8)?' ':'\n');
			printf("\n");
			break; // no need to process this further
		}
	}

}

int main()
{
	char board[64];
	memset(board, '.', 64);

	cache_hit = 0;
	cache_miss = 0;

	cache = malloc(536870912);	// 2 ^ 32 bits, for 2^32 possible board configurations (4 bits per row)
	if(cache == NULL)
	{
		perror("unable to allocate memory");
		exit(-1);
	}

	memset(cache, 0x0, 536870912);
	try_inserting_queens(board);

	printf("cache hit: %qu\ncache miss: %qu\n", cache_hit, cache_miss);
	free(cache);

	return 0;
}