8 Queens

This is a discussion on 8 Queens within the C Programming forums, part of the General Programming Boards category; Hello. I have attempted to implement a program that solves the 8 Queens problem. For those of you who have ...

  1. #1
    Registered User PutoAmo's Avatar
    Join Date
    Mar 2002
    Posts
    72

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

  2. #2
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    for more than one solution place first queen in a random square and go from there. There is no randomness in your solution so it will find same one each time.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  3. #3
    Registered User PutoAmo's Avatar
    Join Date
    Mar 2002
    Posts
    72
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 8 Queens, problem with searching 2D array
    By Sentral in forum C++ Programming
    Replies: 35
    Last Post: 03-11-2009, 05:12 PM
  2. Problems with the eight queens problem
    By Wicket in forum C++ Programming
    Replies: 1
    Last Post: 06-12-2008, 10:29 AM
  3. 8 Queens problem
    By Dashing Boy in forum C++ Programming
    Replies: 14
    Last Post: 10-15-2007, 01:12 PM
  4. 8 Queens
    By Brad0407 in forum Contests Board
    Replies: 36
    Last Post: 06-25-2007, 11:37 AM
  5. and this is my solution for the 8 queens puzzle
    By negevy in forum C Programming
    Replies: 1
    Last Post: 09-01-2005, 12:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21