U E D R , A S I H C RSS

Eight Queen Problem/이선우

NQueen.java


~cpp 
public class NQueen
{
	public static final char BLANK_BOARD = '.';
	public static final char QUEEN_MARK = 'Q';
	
	
	private int numberOfBoard;
	private int sizeOfBoard;
	private int [] board;
	
	
	private NQueen() {}
	public NQueen( int sizeOfBoard )
	{
		this.sizeOfBoard = sizeOfBoard;
		board = new int[sizeOfBoard];
		numberOfBoard = 0;
	}
	
	
	protected void initBoard()
	{
		initBoard( 0 );
	}
	protected void initBoard( int from )
	{
		for(int i=from; i<sizeOfBoard; i++ ) board[i] = -1;
	}
	
	
	public void findPosition()
	{
		initBoard();
		setLinePosition( 0 );
	}
	
	
	private void setLinePosition( int line )
	{
		if( line == sizeOfBoard ) {
			if( checkRuleSet() ) {
				numberOfBoard ++;
				//printBoard();
				//System.exit( 0 );
			}
			
			initBoard( line-1 );
			return;
		}
		
		for( int i=0; i<sizeOfBoard; i++ ) {
			board[line] = i;
			setLinePosition( line + 1 );
		}
	}
	
	
	private boolean checkRuleSet()
	{
		for( int i=0; i<sizeOfBoard; i++ ) {
			if( ! checkRule( board[i], i )) return false;
		}
	
		return true;
	}
	

	
	private boolean checkRule( int x, int y )
	{
		int rightDownWay = x - y;
		int leftDownWay = x + y;
		for( int i=0; i<sizeOfBoard; i++ ) {
			if( y != i ) {
				if( board[i] == x || board[i] == rightDownWay || board[i] == leftDownWay ) return false;
			}
			rightDownWay ++;
			leftDownWay --;
		}
		return true;
	}
	
	
	
	private void printBoard()
	{
		for( int i=0; i<sizeOfBoard; i++ ) {
			for( int j=0; j<sizeOfBoard; j++ ) {
				if( board[i] == j ) System.out.print( QUEEN_MARK );
				else System.out.print( BLANK_BOARD );
			}
			System.out.println();
		}
	}
	
	
	public void printNumberOfBoard()
	{
		System.out.println( "Number of different board: " + numberOfBoard );
	}
	
	
	public static void main( String [] args )
	{
		try {
			if( args.length != 1 ) throw new Exception();
			
			NQueen nq = new NQueen( Integer.parseInt( args[0] ));
			nq.findPosition();
			nq.printNumberOfBoard();
		}
		catch( Exception e ) {
			System.out.println( "Usage: java NQueen size_of_queen" );
		}
	}
}
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.1019 sec