역 추적 법 N 황후 문제 풀이 (자바 실현)

역 추적 법: 탐색 법 이 라 고도 부 르 는데 문제 규모 의 크기 를 고려 하지 않 고 문제 의 가장 뚜렷 한 최소 규모 부터 가능 한 답 을 점차적으로 풀 고 이 를 통 해 문제 의 규 모 를 천천히 확대 하여 최종 문제 의 해결 에 반복 적 으로 접근 하 는 것 이다.이러한 교 체 는 궁 거 와 유사 하고 탐색 적 인 것 이다. 현재 의 가능 한 답안 이 최종 해 를 얻 을 수 없다 는 테스트 를 받 았 을 때 현재 의 이 구 해 과정 을 취소 하고 이전 단계 로 거 슬러 올 라 가 다른 구 해 경 로 를 찾 기 때문이다.
현재 의 구 해 과정 을 취소 하기 위해 서 는 이전 단계 의 구 해 경 로 를 저장 해 야 한 다 는 점 이 중요 하 다.
말 만 하고 재미 가 없 으 니 배 운 알고리즘 문제 로 활용 해 보 자.
N 황후 문제: N * N 의 체스 바둑판 에 N 개의 황 후 를 어떻게 배치 해 야 N 개의 황후 가 서로 위협 하지 않 고 바둑판 에 공동으로 존재 할 수 있 습 니까? 즉, N * N 칸 의 바둑판 에 두 황후 가 같은 줄, 같은 열, 같은 사선 에 있 는 것 이 없습니다.
사고 풀이: 가장 생각 하기 쉬 운 방법 은 1 열의 첫 번 째 줄 부터 질서 있 게 황 후 를 올 리 려 고 시도 한 다음 에 2 열의 몇 번 째 줄 에 황 후 를 올 릴 수 있 는 것 입 니 다. 만약 에 2 열 에 도 성공 하면 3 열 을 계속 놓 습 니 다. 만약 에 이때 두 번 째 줄 이 3 열 에 황 후 를 한 줄 도 놓 을 수 없다 는 것 은 지금까지 의 시도 가 무효 라 는 것 을 의미한다. (즉, 최종 해 제 를 얻 을 수 없다 는 것 이다) 이 럴 때 는 이전 단계 (즉, 두 번 째 단계) 로 거 슬러 올 라 가 이전 단계 (두 번 째 단계) 에 놓 인 황후 의 위 치 를 다시 가 져 가 요구 에 부 합 된 다른 곳 에 두 어야 한다. 이렇게 시도 적 으로 거 슬러 올 라 가면천천히 다가 가서 풀 수 있 을 거 야.
해결 해 야 할 문제: 어떻게 N * N 격자 바둑판 이 더욱 효과 적 이라는 것 을 표시 합 니까?현재 가 고 있 는 탐색 경로 가 요구 에 부합 되 는 지 어떻게 테스트 합 니까?이 두 가지 문 제 는 어떤 데이터 구 조 를 사용 하 는 지 고려 해 야 한다. 적당 한 데이터 구 조 를 사용 하면 프로 그래 밍 문 제 를 해결 하 는 어려움 을 간소화 하 는 데 유리 하 다.
이 를 위해 저 희 는 다음 과 같은 데이터 구 조 를 사용 합 니 다.
int column[col] = row 표시 제 col 열거했어 row 행 에 황후 하나 놓 기
boolean rowExists [i] = true 는 i 행 에 황후 가 있다 는 뜻 이다.
boolean a [i] = true 는 오른쪽 높 고 왼쪽 낮은 i 조 사선 에 황후 가 있다 는 것 을 나타 낸다.  ↓ 순차 1 ~ 2 * N - 1 순차 번호)
boolean b [i] = true 는 왼쪽 높 고 오른쪽 낮은 i 조 사선 에 황후 가 있다 는 것 을 나타 낸다.  ↑ 순서 1 ~ 2 * N - 1 순서 번호)
이 데이터 구조 에 대응 하 는 알고리즘 은 다음 과 같 습 니 다.

  
  
  
  

   
   
   
   
/**  
   
   
   
   
 *       N       
   
   
   
   
 * @author haolloyin  
   
   
   
   
 */ 
   
   
   
   
public class N_Queens {  
   
   
   
   
      
   
   
   
   
    //        
   
   
   
   
    private int queensNum = 4;  
   
   
   
   
 
   
   
   
   
    // column[i] = j     i     j          
   
   
   
   
    private int[] queens = new int[queensNum + 1];  
   
   
   
   
 
   
   
   
   
    // rowExists[i] = true     i       
   
   
   
   
    private boolean[] rowExists = new boolean[queensNum + 1];  
   
   
   
   
 
   
   
   
   
    // a[i] = true          i         
   
   
   
   
    private boolean[] a = new boolean[queensNum * 2];  
   
   
   
   
 
   
   
   
   
    // b[i] = true          i         
   
   
   
   
    private boolean[] b = new boolean[queensNum * 2];  
   
   
   
   
      
   
   
   
   
