Eight Queen Problem/kulguy

느낌점 ¶

문제에 대한 개략적인 이해만 하고서 마치 그 알고리즘을 완전히 이해한 냥 무턱대고 코딩에 들어갔다가 정답이고 뭐고 완전히 엉켜버렸습니다. 결국 처음부터 다시 코딩 이전 단계부터 차근히 준비하여 겨우 문제를 해결할 수 있었습니다. 코딩 이전의 여러 프로그래밍 단계는 함부로 건너뛸 단계가 아니란 것을 다시 한번 뼈 속 깊이 깨달았으며 성능을 위해 시공 교환 법칙을 나름대로 적용해 보았는데 그 효과의 상당함을 경험하였습니다.

알고리즘이 중요하다
디자인도 중요하다.
성능을 높이고자 한다면 우선 시공 교환 법칙을 이용하자.
시공 교환 법칙이 뭐죠?

성능이란 것을 크게 수행 시간(時)과 수행시 필요한 메모리(空)라는 2가지 측면에서 본다면 메모리쪽의 성능을 희생해서 수행 시간을 끌어올리는 것을 말합니다. 즉, 자주 쓰일 것 같은 계산 결과는 매번 계산하지 않고 메모리에 담아두거나 외부에 저장했다가 가져오는 식이 되는 거죠. 저같은 경우 문제를 풀기 위해 체스판 위에 퀸 하나가 놓일 때마다 다음 퀸이 놓일 수 있는 "가능한 자리를 계산"해서 그 다음 퀸을 배치하는 방식을 사용했습니다. 이 때 "가능한 자리를 계산"한 결과를 메모리에 담아두고 계속 이용하였죠. 참고로 이 용어와 개념들은 김창준님이 마소에 기고하신 파이썬 관련 기사에서 비스므리 인용한 것 입니다. 인용이란 본래 그 내용을 정확히 전달해야 하는데 -_-;;; 마소 기사를 직접 참고해보시기 바랍니다

마소2001년 4월 About Python 기사 - 파이썬 최적화론

[edit]

소스 파일 ¶

[edit]

QueensProblem.java ¶

~cpp 
public class QueensProblem
{
	// to run, prompt>java QueensProblem x
	public static void main(String[] args)
	{
		QueensProblem problem = new QueensProblem(Integer.parseInt(args[0]));
		long start = System.currentTimeMillis();
		problem.locate(0);
		System.out.println("소요시간(ms) = " + String.valueOf(System.currentTimeMillis() - start));
		System.out.println("가능한 해답 = " + String.valueOf(problem.getSuccessNum()));
	}

	public QueensProblem(int queensNum)
	{
		this.queensNum = queensNum;
		board = new Chessboard(queensNum);	
	}

	public int getSuccessNum()
	{
		return successNum;
	}
	
	public boolean locate(int index)
	{
		if (index == queensNum)
		{
			++successNum;
		//	System.out.println("성공 " + String.valueOf(++successNum));
		//	System.out.println(board);
			return true;
		}
	
		Chessboard.PointList points = board.getAvailablePoints();
		Point point = null;
		while ((point = points.nextPoint()) != null)
		{
			if(point.getY() == index + 1)
				return false;

			Queen queen = new Queen(point);
			board.locate(queen);
			if (locate(index + 1))
			{
		//		return true;
				board.rollback();
			}
			else
			{
				board.rollback();
			}
		}
		
		return false;
	}	

	private Chessboard board;
	private int queensNum;
	
	private int successNum;
}

[edit]

Chessboard.java ¶

~cpp 
import java.util.*;

public class Chessboard
{
	public Chessboard(int size)
	{
		this.size = size;
		queens = new Stack();
		availablePointsStack = new Stack();
		List availablePoints = new ArrayList();
		for (int y = 0; y < size; ++y)
			for (int x = 0; x < size; ++x)
				availablePoints.add(new Point(x, y));
		availablePointsStack.push(new PointList(availablePoints));
	}

	public void locate(Queen queen)
	{
		List availablePoints = new ArrayList();
		List points = ((PointList)availablePointsStack.peek()).getPoints();
		Iterator pointsIter = points.iterator();
		while (pointsIter.hasNext())
		{
			Point point = (Point)pointsIter.next();
			if (!queen.canAttack(point))
				availablePoints.add(point);
		}
		
		queens.push(queen);
		availablePointsStack.push(new PointList(availablePoints));
	}

	public void rollback()
	{
		queens.pop();
		availablePointsStack.pop();
	}

	public PointList getAvailablePoints()
	{
		return (PointList)availablePointsStack.peek();
	}	

	public String toString()
	{
		StringBuffer buff = new StringBuffer();
		Iterator iter = queens.iterator();
		while (iter.hasNext())
		{
			Queen queen = (Queen)iter.next();
			buff.append(queen.getPoint().toString());
			buff.append("\n");
		}

		return buff.toString();
	}
	
	private int size;
	private Stack queens;
	private Stack availablePointsStack;

	public static class PointList
	{
		public PointList(List points)
		{
			this.points = points;
			index = 0;
		}
		
		public Point nextPoint()
		{
			Point point = null;
			if (index < points.size())
			{
				point = (Point)points.get(index);
				++index;
			}
			return point;
		}

		public List getPoints()
		{
			return points;
		}

		public String toString()
		{
			StringBuffer buff = new StringBuffer();
			Iterator iter = points.iterator();
			while (iter.hasNext())
			{
				Point point = (Point)iter.next();
				buff.append(point);
				buff.append("\n");
			}

			return buff.toString();
		}


		private int index;
		private List points;
	}
}

[edit]

Queen.java ¶

~cpp 
public class Queen
{
	public Queen(Point point)
	{
		this.point = point;
	}

	public boolean canAttack(Point p)
	{
		return point.equalsX(p) || point.equalsY(p) || point.isLocatedCrossly(p);
	}

	public Point getPoint()
	{
		return point;
	}

	private Point point;
}

[edit]

Point.java ¶

~cpp 
public class Point
{
	public Point(int x, int y)
	{
		this.x = x;
		this.y = y;
	}

	public boolean equalsX(Point point)
	{
		return point.x == x;
	}

	public boolean equalsY(Point point)
	{
		return point.y == y;
	}

	public boolean isLocatedCrossly(Point point)
	{
		int diffX = Math.abs(point.x - x);
		int diffY = Math.abs(point.y - y);

		return diffX == diffY;
	}

	public int getX()
	{
		return x;
	}

	public int getY()
	{
		return y;
	}

	public String toString()
	{
		return "(" + String.valueOf(x) + ", " + String.valueOf(y) + ")";
	}

	private int x;
	private int y;
}