문제 설명: 그림과 같이 8개의 퀸을 체스판 위에 놓습니다. 두 명의 퀸이 서로 공격할 수 없습니다. 즉, 두 명의 퀸이 같은 행, 열 또는 대각선에 있을 수 없습니다.
이 기사에서는 두 문제에 대해 약간 다른 솔루션이 사용되지만 둘 다 1차원 배열을 사용합니다. 6.20에서는 효과적인 레이아웃을 찾는 것이 필요했는데, 8개의 요소로 구성된 1비트 배열을 만들었고, 배열의 값을 무작위로 섞은 다음 그 값을 아래 첨자와 비교하여 마침내 효과적인 레이아웃을 얻었습니다. 6.22, 필수입니다. 모두 찾기 효과적인 레이아웃, 여기서는 8진수를 사용하고, 001234567-076543210의 모든 숫자를 순회하고, 이를 8진수 문자열로 변환하고, 각 비트를 해당 첨자와 비교하고, 조건에 맞는 레이아웃을 출력합니다. 구현원리와 방법은 아래에서 자세히 소개하겠습니다.
1부 유효한 레이아웃인지 판단하는 방법
우리는 체스판을 0~7 범위의 8*8 행렬로 처리합니다. 왼쪽 그림을 관찰하면 레이아웃이 일련의 숫자 쌍(위에서 아래로), 즉 (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[i] = i가 됩니다. 그런 다음 배열을 무작위로 섞은 다음 조건 2가 충족되는지 확인합니다.
다음과 같이 코드 코드를 복사합니다.
// 배열 생성 및 초기화
int [] 목록 = 새로운 int [arrSize];
for(int i = 0; i < arrSize; i++)
목록[i] = i;
// 배열을 무작위로 섞는다
공개 정적 무효 RandomizeArray(int [] 목록){
int arrSize = 목록.길이;
int ranIndex;
for(int i = 0; i < arrSize; i++){
ranIndex = (int)(Math.random() * arrSize);
if(ranIndex != i){
int temp = 목록[i];
목록[i] = 목록[ranIndex];
목록[ranIndex] = 온도;
}
}
}
6.20의 코드 본문은 다음과 같습니다.
다음과 같이 코드 코드를 복사합니다.
// 6.20 게임: 여덟 여왕
공개 무효solveEightQueens(){
int arrSize = 8;
int [] 목록 = 새로운 int [arrSize];
for(int i = 0; i < arrSize; i++)
목록[i] = i;
정수 개수 = 0;
부울 notValid = true;
동안(유효하지 않음){
카운트++;
유효하지 않음 = 거짓;
randomizeArray(목록);
for(int i = 0; i < arrSize; i++){
for(int j = i + 1; j < arrSize; j++){
if(j - i == Math.abs(list[j] - list[i])){ // 조건이 충족되는지 확인
유효하지 않음 = 사실;
부서지다;
}
}
if(notValid) break;
} // 외부 for 루프의 끝
} // 잠시 동안의 끝
// 결과를 인쇄한다
나는 int;
System.out.println("O(∩_∩)오하하~, " + count + "번 시도해서 결국 성공했습니다.");
for(i = 0; i < arrSize - 1; i++){
System.out.print("(" + i + ", " + 목록[i] + "), ");
}
System.out.println("(" + i + ", " + 목록[i] + ")");
}
2부 유효한 레이아웃을 모두 찾기
6.22에서는 유효한 8개 퀸 레이아웃을 모두 찾아야 하므로 배열을 무작위로 섞는 방법은 더 이상 적용할 수 없으므로 가능한 모든 배열을 순회할 수 있는 방법을 찾아야 합니다. 가장 직접적인 방법 중 하나는 8층 for 루프를 사용하는 것이지만, 코드의 양이 너무 많고 헤드가 희미해지기 쉬우므로 이 방법은 사용하지 않습니다.
1부에서 배열의 값을 주의 깊게 관찰하면 모두 0-7 사이에 있음을 알 수 있으므로 8진수 정수를 사용하여 순회하면 모든 순열이 포함된다는 것을 확인할 수 있습니다. 8자리 숫자가 다르기 때문에 가능한 순열은 8! = 40320이고, 8진수의 총 개수는 8^8 = 16777216이므로 가능한 비율은 40320/16777216 = 1/416이 되어 40320이 됩니다. 순열 최종 유효한 레이아웃을 필터링하는 검사도 있습니다. 이 방법은 아직은 조금 비효율적이지만 아직 더 효율적인 방법을 찾지 못했습니다.
다음과 같이 코드 코드를 복사합니다.
// 6.22 게임: 여덟 여왕 문제에 대한 다양한 해결책(int 값을 증가시킨 다음 이를 8진수 문자열로 변환한 후 확인)
공개 정적 무효solvEightQueensMethod(){
int start = 001234567; // 8진수
int end = 076543210; // 8진수
int count = 0; // 유효한 레이아웃 수를 계산합니다.
for(int i = 시작; i < 끝; i++){
부울 isValid = isValid(i);
if(isValid){
if(++개수 % 7 == 0)
System.out.println(Integer.toOctalString(i) + ": " + isValid);
else System.out.print(Integer.toOctalString(i) + ": " + isValid + " ");
}
}
System.out.println("count = " + count); // 유효한 레이아웃 수를 출력합니다.
}
// 숫자가 유효한 레이아웃인지 확인
공개 정적 부울 isValid(int 숫자){
String numOct = Integer.toOctalString(number);
int arrSize = numOct.length();
if(arrSize==7) { // 숫자의 첫 번째 숫자가 0이면 생성된 문자열은 7자만 갖습니다.
numOct = '0' + numOct;
arr크기++;
}
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 //동일한 대각선;
}
}
사실을 반환;
}
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-queen 레이아웃을 모두 찾는 데 사용되는 방법은 int 유형 번호를 증가시킨 다음 하나씩 확인하는 것입니다. 위의 문제도 비슷한 방법으로 해결할 수 있습니다. 하지만 좀 더 효율적인 방법이 있다면 전문가에게 조언을 구하시기 바랍니다.