nqueensboard.java

N-Queen solver written in java with excellent Graphical user interface.

/*
 * NQueensBoard.java
 *
 * Created on January 21, 2008, 12:50 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */
import java.io.*;
import javax.swing.JOptionPane;
/**
 *
 * @author Gopal Lal and Sandeepan Jindal
 */
public class NQueensBoard {
    int[][] board;
    int size;
    int [] index;
    
    /** Creates a new instance of NQueensBoard */
    public NQueensBoard(int n) {
        size = n;
	board = new int[size][size];
        index = new int[size];
	for (int i = 0; i < size; i++)
	{
            for (int j = 0; j < size; j++) 
            {
		board[i][j] = 0;
            }
            index[i] = -1;
	}
    }
	public void addQueenAt(XYLocation l)
	{
		if (!(queenExistsAt(l)))
			board[l.getXCoOrdinate()][l.getYCoOrdinate()] = 1;
                index[l.getXCoOrdinate()] = l.getYCoOrdinate();
	}

        public void addQueenAt(int x, int y)
	{
                XYLocation l = new XYLocation(x, y);
		if (!(queenExistsAt(l)))
			board[l.getXCoOrdinate()][l.getYCoOrdinate()] = 1;
                index[l.getXCoOrdinate()] = l.getYCoOrdinate();
	}
	public void removeQueenFrom(XYLocation l) 
	{
		if (board[l.getXCoOrdinate()][l.getYCoOrdinate()] == 1) 
		{
			board[l.getXCoOrdinate()][l.getYCoOrdinate()] = 0;
		}
	}

	private boolean queenExistsAt(int x, int y) 
	{

		return (board[x][y] == 1);
	}

	public boolean queenExistsAt(XYLocation l) 
	{

		return (queenExistsAt(l.getXCoOrdinate(), l.getYCoOrdinate()));
	}

	public void moveQueen(XYLocation from, XYLocation to) 
	{

		if ((queenExistsAt(from)) && (!(queenExistsAt(to)))) 
		{
			removeQueenFrom(from);
			addQueenAt(to);
		}
	}

	public void clear()
	{

		for (int i = 0; i < size; i++) 
		{
			for (int j = 0; j < size; j++) 
			{
				board[i][j] = 0;
			}
                        index[i] = -1;
		}
	}

	private boolean isSquareHorizontallyAttacked(int x, int y)
	{

		return numberOfHorizontalAttacksOn(x, y) > 0;
	}

	private boolean isSquareVerticallyAttacked(int x, int y) 
	{
		return numberOfVerticalAttacksOn(x, y) > 0;
	}

	private boolean isSquareDiagonallyAttacked(int x, int y)
	{
		return numberOfDiagonalAttacksOn(x, y) > 0;
	}

	public boolean isSquareUnderAttack(int x,int y) 
	{

		return (isSquareHorizontallyAttacked(x, y)
				|| isSquareVerticallyAttacked(x, y) || isSquareDiagonallyAttacked(
				x, y));
	}

	public int getSize() 
	{
	return size;
	}

	public void print() 
	{
	System.out.println(getBoardPic());
	}

	public String getBoardPic()
	{

		StringBuffer buffer = new StringBuffer();
		for (int row = 0; (row < size); row++) 
		{ // row
			for (int col = 0; (col < size); col++) 
			{
			// col
				if (queenExistsAt(col, row)) 
				{
					buffer.append(" Q ");
				} else 
				{
					buffer.append(" - ");
				}
			}
			buffer.append("\n");
		}
		return buffer.toString();
	}

	public int getNumberOfAttacksOn(int x, int y) 
	{

		return numberOfHorizontalAttacksOn(x, y)
				+ numberOfVerticalAttacksOn(x, y)
				+ numberOfDiagonalAttacksOn(x, y);
	}

	public int numberOfHorizontalAttacksOn(int x, int y) 
	{

		int retVal = 0;
		for (int i = 0; i < size; i++) 
		{
			if ((queenExistsAt(i, y))) 
			{
				if (i != x)
					retVal++;
			}
		}
		return retVal;
	}

	public int numberOfVerticalAttacksOn(int x, int y) 
	{
	

		int retVal = 0;
		for (int j = 0; j < size; j++) 
		{
			if ((queenExistsAt(x, j)))
			{
				if (j != y)
					retVal++;
			}
		}
		return retVal;
	}