    //        
   
   
   
   
    private void init() {  
   
   
   
   
        for (int i = 0; i < queensNum + 1; i++) {  
   
   
   
   
            rowExists[i] = false;  
   
   
   
   
        }  
   
   
   
   
          
   
   
   
   
        for(int i = 0; i < queensNum * 2; i++) {  
   
   
   
   
            a[i] = b[i] = false;  
   
   
   
   
        }  
   
   
   
   
    }  
   
   
   
   
 
   
   
   
   
    //                ,      true  
   
   
   
   
    private boolean isExists(int row, int col) {  
   
   
   
   
        return (rowExists[row] || a[row + col - 1] || b[queensNum + col - row]);  
   
   
   
   
    }  
   
   
   
   
 
   
   
   
   
    //    ：        
   
   
   
   
    public void testing(int column) {  
   
   
   
   
 
   
   
   
   
        //        
   
   
   
   
        for (int row = 1; row < queensNum + 1; row++) {  
   
   
   
   
            //     row    column          
   
   
   
   
            if (!isExists(row, column)) {  
   
   
   
   
                //     row    column        
   
   
   
   
                queens[column] = row;  
   
   
   
   
                //      row    column                 
   
   
   
   
                rowExists[row] = a[row + column - 1] = b[queensNum + column - row] = true;  
   
   
   
   
                  
   
   
   
   
                //      ，    
   
   
   
   
                if(column == queensNum) {  
   
   
   
   
                    for(int col = 1; col <= queensNum; col++) {  
   
   
   
   
                        System.out.print("("+col + "," + queens[col] + ")  ");  
   
   
   
   
                    }  
   
   
   
   
                    System.out.println();  
   
   
   
   
                }else {  
   
   
   
   
                    //           
   
   
   
   
                    testing(column + 1);  
   
   
   
   
                }  
   
   
   
   
                //            ，     
   
   
   
   
                rowExists[row] = a[row + column - 1] = b[queensNum + column - row] = false;  
   
   
   
   
            }  
   
   
   
   
        }  
   
   
   
   
    }  
   
   
   
   
      
   
   
   
   
    //     
   
   
   
   
    public static void main(String[] args) {  
   
   
   
   
        N_Queens queen = new N_Queens();  
   
   
   
   
        queen.init();  
   
   
   
   
        //    1        
   
   
   
   
        queen.testing(1);  
   
   
   
   
    }  
   
   
   
   
} 
  
  
  
  

N = 8 시 구 해 결 과 는 다음 과 같 습 니 다 (주: 가로 좌 표 는 열 수 이 고 세로 좌 표 는 줄 수 입 니 다).
 

   
   
   
   

    
    
    
    
(1,1)  (2,5)  (3,8)  (4,6)  (5,3)  (6,7)  (7,2)  (8,4)    
    
    
    
    
(1,1)  (2,6)  (3,8)  (4,3)  (5,7)  (6,4)  (7,2)  (8,5)    
    
    
    
    
(1,1)  (2,7)  (3,4)  (4,6)  (5,8)  (6,2)  (7,5)  (8,3)    
    
    
    
    
... ...  
    
    
    
    
... ...  
    
    
    
    
(1,8)  (2,2)  (3,4)  (4,1)  (5,7)  (6,5)  (7,3)  (8,6)    
    
    
    
    
(1,8)  (2,2)  (3,5)  (4,3)  (5,1)  (6,7)  (7,4)  (8,6)    
    
    
    
    
(1,8)  (2,3)  (3,1)  (4,6)  (5,2)  (6,5)  (7,7)  (8,4)    
    
    
    
    
(1,8)  (2,4)  (3,1)  (4,3)  (5,6)  (6,2)  (7,7)  (8,5)   
   
   
   
   

N = 4 시 구 해 결 과 는 다음 과 같 습 니 다.
 

   
   
   
   

    
    
    
    
(1,2)  (2,4)  (3,1)  (4,3)    
    
    
    
    
(1,3)  (2,1)  (3,4)  (4,2)  
   
   
   
   

시간 이 있 으 면 출력 결 과 를 직관 적 인 기호 형식 이나 인터페이스 형식 으로 인쇄 하 는 것 이 좋 습 니 다.
 
소결:
1. 문제 에 따라 적당 한 데이터 구 조 를 선택 하 는 것 이 매우 중요 하 다. 상기 a, b 표지 배열 처럼 모든 사선 의 번호 순서 와 방향 이 상당히 중요 하 다.책 을 읽 을 때 도 이해 하 는 데 시간 이 좀 걸 렸 어 요. 후... 그리고 queens [col] = row 수 조 는 2 차원 이 아 닌 1 차원 으로 종횡 으로 교차 하 는 격자 바둑판 의 특정 위치 에 황후 가 있 는 지 를 나타 내 는 것 도 경제적 이 고 재 미 있 는 일이 다.
 
2. 정확 한 운용, 조직 이 확정 한 데이터 구 조 는 알고리즘 의 실현 논리 에서 도 중요 하 다. 예 를 들 어 코드 중의 isExists (int row, int col) 방법 내의 (rowExists [row] | a [row + col - 1] | b [queensNum + col - row]) 는 황후 의 위 치 를 놓 으 려 는 x, y 좌표 와 사선 간 의 수치 관 계 를 명확 하 게 이해 한 것 이다.알고리즘 을 정확하게 실행 할 수 있 습 니 다.물론 사선 의 번호, 순서 도 중요 하 다.