Thread: 8 Queens

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;
}

Hmm, I am not sure whether I have understood your answer. My progam is supposed to check square by square the whole board (from 0,0 till 7,7). After a new queen is checked, if the result is that that queen is in conflict with the others, the next square on the board will be checked. So the order is:

0,0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
1,0
1,1
1,2
1,3
...
...
...
7,4
7,5
7,6
7,7


I dont understand why I need randomness when I want to find all solutions to the problem.