U E D R , A S I H C RSS

Eight Queen Problem/이선우3



1. Point.java

2차원 평면에서 좌표계를 나타낸다.

~cpp 
package suwlee.game.nqueen;



public class Point 
{
	private int x;
	private int y;
	
	
	public Point() {}
	public Point( int x, int y )
	{
		setX( x );
		setY( y );
	}
	
	
	public int getX()
	{
		return x;
	}
	
	
	public int getY()
	{
		return y;
	}
	
	
	public void setX( int x )
	{
		this.x = x;
	}
	
	
	public void setY( int y )
	{
		this.y = y;
	}
	
	
	public void setPoint( int x, int y )
	{
		setX( x );
		setY( y );
	}
	
	
	public boolean isSamePoint( Point another )
	{
		if( x == another.x && y == another.y ) return true;
		return false;
	}
}

2. Chessman.java

일반적인 체스 말이 지녀야할 속성을 나타낸다. 여기서 doIHurtYou()는 자신이 다른 체스 말에게 영향을 주는지를 알아본다.

~cpp 
package suwlee.game.nqueen;


public abstract class Chessman extends Point 
{
	public Chessman() 
	{
		super();
	}
	
	
	public Chessman( int x, int y )
	{
		super( x, y );
	}


	public abstract boolean doIHurtYou( Chessman another );
}

3. Queen.java

체스 말 중에서 퀸에 해당한다. 가로,세로,오른쪽/왼쪽 대각선 방향을 체크한다.

~cpp 
package suwlee.game.nqueen;


import suwlee.game.nqueen.Point;


public class Queen extends Chessman 
{
	public Queen() 
	{
		super();
	}


	public Queen( int x, int y )
	{
		super( x, y );
	}


	public boolean doIHurtYou( Chessman another )
	{
		if( getX() == another.getX() ) return true;
		if( getY() == another.getY() ) return true;
		
		double angle = ((double)another.getY() - (double)getY()) / ((double)another.getX() - (double)getX());
		if( angle == 1.0 || angle == -1.0 ) return true;
		
		return false;
	}
}

4. Board.java

일반적인 2차원 형태의 보드를 나타낸다. 실제로 구현하는 보드는 이를 상속받아 draw() 메소드를 구현하게 함으로써 다양한 형태의 보드를 구현하는게 가능하다.

~cpp 
package suwlee.game.nqueen;


import java.util.Enumeration;
import java.util.Vector;


public abstract class Board 
{
	private Vector board;
	private int sizeOfBoard;
	
	
	private Board() {}
	public Board( int sizeOfBoard ) throws Exception
	{
		if( sizeOfBoard < 1 ) throw new Exception( Board.class.getName() + "- size_of_board must be greater than 0." );
		this.sizeOfBoard = sizeOfBoard;
		board = new Vector();
	}
	
	
	public int getSizeOfBoard()
	{
		return sizeOfBoard;
	}
	
	
	public int countChessman()
	{
		return board.size();
	}
	
	
	public boolean setChessman( Chessman chessman )
	{
		if( countChessman() == (sizeOfBoard^2) ) return false;
		
		Chessman prevOne;
		for( Enumeration e=board.elements(); e.hasMoreElements(); ) {
			prevOne = (Chessman)e.nextElement();
			if( chessman.doIHurtYou( prevOne ) || prevOne.doIHurtYou( chessman )) return false;
		}
		
		board.addElement( chessman );
		return true;
	}
	
	
	public Chessman getChessman( int x, int y )
	{
		return getChessman( new Point( x, y ));
	}
	
	
	public Chessman getChessman( Point point )
	{
		Chessman prevOne;
		for( Enumeration e=board.elements(); e.hasMoreElements(); ) {
			prevOne = (Chessman)e.nextElement();
			if( prevOne.isSamePoint( point )) return prevOne;
		}
		
		return null;
	}


	public boolean removeChessman( int x, int y )
	{
		return removeChessman( new Point( x, y ));
	}
	
	
	public boolean removeChessman( Point point )
	{
		Chessman prevOne;
		for( Enumeration e=board.elements(); e.hasMoreElements(); ) {
			prevOne = (Chessman)e.nextElement();
			if( prevOne.isSamePoint( point )) return removeChessman( prevOne );
		}
		
		return false;
	}

	
	public boolean removeChessman( Chessman chessman )
	{
		return board.removeElement( chessman );
	}


	public void clearBoardBelowYPosition( int y )
	{
		Chessman prevOne;
		for( Enumeration e=board.elements(); e.hasMoreElements(); ) {
			prevOne = (Chessman)e.nextElement();
			if( y <= prevOne.getY() ) removeChessman( prevOne );
		}
	}
	
	
	public abstract void draw();
}

5. ConsolBoard.java

콘솔로 출력을 나타내는 보드

~cpp 
package suwlee.game.nqueen;


import suwlee.game.nqueen.Board;


public class ConsolBoard extends Board 
{
	public ConsolBoard( int sizeOfBoard ) throws Exception
	{
		super( sizeOfBoard );
	}


	/**
	 * @see Board#draw()
	 */
	public void draw() 
	{
		Chessman chessman;
		for( int i=0; i<getSizeOfBoard(); i++ ) {
			for( int j=0; j<getSizeOfBoard(); j++ ) {
				chessman = getChessman( j, i );
				if( chessman instanceof Queen ) System.out.print( "Q" );
				else System.out.print( "." );
			}
			System.out.println();
		}
	}
}

6. NQueenPlayer.java

n-Queens Problem을 해결하는 플레이어. 자신이 생각하는 알고리즘(여기서는 play 메소드)에 따라 보드에 체스 말 중, 퀸을 배열하고 올바른지 확인한다.

~cpp 
package suwlee.game.nqueen;


public class NQueensPlayer 
{
	private Board board;
	private int numberOfSolutions;
	
	
	public NQueensPlayer() {}
	
	
	public void prepareBoard( int sizeOfBoard ) throws Exception
	{
		board = new ConsolBoard( sizeOfBoard );
	}
	
	
	public void play()
	{
		numberOfSolutions = 0;
		setQueen( 0 );
	}
	
	
	public int getNumberOfSolutions()
	{
		return numberOfSolutions;
	}
	
	
	private void setQueen( int y )
	{
		if( y == board.getSizeOfBoard() ) {
			if( board.countChessman() == board.getSizeOfBoard() ) {
				numberOfSolutions ++;
				board.draw();
			}
			return;
		}
		
		Chessman chessman = new Queen();
		for( int x=0; x<board.getSizeOfBoard(); x++ ) {
			chessman.setPoint( x, y );
			if( board.setChessman( chessman )) {
				setQueen( y + 1 );
				board.clearBoardBelowYPosition( y );
			}
		}
	}
	
	
	public static void main( String [] args )
	{
		NQueensPlayer player = new NQueensPlayer();
		try {
			if( args.length != 1 ) throw new Exception();
			player.prepareBoard( Integer.parseInt( args[0] ));
			player.play();
			System.out.println( "I found " + player.getNumberOfSolutions() + " solutions." );
		}
		catch( Exception e ) {
			System.out.println( "Usage: java NQueensPlayer size_of_board" );
		}
	}
}
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0122 sec