	public int numberOfDiagonalAttacksOn(int x, int y) 
	{

		int retVal = 0;

		int i;
		int j;
		// forward up diagonal
		for (i = (x + 1), j = (y - 1); (i < size && (j > -1)); i++, j--) 
		{
			if (queenExistsAt(i, j)) 
			{
				retVal++;
			}
		}
		// forward down diagonal
		for (i = (x + 1), j = (y + 1); ((i < size) && (j < size)); i++, j++) 
		{
			if (queenExistsAt(i, j)) 
			{
				retVal++;
			}
		}
		// backward up diagonal
		for (i = (x - 1), j = (y - 1); ((i > -1) && (j > -1)); i--, j--) 
		{
			if (queenExistsAt(i, j)) 
			{
				retVal++;
			}
		}

		// backward down diagonal
		for (i = (x - 1), j = (y + 1); ((i > -1) && (j < size)); i--, j++) 
		{
			if (queenExistsAt(i, j)) 
			{
				retVal++;
			}
		}

		return retVal;
	}


	public String toString() 
	{
		StringBuffer buf = new StringBuffer();
		for (int row = 0; row < size; row++) 
		{ // rows
			for (int col = 0; col < size; col++) 
			{ // columns
				if (queenExistsAt(col, row)) 
				{
					buf.append('Q');
				} else 
				{
					buf.append('-');
				}
			}
			buf.append("\n");
		}
		return buf.toString();
	}

    public int getTotalConflicts()
    {
        int x=0;
        for (int i=0; i<size; i++)
        {
            x = x + getNumberOfAttacksOn(i, index[i]);
        }
        return x;
    }
    public boolean isConflict()
    {
        return getTotalConflicts() > 0;
    }
    
    public int reduceConflict(int flag)
    {
        int count=0, lflag=0;
		int steps=0;
		int last_i=0;
        while (isConflict())
        {
			steps++;
            int mflag =0, min_i= last_i, min_j= index[last_i], min_now = getTotalConflicts();
            for (int i=0; i<size; i++)
            {
                int current_index = index[i];
//                int t2 = getTotalConflicts();
                int dflag =0;
                for (int j=0; j<size; j++)
                {
                    XYLocation from = new XYLocation(i, index[i]);
                    XYLocation to = new XYLocation(i, j);
                    moveQueen(from, to);
                    int t3 = getTotalConflicts();
                    
                    if (t3 < min_now)
                    {
                        mflag =1;
                        lflag =0;
                        count =0;
//                        System.out.println("for x : "+ i +"\ty : "+ j + "\tprevious conf :" + min_now + "\tcurrent conf :" + t3);
                        min_j = j;
                        min_now = t3;
                        min_i = i;
						last_i =i;
                        if (flag ==1)
                        {
                            dflag =1;
                            break;
                        }
                    }
                    if (lflag ==1 && t3 <= min_now && i!=last_i)
                    {
                        count++;
                        min_j = j;
                        min_now = t3;
                        min_i = i;
						last_i =i;
                        if (flag ==1)
                        {
                            dflag =1;
                            break;
                        }
                    }
                }
                XYLocation from = new XYLocation(i, index[i]);
                XYLocation to = new XYLocation(i, current_index);
                moveQueen(from, to);
                if (dflag ==1)
                    break;
//                System.out.print("min conf : " + t2);
            }
            XYLocation from = new XYLocation(min_i, index[min_i]);
            XYLocation to = new XYLocation(min_i, min_j);
            moveQueen(from, to);
            if (mflag ==0)
                lflag =1;
            if (count>=10)
            {
                if (flag <2)
                {
                    System.out.println("There is dead end with min conflict : "+ min_now);
					//JOptionPane.showMessageDialog(null,("This is the dead end.Min no. of conflicts :"+ min_now +", the program will Terminate now"));
					//System.exit(0);
                    break;
                }
                else
                {
                    count =0; lflag=0;
                    randomPlaceQueens();
                }
            }
            System.out.println("loop completed");
        }
		return steps;
    }
    
    public void randomPlaceQueens()
    {
        clear();
        for (int i=0; i< size; i++)
        {
            addQueenAt(i, (int) (8*Math.random()));
        }
    }

}



/*
XYLOCATION CLASS
Contains class XY location for use in array of queens
*/


class XYLocation 
{
	int xCoOrdinate, yCoOrdinate;

	public XYLocation(int i, int j) 
	{
		xCoOrdinate = i;
		yCoOrdinate = j;
	}

	public int getXCoOrdinate()
	{
		return xCoOrdinate;
	}

	public int getYCoOrdinate() 
	{
		return yCoOrdinate;
	}
	public String toString() 
	{
		return " ( " + xCoOrdinate + " , " + yCoOrdinate + " ) ";
	}


    
}