8 Queens

This is a discussion on 8 Queens within the C Programming forums, part of the General Programming Boards category; I did the following program. But it is giving 10356 solutions! I need the 92 distinct solutions for n = ...

  1. #1
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278

    8 Queens

    I did the following program. But it is giving 10356 solutions! I need the 92 distinct solutions for n = 8. Where wrong am I?

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int *x, count = 0;
    
    /*Return true if a a queen can be placed in kth row
    and ith column. Otherwise it returns false. x[] is a
    global array whose first (k-1) values have been set.*/
    
    int Place(int k, int i)
    {
            int j;
    	
    	for(j = 0; j < k-1; j++)
    	   if( (x[j] == i) || (abs (x[j] - i) == abs(j - k)) )
    	     return 0;
            return 1;
    }
    
    /*Using backtracking, this function prints all possible placements 
    of n queens on n x n chessboard so that they are non-attacking */
    
    void NQueens(int k, int n)
    {
            int i,loop;
    	
    	for(i = 0; i <= n; i++)
    	{
    	   if( Place(k,i) )
    	   {
    	      x[k] = i;
    		  if(k == n) 
    		  {
    		    for(loop = 0; loop < n; loop++)
    			  printf("%u  ", x[loop] );
    			printf("\n");
    		    count++;
    			return ;
    		  }	       	   	    
    		  else
    		    NQueens(k+1,n);
    	   }
    	}
    }	  
    	  	  	  	    
    
    int main()
    {
            int n;
    	
    	printf("Enter the size of the chessboard : ");
    	scanf("%u",&n);
    	
    	x = (int*)calloc(n,sizeof(int));
    		
    	printf("\nThe solutions to the problem are :- \n\n");
    	NQueens(0,n-1);
    	
    	printf("count : %d",count);
        
    	return 0;
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,821
    Well what's the difference between a solution and a "distinct" solution.

    At the moment, you simply count solutions.
    What you would seem to need is some kind of "have I seen this solution before?" test.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problems with the eight queens problem
    By Wicket in forum C++ Programming
    Replies: 1
    Last Post: 06-12-2008, 10:29 AM
  2. 8 Queens problem
    By Dashing Boy in forum C++ Programming
    Replies: 14
    Last Post: 10-15-2007, 01:12 PM
  3. 8 Queens
    By Brad0407 in forum Contests Board
    Replies: 36
    Last Post: 06-25-2007, 11:37 AM
  4. 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
  5. 8 Queens
    By PutoAmo in forum C Programming
    Replies: 2
    Last Post: 03-24-2003, 04:45 AM

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