자바 8 황후 문제 예시 공유 실현

문제 설명:8 개의 황 후 를 바둑판 에 놓 으 면 그 어떠한 두 황후 도 서로 공격 할 수 없다(즉,그 어떠한 두 황후 도 같은 줄,같은 열 또는 같은 대각선 에 있 지 않다).그림 과 같다.

 
본 논문 에서 두 문제 에 대해 약간 다른 해결 방식 을 사 용 했 지만 모두 1 차원 배열 을 사용 했다.6.20 에서 효과 적 인 구 조 를 요구 합 니 다.저 는 8 개의 요소 가 있 는 배열 을 만 들 었 습 니 다.배열 의 값 을 마음대로 흐 트 러 뜨리 고 값 과 아래 표 시 된 비 교 를 통 해 효과 적 인 구 조 를 얻 을 수 있 습 니 다.6.22 에서 모든 효과 적 인 구 조 를 요구 합 니 다.여기 서 저 는 8 진 수 를 사용 하여 옮 겨 다 녔 습 니 다.  001234567-076543210 의 모든 숫자 에서 이 를 8 진 문자열 로 전환 시 켜 각 비트 와 아래 표 시 를 비교 하여 조건 을 만족 시 키 는 구 조 를 출력 합 니 다.실현 원리 와 방식 에 대해 상세히 소개 한다.
파 트 1 효과 적 인 레이아웃 여 부 를 어떻게 판단 합 니까?
우 리 는 바둑판 을 8*8 행렬 로 보고 범 위 는 모두 0-7 이다.왼쪽 그림 을 살 펴 보면 그 구 조 는 한 조 의 수로(위 에서 아래로),즉(0,0),(1,6),(2,3),(3,5),(4,7),(5,1),(6,4),(7,2)를 나 타 낼 수 있다.int[]list={0,6,3,5,7,1,4,2}을 하나의 배열 로 표시 합 니 다.
분명히 이것 은 효과 적 인 구조 이다.다음 에 우 리 는 하나의 문 제 를 고려 해 야 한다.효과 적 인 레이아웃 에서 아래 표 시 는 배열 에 대응 하 는 값,즉 i 와 list[i]와 무슨 관계 가 있 습 니까?
여기   list[i] = k; list[j] = q;   (i>j)두 가지 조건 을 만족 시 킵 니 다.
1、 k != q;
2、 i - j == k - q    혹은  i - j == q -k  （드 림
보증 하기 위해 k!=q.배열 list 를 설명 하고 초기 화 합 니 다.   list[i] = i。 그리고 무 작위 로 배열 을 어 지 럽 히 고 검사 합 니 다.  조건 충족 여부 2

//             
int [] list = new int [arrSize];
for(int i = 0; i < arrSize; i++)
    list[i] = i;
//       
public static void randomizeArray(int [] list){
    int arrSize = list.length;
    int ranIndex;
    for(int i = 0; i < arrSize; i++){
        ranIndex = (int)(Math.random() * arrSize);
        if(ranIndex != i){
            int temp = list[i];
            list[i] = list[ranIndex];
            list[ranIndex] = temp;
        }
    }
}

6.20 의 코드 주 체 는 다음 과 같다.

// 6.20   ：   
    public void solveEightQueens(){
        int arrSize = 8;
        int [] list = new int [arrSize];
        for(int i = 0; i < arrSize; i++)
            list[i] = i;
        int count = 0;
        boolean notValid = true;
        while(notValid){
            count ++;
            notValid = false;
            randomizeArray(list);
            for(int i = 0; i < arrSize; i++){
                for(int j = i + 1; j < arrSize; j++){
                    if(j - i == Math.abs(list[j] - list[i])){  //         
                        notValid = true; 
                        break;
                    }
                }
                if(notValid) break;
            }   // end of outer for loop
        }   // end of while

        // print the result
        int i;
        System.out.println("O(∩_∩)O  ~, I have tried " + count + " times, and eventually succeed.");
        for(i = 0; i < arrSize - 1; i++){
            System.out.print("(" + i + ", " + list[i] + "), ");
        }
        System.out.println("(" + i + ", " + list[i] + ")");
    }

파 트 2 는 모든 효과 적 인 구 조 를 구 했다.6.22 는 모든 효과 적 인 8 황후 구 조 를 구 해 야 하기 때문에 무 작위 로 배열 을 어 지 럽 히 는 방법 은 더 이상 적용 되 지 않 고 모든 가능 한 방법 을 찾 을 수 밖 에 없 었 다.가장 직접적인 방법 은 8 층 for 순환 을 사용 하지만 코드 의 양 이 너무 많 고 머리 가 쉽게 어 지 러 워 서 이 방법 을 사용 하지 않 는 다 는 것 이다.
파 트 1 의 배열 값 을 자세히 살 펴 보면 0-7 사이 에 있 기 때문에 8 진 int 수 를 사용 하여 옮 겨 다 니 면 모든 배열 을 포함 할 수 있 습 니 다.8 자리 숫자 가 각각 다 르 기 때문에 가능 한 배열 은 8!=40320 종,8 진법 은 모두 있다.  8^8=167777216 개,그래서  가능 한 비율  40320/16777216=1/416,얻 은 이 40320 개의 배열 은 검 사 를 해 야 최종 적 으로 효과 적 인 구 조 를 선별 할 수 있다.이 방법 은 효율 이 좀 낮 지만 아직 더 효율 적 인 것 을 생각해 내지 못 했다.

// 6.22   ：            (  int   ，             ，     ）
    public static void solveEightQueensMethod(){
        int start = 001234567;  //    
        int end = 076543210;   //    
        int count = 0;   //         
        for(int i = start; i < end; i++){
            boolean isValid = isValid(i);
            if(isValid){

                if(++count % 7 == 0)
                    System.out.println(Integer.toOctalString(i) + ": " + isValid);
                else System.out.print(Integer.toOctalString(i) + ": " + isValid + "  ");
            }
        }
        System.out.println("count = " + count);  //         
    }
//    number        
    public static boolean isValid(int number){
        String numOct = Integer.toOctalString(number);
        int arrSize = numOct.length();
        if(arrSize==7) { //   number    0，             
            numOct = '0' + numOct;
            arrSize ++;
        }
        for(int i = 1; i < arrSize; i ++){
            for(int j = i - 1; j >= 0; j--){
                if(numOct.charAt(i) == numOct.charAt(j)) return false;   //    
                if(i - j == Math.abs(numOct.charAt(i) - numOct.charAt(j))) return false;  //      
            }
        }
        return true;
    }

Part 3  질문
작년 에 한 필기시험 에서 이런 문제 가 있 었 다.모든 조합 을 출력 할 시퀀스 를 지정 합 니 다.예컨대
"123"의 출력:  1， 2， 3， 12， 13， 21， 23， 31， 32， 123， 132， 213， 231， 312， 321
"abcd"의 출력:a,b,c,d,ab,ac,ad,ba,bc,bd,ca,cb,cd,da,db,dc,abc,acb,abd,adb,acd,adc,...,abcd,...
6.22 에서 모든 8 황후 의 구 조 를 구하 고 사용 하 는 방법 은 int 형 수 를 증가 시 켜 하나씩 검사 하 는 것 이다.위의 문 제 는 유사 한 방법 으로 해결 할 수 있다.그러나 효율 이 좀 낮 아서 더 효율 적 인 방법 이 있다 면 고수 의 조언 을 구 해 야 한다.