ISourceCode

Make the frequent cases fast and the rare case correct

N-Queens Problem

Problem statement : Need to place n queens on a nxn chessboard in such a way that no queen is attacked by another.

Good example of recursion and backtracking

Algorithm:

InsertQueen(row)
    for every position col on the same row
       if position col is available
       place the next queen in position col;
       if (row < n)
          InsertQueen (row+1);
       else success;
       remove the queen from position col;

Implementation : C for 4×4 replace dimension with any number.

#include "stdio.h"

#define available 1
#define dimension 4 // 4-queen problem
#define norm dimension-1

int Column[dimension], PositionInRow[dimension], count = 0;
int LeftDiagonal[dimension*2 - 1]; //contains 6 elements for 4x4 board below the diagonal
int RightDiagonal[dimension*2 - 1];//contains 6 elements for 4x4 board above the diagonal

void PrintBoard()
{   int col, row;

    for (row = 0; row < dimension; row++) {
	for (col = 0; col < PositionInRow[row]; col++)
	    putchar('.');
	putchar('$');
	for (col = PositionInRow[row] + 1; col < dimension; col++)
	    putchar('.');
	putchar('\n');
    }
    putchar('\n');
    count++;
}

void InsertQueen(int row)
{   int col;

    for (col = 0; col < dimension; col++)
	if (Column[col] == available && LeftDiagonal[row+col] == available && RightDiagonal[row-col+norm] == available)
	{
	    PositionInRow[row] = col;
	    Column[col] = !available;
	    LeftDiagonal[row+col] = !available;
	    RightDiagonal[row-col+norm] = !available;
	    if (row < dimension-1)
		 InsertQueen(row+1);
	    else PrintBoard();
	    Column[col] = available;
	    LeftDiagonal[row+col] = available;
	    RightDiagonal[row-col+norm] = available;
	}
}

int main()
{
    int i;

    for (i = 0; i < dimension; i++)
	PositionInRow[i] = -1;
    for (i = 0; i < dimension; i++)
	Column[i] = available;
    for (i = 0; i < dimension*2 - 1; i++)
	LeftDiagonal[i] = RightDiagonal[i] = available;
    InsertQueen(0);
    printf("%d solutions found\n",count);
    return 0;
}

OUTPUT:

laptop:~$ ./a.out
.$..
…$
$…
..$.

..$.
$…
…$
.$..

2 solutions found

The board is considered in this manner:
4×4 board

(0,0)| (0,1) | (0,2) | (0,3)
———————————-
(1,0)| (1,1) | (1,2) | (1,3)
———————————
(2,0)| (2,1) | (2,2) | (2,3)
———————————
(3,0)| (3,1) | (3,2) | (3,3)

First successful Board

(Moveno) | Queen | row | col
————————————–
(1) 0 0 0
(2) 2 1 2 — fail
(3) 2 1 3
(4) 3 2 1 — fail
(5) 1 0 1
(6) 2 1 3
(7) 3 2 0
(8) 4 3 2

Below is a Image of 8- queen problem – courtesy wikipedia
Click on image to see a simulation.

classic computer science problem with complete description available on Wikipedia . Also there are numerous articles and implementations on the Internet.

The no of solutions for a 8×8 board is 92.

This one had to be in a algorithms blog.

Thanks for Reading !

