Monday, December 01, 2008

Fallable brute force '8 Queens' puzzle in C

Yay, so got this to work today. Used bash to make it loop and show how fast it could find solutions. Once it took just under 1.5s. It usually takes longer :) For archival purposes and sharing, this is what I did.
queens.c (gcc queens.c -o queens)
#include <stdio.h>
#include <stdlib.h>
#define SIZE 8

void clear_board( void );
void print_board( void );
int mark_square( int x, int y );

int board[SIZE][SIZE];

int main( void )
{
srand( time( NULL ) );
int i;
clear_board();

for(i=0; i <= SIZE; i++)
{
if ( mark_square(rand() % SIZE, rand() % SIZE) == 1 )
{
clear_board();
i=0;
}
}
print_board();
return 0;
}

void clear_board( void )
{
int row;
int col;

for ( row = 0; row <= SIZE; row++ )
for ( col = 0; col <= SIZE; col++ )
board[row][col] = 0;
}

int mark_square( int x, int y )
{
int i;

if ( board[x][y] == 0 )
{
for ( i = 0; i < SIZE; i++)
board[x][i] = 1;
for ( i = 0; i < SIZE; i++)
board[i][y] = 1;
for ( i = 0; i < SIZE; i++)
{
if (x-i >= 0)
{
if (y+i < SIZE)
board[x-i][y+i] = 1;
if (y-i >= 0)
board[x-i][y-i] = 1;
}
if (x+i < SIZE)
{
if (y+i < SIZE)
board[x+i][y+i] = 1;
if (y-i >= 0)
board[x+i][y-i] = 1;
}
}
board[x][y] = 2;
return 0;
}
else
return 1;
}

void print_board( void )
{
int row;
int col;

for ( row = 0; row < SIZE; row++ )
{
for ( col = 0; col < SIZE; col++ )
{
if ( board[row][col] == 0 ) printf( "." );
if ( board[row][col] == 1 ) printf( "x" );
if ( board[row][col] == 2 ) printf( "Q" );
}
printf( "\n" );
}
printf( "\n" );
}


Note:
Some context, this is my solution to problem 6.27(a) Eight Queens: Brute-Force Approaches, p. 264 of C How to Program, 5th edition, by: Deitel and Deitel. Figure if by chance someone is looking up this problem they would be more likely to stumble over this post :)

No comments: