Skip to content

Instantly share code, notes, and snippets.

@AsadR
Created March 10, 2012 20:08
Show Gist options
  • Save AsadR/2012876 to your computer and use it in GitHub Desktop.
Save AsadR/2012876 to your computer and use it in GitHub Desktop.
Dumb Eight Queen Solution in 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment