Hello.
I have attempted to implement a program that solves the 8 Queens problem. For those of you who have not heard of it before: The program is to find all possible combinations of 8 queens on a chess board without any of them threatening the others.
In my program I use a recursive function that systematically puts a queen on the board at a time and calls a test function that returns 1 if that queen does not interfere with any of the queens already placed on the board or 0 if it does interfere.
I use an array for holding the coordinates of the queens already placed on the board. Variable Q is just a count for the queens already on the board.
Well, and the rest of the program, tho uncommented, shouldn't be hard to understand (for anyone willing to help).
My program does some of the job: It finds 1 of the solutions (I think the first one) but then keeps printing the same solution all time.
Since I do this for fun I would appreciate any hints, rather than the precise solution.
Thanks.
Code:
#include <stdio.h>
int Q;
int Sol[8][2];
void nextQ( void );
int testQ( int, int );
void printSol( void );
int main( void )
{
nextQ( );
return 0;
}
void nextQ( void )
{
int row, col;
for( row = 0; row < 8; row++ )
for( col = 0; col < 8; col++ )
if( testQ( row, col ) )
{
Sol[Q][0] = row;
Sol[Q][1] = col;
Q += 1;
if( Q < 8 )
nextQ( );
else
printSol( );
Q -= 1;
}
return;
}
int testQ( int row, int col )
{
int q, row_abs, col_abs;
for( q = 0; q < Q; q++ )
{
if( Sol[q][0] == row || Sol[q][1] == col )
return 0;
row_abs = Sol[q][0] - row > 0 ? Sol[q][0] - row : row - Sol[q][0];
col_abs = Sol[q][1] - col > 0 ? Sol[q][1] - col : col - Sol[q][1];
if( row_abs == col_abs )
return 0;
}
return 1;
}
void printSol( void )
{
int row, col, i, set = 0, (*walker)[2] = Sol;
static int count = 1;
printf( "Sol #%d\n", count++ );
for( row = 0; row < 8; row++ )
{
for( col = 0; col < 8; col++ )
{
for( i = 0; i < 8; i++ )
if( walker[i][0] == row && walker[i][1] == col )
set = 1;
if( !set ) printf( "O " );
else printf( "X " ), set = 0;
}
printf( "\n" );
}
printf( "\n" );
return;
}