C 언어 로 8 황후 문제 해결 및 해석
8 황후 문 제 는 오래 되 고 유명한 문제 이다.이 문 제 는 19 세기 의 유명한 수학자 고 스 가 1850 년 에 제기 한 것 이다.8*8 체스 판 에 8 개의 황후 가 있 고 각 황후 가 한 칸 을 차지한다.황후 간 에 서로'공격'하 는 현상 이 나타 나 지 않도록 요구한다.즉,두 황후 가 같은 줄,같은 열 또는 같은 대각선 에 있어 서 는 안 된다 는 것 이다.--총 몇 가지 다른 방법 이 있 나.
역 추적 알고리즘 도 탐색 법 이 라 고 하 는데 이것 은 문 제 를 검색 하 는 방법 이다.새삼ǖ막 본 사상 은 모든 해 를 포함 하 는 해 공간 트 리 에서 깊이 우선 전략 에 따라 뿌리 결점 에서 공간 트 리 를 검색 하 는 것 이다.알고리즘 은 공간 트 리 의 임 의 노드 를 검색 할 때 항상 이 노드 가 문제 의 해 를 포함 하지 않 는 지 여 부 를 판단 합 니 다.만약 포함 되 지 않 는 다 면,이 결점 을 뿌리 로 하 는 서브 트 리 에 대한 시스템 검색 을 뛰 어 넘 고,한 층 한 층 조상 결점 으로 거 슬러 올라간다.그렇지 않 으 면 이 하위 트 리 에 들 어가 깊이 우선 정책 에 따라 계속 검색 합 니 다.역 추적 법 은 문제 의 모든 해 를 구 할 때 뿌리 로 거 슬러 올 라 가 야 하 며,뿌리 가 맺 힌 모든 하위 나 무 는 이미 다 검색 되 어서 야 끝났다.
8 황후 문 제 는 많은 중 해법 이 있 는데 그 중에서 역 추적 법 으로 구 해 를 하 는 것 이 그 중의 하나 이다.역 추적 도 가장 직접적인 해법 이 고 이해 하기 쉽다.
8 황후 문제 의 역 추적 법 알고리즘 은 1 차원 배열 로 처리 할 수 있다.배열 의 아래 표 시 는 바둑판 의 i 열 을 나타 내 고 a[i]의 수 치 는 황후 가 i 열 에 놓 인 위 치 를 나타 낸다.예 를 들 어 a[1]=5 는 바둑판 의 다섯 번 째 줄 에 황 후 를 놓 는 것 을 나타 낸다.프로그램 에서 먼저 a[1]=1 을 가정 하면 첫 번 째 황 후 는 바둑판 의 첫 번 째 줄 의 위치 에 놓 인 다음 에 두 번 째 열 에서 황후 가 가능 한 위 치 를 탐색 하고 적당 한 위 치 를 찾 은 후에 후속 적 인 각 열 을 처리 하 는 것 을 나타 낸다.이렇게 각 열의 반복 적 인 탐색 을 통 해 최종 적 으로 황후 의 모든 배치 방법 을 찾 을 수 있다.
8 황후 문 제 는 역 추적 법 으로 해결 할 수 있 고 절 차 는 다음 과 같다.
#include<stdio.h>
#define Queens 8 // ,
int a[Queens+1]; // , 1 1
int main(){
int i, k, flag, not_finish=1, count=0;
// , i-1 , i
i=1;
a[1]=1; //
printf(" :
");
while(not_finish){ //not_finish=l:
while(not_finish && i<=Queens){ // Queens
for(flag=1,k=1; flag && k<i; k++) //
if(a[k]==a[i])
flag=0;
for (k=1; flag&&k<i; k++) //
if( (a[i]==a[k]-(k-i)) || (a[i]==a[k]+(k-i)) )
flag=0;
if(!flag){ // , i
if(a[i]==a[i-1]){ // a[i] a[i-1]
i--; // ,
if(i>1 && a[i]==Queens)
a[i]=1; // a[i] Queens a[i] 1
else
if(i==1 && a[i]==Queens)
not_finish=0; // Queens
else
a[i]++; // a[il
}else if(a[i] == Queens)
a[i]=1;
else
a[i]++; // a[i]
}else if(++i<=Queens)
if(a[i-1] == Queens )
a[i]=1; // Queens a[i]=l
else
a[i] = a[i-1]+1; //
}
if(not_finish){
++count;
printf((count-1)%3 ? "\t[%2d]:" : "
[%2d]:", count);
for(k=1; k<=Queens; k++) //
printf(" %d", a[k]);
if(a[Queens-1]<Queens )
a[Queens-1]++; //
else
a[Queens-1]=1;
i=Queens -1; //
}
}
}
출력 결과:8 황후 의 가능 한 설정 은:
[ 1]: 1 5 8 6 3 7 2 4 [ 2]: 1 6 8 3 7 4 2 5 [ 3]: 1 7 4 6 8 2 5 3
[ 4]: 1 7 5 8 2 4 6 3 [ 5]: 2 4 6 8 3 1 7 5 [ 6]: 2 5 7 1 3 8 6 4
[ 7]: 2 5 7 4 1 8 6 3 [ 8]: 2 6 8 3 1 4 7 5 [ 9]: 2 6 1 7 4 8 3 5
[10]: 2 7 3 6 8 5 1 4 [11]: 2 7 5 8 1 4 6 3 [12]: 2 8 6 1 3 5 7 4
[13]: 3 5 7 1 4 2 8 6 [14]: 3 5 8 4 1 7 2 6 [15]: 3 5 2 8 1 7 4 6
[16]: 3 5 2 8 6 4 7 1 [17]: 3 6 8 1 4 7 5 2 [18]: 3 6 8 1 5 7 2 4
[19]: 3 6 8 2 4 1 7 5 [20]: 3 6 2 5 8 1 7 4 [21]: 3 6 2 7 1 4 8 5
[22]: 3 6 2 7 5 1 8 4 [23]: 3 6 4 1 8 5 7 2 [24]: 3 6 4 2 8 5 7 1
[25]: 3 7 2 8 5 1 4 6 [26]: 3 7 2 8 6 4 1 5 [27]: 3 8 4 7 1 6 2 5
[28]: 3 1 7 5 8 2 4 6 [29]: 4 6 8 2 7 1 3 5 [30]: 4 6 8 3 1 7 5 2
[31]: 4 6 1 5 2 8 3 7 [32]: 4 7 1 8 5 2 6 3 [33]: 4 7 3 8 2 5 1 6
[34]: 4 7 5 2 6 1 3 8 [35]: 4 7 5 3 1 6 8 2 [36]: 4 8 1 3 6 2 7 5
[37]: 4 8 1 5 7 2 6 3 [38]: 4 8 5 3 1 7 2 6 [39]: 4 1 5 8 2 7 3 6
[40]: 4 1 5 8 6 3 7 2 [41]: 4 2 5 8 6 1 3 7 [42]: 4 2 7 3 6 8 1 5
[43]: 4 2 7 3 6 8 5 1 [44]: 4 2 7 5 1 8 6 3 [45]: 4 2 8 5 7 1 3 6
[46]: 4 2 8 6 1 3 5 7 [47]: 5 7 1 3 8 6 4 2 [48]: 5 7 1 4 2 8 6 3
[49]: 5 7 2 4 8 1 3 6 [50]: 5 7 2 6 3 1 4 8 [51]: 5 7 2 6 3 1 8 4
[52]: 5 7 4 1 3 8 6 2 [53]: 5 8 4 1 3 6 2 7 [54]: 5 8 4 1 7 2 6 3
[55]: 5 1 4 6 8 2 7 3 [56]: 5 1 8 4 2 7 3 6 [57]: 5 1 8 6 3 7 2 4
[58]: 5 2 4 6 8 3 1 7 [59]: 5 2 4 7 3 8 6 1 [60]: 5 2 6 1 7 4 8 3
[61]: 5 2 8 1 4 7 3 6 [62]: 5 3 8 4 7 1 6 2 [63]: 5 3 1 6 8 2 4 7
[64]: 5 3 1 7 2 8 6 4 [65]: 6 8 2 4 1 7 5 3 [66]: 6 1 5 2 8 3 7 4
[67]: 6 2 7 1 3 5 8 4 [68]: 6 2 7 1 4 8 5 3 [69]: 6 3 5 7 1 4 2 8
[70]: 6 3 5 8 1 4 2 7 [71]: 6 3 7 2 4 8 1 5 [72]: 6 3 7 2 8 5 1 4
[73]: 6 3 7 4 1 8 2 5 [74]: 6 3 1 7 5 8 2 4 [75]: 6 3 1 8 4 2 7 5
[76]: 6 3 1 8 5 2 4 7 [77]: 6 4 7 1 3 5 2 8 [78]: 6 4 7 1 8 2 5 3
[79]: 6 4 1 5 8 2 7 3 [80]: 6 4 2 8 5 7 1 3 [81]: 7 1 3 8 6 4 2 5
[82]: 7 2 4 1 8 5 3 6 [83]: 7 2 6 3 1 4 8 5 [84]: 7 3 8 2 5 1 6 4
[85]: 7 3 1 6 8 5 2 4 [86]: 7 4 2 5 8 1 3 6 [87]: 7 4 2 8 6 1 3 5
[88]: 7 5 3 1 6 8 2 4 [89]: 8 2 4 1 7 5 3 6 [90]: 8 2 5 3 1 7 4 6
총결산
이상 은 이 글 의 전체 내용 입 니 다.본 논문 의 내용 이 여러분 의 학습 이나 업무 에 어느 정도 참고 학습 가치 가 있 기 를 바 랍 니 다.궁금 한 점 이 있 으 시 면 댓 글 을 남 겨 주 셔 서 저희 에 대한 지지 에 감 사 드 립 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Java 프로그램과 C 언어의 차이에 대한 간단한 분석C 언어를 배운 우리에게 자바는 비교적 간단한 프로그래밍 언어라고 할 수 있다. Java 언어에서는 모든 변수를 먼저 선언해야 사용할 수 있습니다. 그렇지 않으면 프로그램이 실행될 수 없습니다.하나의 C 언어는 몇 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.