8황후 문제(귀속, 거슬러 올라가는 알고리즘)

8황후 문제


문제 소개: 팔황후 문제는 오래되고 유명한 문제로 거슬러 올라가는 알고리즘의 전형적인 사례이다.이 문제는 국제 서양 바둑 기사 맥스 베셀이 1884년에 제기한 것이다. 8*8칸의 국제 장기에 8개의 황후를 놓아서 서로 공격할 수 없게 한다. 즉, 임의의 두 황후가 같은 줄에 있을 수 없거나 같은 직선에 있을 수 없다는 것이다.

생각


1. 첫 번째 황후가 먼저 1열에 놓기 2.두 번째 황후는 두 번째 줄의 첫 번째 열에 놓고 OK 여부를 판단한다. OK가 없으면 계속 두 번째 열, 세 번째 열에 놓고 순서대로 모든 열을 다 놓고 적당한 것을 찾는다.세 번째 황후를 계속해서, 아니면 첫 번째 열, 두 번째 열, 여덟 번째 황후도 충돌하지 않는 위치에 놓을 수 있을 때까지 정확한 해를 찾은 셈이다.정확한 해를 얻었을 때, 창고가 이전 창고로 되돌아갈 때, 거슬러 올라가기 시작하고, 곧 황후가 1열에 놓인 모든 정확한 해를 모두 얻는다.그리고 뒤돌아서서 첫 번째 황후를 2열에 놓고 1, 2, 3, 4단계를 계속 순환합니다.

public class QueueEight {
	
	// queue 
	static int count = 0;
	int queue = 8;
	// array, 
	int []array = new int[queue];
	public static void main(String []args) {
		// 
		QueueEight queueEight = new QueueEight();
		queueEight.check(0);
		System.out.println(" "+count+" ");
		
	}
	// n 
	// :check , check for() , 
	public void check(int n) {
		if(n==queue) {//n==8,8 
			print();
			return ;
			
		}
		// 
		for(int i=0;i

좋은 웹페이지 즐겨찾기