U E D R , A S I H C RSS

Eight Queen Problem/kulguy

Š‚Œ 

ฌธ œ— Œ€ํ•œ ฐœžต ธ ดํ•ดงŒ ํ•˜ณ „œ งˆ˜ ทธ •Œณ ฆฌฆ˜„ ™„ „ํžˆ ดํ•ดํ•œ ƒฅ ฌดํ„Œ€ณ  ฝ””ฉ— “ค–ดฐ”‹ค€  •‹ตดณ  ญณ  ™„ „ํžˆ —‰œ„ ธŠต‹ˆ‹ค. ฒฐตญ ฒ˜Œ€„‹ค‹œ ฝ””ฉ ด „ ‹จ„€„ฐจํžˆ €„ํ•˜—ฌ ฒจšฐ ฌธ œ ํ•ดฒฐํ•  ˆ˜ žˆ—ˆŠต‹ˆ‹ค. ฝ””ฉ ด „˜ —ฌŸฌ ํ”„กœทธž˜ฐ ‹จ„Š” ํ•จ€กœ „ˆ›ธ ‹จ„€ •„‹ˆž€ ฒƒ„ ‹ค‹œ ํ•œฒˆ ˆ † Šด ‹ฌ•˜œฉฐ „Šฅ„ œ„ํ•ด ‹œณต ตํ™˜ ฒ•™„ ‚˜„Œ€กœ  šฉํ•ด ณด•˜Š”ฐ ทธ ํšจ˜ ƒ‹ํ•จ„ ฒฝํ—˜ํ•˜˜€Šต‹ˆ‹ค.

  • •Œณ ฆฌฆ˜ด ค‘š”ํ•˜‹ค
  • ””žธ„ ค‘š”ํ•˜‹ค.
  • „Šฅ„ †’ดณ ž ํ•œ‹คฉด šฐ„  ‹œณต ตํ™˜ ฒ•™„ ดšฉํ•˜ž.
    ‹œณต ตํ™˜ ฒ•™ด ญฃ ?
    „Šฅดž€ ฒƒ„ ํฌฒŒ ˆ˜ํ–‰ ‹œ„(ๆ™‚) ˆ˜ํ–‰‹œ ํ•„š”ํ•œ ฉ”ชจฆฌ(็ฉบ)Š” 2€€ ธกฉด—„œ ณธ‹คฉด ฉ”ชจฆฌชฝ˜ „Šฅ„ ํฌƒํ•ด„œ ˆ˜ํ–‰ ‹œ„„ Œ–ด˜ฌฆฌŠ” ฒƒ„ งํ•ฉ‹ˆ‹ค. ฆ‰, ž “ฐ ฒƒ ฐ™€ „‚ฐ ฒฐŠ” งคฒˆ „‚ฐํ•˜€ •Šณ  ฉ”ชจฆฌ— ‹ด•„‘‚˜ ™ธ€—  €žฅํ–ˆ‹ค€ € ธ˜คŠ” ‹ด ˜Š” ฃ .  €ฐ™€ ฒฝšฐ ฌธ œ ํ’€ธฐ œ„ํ•ด ฒดŠคํŒ œ„— ํ€ธ ํ•˜‚˜€ †“ •Œงˆ‹ค ‹คŒ ํ€ด †“ ˆ˜ žˆŠ” "€Šฅํ•œ žฆฌ „‚ฐ"ํ•ด„œ ทธ ‹คŒ ํ€„ ฐฐ˜ํ•˜Š” ฐฉ‹„ ‚ฌšฉํ–ˆŠต‹ˆ‹ค. ด •Œ "€Šฅํ•œ žฆฌ „‚ฐ"ํ•œ ฒฐ ฉ”ชจฆฌ— ‹ด•„‘ณ  „† ดšฉํ•˜˜€ฃ . ฐธณ กœ ด šฉ–ด™€ ฐœ…“ค€ €ฐฝ€‹˜ด งˆ†Œ— ธฐณ ํ•˜‹  ํŒŒดฌ € จ ธฐ‚ฌ—„œ „Šค€ฆฌ ธšฉํ•œ ฒƒ ž…‹ˆ‹ค. ธšฉดž€ ณธž˜ ทธ ‚ดšฉ„  •ํ™•ํžˆ  „‹ฌํ•ด• ํ•˜Š”ฐ -_-;;; งˆ†Œ ธฐ‚ฌ ง ‘ ฐธณ ํ•ดณด‹œธฐ ฐ”ž‹ˆ‹ค :)

  • See Also งˆ†Œ2001…„ 4›” About Python ธฐ‚ฌ - ํŒŒดฌ ตœ ํ™”ก 

†ŒŠค ํŒŒ

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;
}

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;
	}
}

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;
}

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;
}





Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:12
Processing time 0.0142 sec