3 responses to “N-Queens Problem

  1. Kishore Ravindran February 7, 2011 at 6:21 am

    Is it possible to implement HashMap logic in C?? That is it should take key value pair of any combination of int,float,String

  2. Kishore Ravindran February 7, 2011 at 9:59 am

    Hi, Here’s a java program to find all the Consecutive sum of a number
    eg :
    9: Can be represented as consecutive sum of
    9=4+5
    9=2+3+4

    99: Can be represented as consecutive sum of
    99=49+50+
    99=14+15+16+17+18+19+
    99=4+5+6+7+8+9+10+11+12+13+14+
    99=7+8+9+10+11+12+13+14+15+
    99=32+33+34+

    Here’s is the Java program

    import java.util.ArrayList;
    import java.util.Iterator;
    import java.util.Scanner;

    public class ConsecutiveSumFinder {

    public static void main(String[] args)
    {
    // TODO code application logic here
    Scanner myscan = new Scanner(System.in);
    System.out.print(“Please enter a number: “);
    int number = myscan.nextInt();

    ConsecutiveSumFinder csf = new ConsecutiveSumFinder();
    // returns all the odd factors of the input number
    ArrayList factors = csf.findFactor(number);

    // if the input doesnt have odd factors then the input
    //cannot be decomposed to sum of consecutive numbers
    if(factors.size()>0)
    {
    System.out.println(number+”: Can be represented as consecutive sum of”);
    Iterator factorsIterate = factors.iterator();
    while(factorsIterate.hasNext())
    {
    int factor = Integer.parseInt(factorsIterate.next().toString());
    int noOfno = (2*number)/factor;
    int temp = noOfno;
    temp = Math.abs(temp – factor);
    temp = temp+1;
    temp = temp/2;
    System.out.print(number+”=”);
    if(noOfno > factor)
    {
    noOfno = factor;
    }
    for(int j=0;j<noOfno;j++)
    {
    System.out.print(temp+"+");
    temp++;
    }
    System.out.println("");
    }
    }
    else
    {
    System.out.println(number+": Cannot be represented as sum of consecutive numbers");
    }
    }

    private ArrayList findFactor(int number)
    {
    int factor = 0;
    ArrayList factors = new ArrayList();
    for (int i = 1; i <= number; i++)
    {
    if(number % i == 0)
    {
    factor = number / i;
    if(factor % 2 != 0)
    {
    if(factor != 1)
    {
    factors.add(factor);
    }
    }
    }
    }
    return factors;
    }
    }

    Full credit goes to Doctor Rick, The Math Forum
    http://mathforum.org/library/drmath/view/57166.html

  3. kapil bhosale (M.Tech) September 21, 2012 at 6:06 am

    java code for 4 queen:

    public class FourQueen 
    {
    	int[][] board = new int[8][8];
    	
    	public static void main(String [] arg)
    	{
    		System.out.println("Four queen problem solution");
    		FourQueen fourQueen = new FourQueen();
    		fourQueen.placeQueen(0);
    	}
    	
    	
    	
    	public boolean placeQueen( int currentQueenNumber)
    	{
    		
    		if( currentQueenNumber == 8 ) 
    			{
    				System.out.println("Solution is : ");
    				printBoard();
    				return true;
    			}
    		
    		
    		for( int j=0; j&lt;8; j++)
    		{
    			if ( isQueenValid(currentQueenNumber, j) )
    			{	
    				board[currentQueenNumber][j] = 1;
    				//printBoard();				
    				placeQueen( currentQueenNumber + 1 );				
    				board[currentQueenNumber][j] = 0;
    			}
    		}
    				
    		return false;
    	}
    	
    	public boolean isQueenValid(int xPosition, int yPosition)
    	{
    		for(int i=0; i&lt;8; i++)
    			for(int j=0; j&lt;8; j++)
    			 	if(board[i][j] == 1 &amp;&amp; (xPosition == i || yPosition == j || (Math.abs(xPosition - i) == Math.abs(yPosition - j))))
    					return false;
    		
    		return true;
    	}
    	
    	public void printBoard()
    	{
    		for(int i=0; i&lt;8; i++)
    			{
    				for(int j=0; j&lt;8; j++)
    				{
    					if( board[i][j] == 0 )				
    						System.out.print(&quot;  | &quot;);
    					else 
    						System.out.print(&quot;X | &quot;);
    				}
    				System.out.println(&quot;\n----------------------------------&quot;);
    			}
    			System.out.println(&quot;--------------------------------------------------&quot;);
    					
    	}
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: