회 소 법의 N 황후 문제

역 추적 법
많은 질문 이 있 는데, 그것 을 찾 아야 할 때 나 대답 을 요구 할 때, 왕왕 소 급 법 을 사용 해 야 한다.
역 추적 법의 기본 적 인 방법 은 또는 질서 정연 하 게 조직 되 어 불필요 한 검색 을 피 할 수 있 는 궁 거 식 검색 법 이다.이런 방법 은 조합 수가 상당히 큰 문 제 를 푸 는 데 적용 된다.
사상 방법
역 추적 법 은 문제 의 해 공간 트 리 에서 전략 에 따라 뿌리 결점 에서 출발 하여 해 공간 트 리 를 검색 한다.알고리즘 은 공간 트 리 의 임 의 한 점 을 검색 할 때 이 노드 에 문제 의 해 가 포함 되 어 있 는 지 여 부 를 판단 합 니 다.만약 에 포함 되 지 않 는 다 면 이 결점 이 뿌리 인 나무 에 대한 검색 은 조상 에 게 결점 을 주 었 다.그렇지 않 으 면 이 하위 트 리 에 들 어가 깊이 우선 정책 에 따라 계속 검색 합 니 다.
가지치기 함수:
제약 함수 로 확장 노드 에서 제약 에 만족 하지 않 는 하위 트 리 잘라 내기;한계 함수 로 가장 잘 풀 리 지 않 는 자 수 를 잘라 내다.
특징.
역 추적 법 으로 문 제 를 푸 는 현저 한 특징 은 검색 과정 에서 동태 적 으로 문제 가 발생 하 는 해결 공간 이다.언제든지 알고리즘 은 루트 노드 에서 현재 확장 노드 까지 의 경로 만 저장 합 니 다.만약 에 공간 트 리 에서 뿌리 결점 에서 잎 결점 까지 의 가장 긴 경로 의 길이 가 h (n) 이면 역 추적 법 에 필요 한 계산 공간 은 보통 O (h (n) 이다.전체 분해 공간 을 명시 적 으로 저장 하려 면 O (2h (n) 또는 O (h (n)!) 메모리 공간 이 필요 합 니 다.
N 황후 문제
문제 설명
N 황후 문 제 는 하나의 NXN 바둑판 에 N 개의 황 후 를 올 려 모든 황후 가 다른 N - 1 황후 도 공격 하지 못 하고 다른 N - 1 황후 에 게 도 공격 당 하지 않도록 해 야 한다.
문제 분석
체스 의 규칙 에 따 르 면 한 황 후 는 같은 줄 이나 같은 줄 또는 같은 사선 에 있 는 다른 모든 바둑 알 을 공격 할 수 있다.따라서 N 황후 문 제 는 N 황후 중 어느 두 개가 같은 줄 이나 같은 열 또는 같은 사선 에 놓 여 서 는 안 된다 는 것 과 같다.
저희 N 드릴 게 요.×N 바둑판 의 줄 과 열 은 각각 왼쪽 에서 오른쪽으로, 위 에서 아래로 1, 2, 3... N 번 호 를 매 기 는 동시에 N 황후 에 게 도 각각 1, 2, 3... N 번 호 를 매 긴 다.서로 다른 황 후 를 같은 줄 에 두 지 말 라 고 요구 하기 때문에 광범 위 함 을 잃 지 않 고 황후 i 를 제 i 행 에 만 두 도록 설정 할 수 있 습 니 다.이렇게 하면 N 후 문제 의 해 는 N 원조 (x1, x2, x3... xN) 로 표시 할 수 있다.그 중에서 xi 는 황후 i 가 처 한 열 호 를 나타 낸다.
그러면 제약 조건 이나 한계 함 수 는 ① xi ≠ xj (황후 i 와 j 는 같은 열 에 있 지 않다) 이다.② xi - i ≠ xj - j (황후 i 와 j 는 경사 율 이 - l 인 같은 사선 에 있 지 않다).③ xi + i ≠ xj + j (황후 i 와 j 는 경사 율 이 + l 인 같은 사선 에 있 지 않다).④ 그 중에서 i, j = 1, 2,..., k, 그리고 i < > j.
코드 및 상세 설명

/**
 * @ClassName_NQueen
 * @author_Stone6762
 * @CreationTime_2016 11 23    5:15:43
 * @Description_
 */
public class NQueen {

    private int QueenSize;//N       
    private int[] QueenInfo;//     ，          （    i     i ，         ）

    @SuppressWarnings("unused")
    private NQueen() {}

    public NQueen(int size) throws Exception {
        if (size > 0) {
            this.QueenSize = size;
            this.QueenInfo = new int[size + 1];
        } else {
            throw new Exception("       ！");
        }
    }

    /**
     * @Description:  pos         :       ，  ，   
     * @param pos     
     * @return
     */
    private Boolean PlaceSafety(int pos) {
        //        ，                 
        for (int i = 1; i < pos; i++) {
            //            
            if (Math.abs(pos - i) == Math.abs(QueenInfo[i] - QueenInfo[pos])
                    || (QueenInfo[i] == QueenInfo[pos])) {//  ，          
                return false;
            }
        }
        return true;
    }

    /**
     * @Description:         n    
     */
    public void ShowResult() {
        QueenInfo[1] = 0;
        int pos = 1;//           
        while (pos > 0) {//             
            QueenInfo[pos] += 1;
            //   Pos        ：           ，       ，             
            while (QueenInfo[pos] <= QueenSize && (!this.PlaceSafety(pos))) {
                QueenInfo[pos] += 1;
            }
            if (QueenInfo[pos] <= QueenSize) {//              
                if (pos == QueenSize) {//              ，           ，     
                    //      ，   
                    QueenInfo[0]++;
                    this.Print();
                    //          ，               ，     ，      
                    //  ，         ，    ，       
                } else {//            ，         
                    pos++;
                    QueenInfo[pos] = 0;
                }           
            } else {//          ，      
                pos--;
            }
        }
    }

    /**
     * @Description:       
     */
    private void Print() {
        System.out.println("  " + QueenInfo[0]);
        for (int i = 1; i <= QueenSize; i++) {
            for (int j = 1; j <= QueenSize; j++) {
                if (j == QueenInfo[i]) {
                    System.out.print("■");
                } else {
                    System.out.print("□");
                }
            }
            System.out.println();
        }
        System.out.println();
    }
}