여덟 여왕 문제
Eight Queens 문제는 오래되고 유명한 문제이자 역추적 알고리즘의 전형적인 예입니다. 이 문제는 1850년 19세기의 유명한 수학자 Gauss에 의해 제기되었습니다. 8X8 격자 체스에 8개의 퀸을 배치하여 서로 공격할 수 없도록 합니다. 즉, 두 명의 퀸이 같은 행, 같은 열 또는 같은 행에 있을 수 없습니다. 같은 경사면에서 온라인으로 몇 가지 방법으로 넣을 수 있는지 물어보세요.
가우스는 76가지 해법이 있다고 믿었습니다. 1854년에 여러 저자가 베를린의 체스 매거진에 40개의 서로 다른 솔루션을 발표했습니다. 나중에 누군가 그래프 이론을 사용하여 92개의 결과를 해결했습니다. 실제로 92개의 솔루션이 있습니다.
여덟 여왕 문제의 구현을 위해 역동적인 그래픽 시연과 결합하면 알고리즘 설명이 더욱 생생하고 생생해 교육 결과가 좋을 수 있습니다. 다음은 저자가 Turbo C를 사용하여 구현한 Eight Queens 문제에 대한 그래픽 프로그램으로, 92개 세트의 솔루션을 모두 시연할 수 있습니다. 여덟 여왕 문제의 동적 그래픽 구현은 주로 다음 두 가지 문제를 해결해야 합니다.
1． 역추적 알고리즘 구현
(1) 이 문제를 해결하기 위해 체스판의 가로좌표를 i로, 세로좌표를 j로 설정합니다. i와 j의 값은 1부터 8까지입니다. 퀸이 (i,j) 위치를 차지하면 이 위치의 수직, 수평, 대각선 방향에는 다른 퀸을 배치할 수 없습니다. using 문을 구현하려면 다음 세 가지 정수 배열(a[8], b[15], c[24])을 정의할 수 있습니다. 그 중:
a[j-1]=1 j 열에 여왕이 없습니다.
a[j-1]=0 j 열에 여왕이 있습니다.
b[i+j-2]=1 (i,j)의 대각선(왼쪽 위에서 오른쪽 아래로)에는 여왕이 없습니다.
b[i+j-2]=0 (i,j) c[i-j+7]=1 (i,j)의 대각선(왼쪽 위에서 오른쪽 아래로)에는 퀸(오른쪽 위에서 왼쪽 아래로)이 있고 퀸은 없습니다.
c[i-j+7]=0 (i,j) 대각선에 여왕이 있습니다(오른쪽 위에서 왼쪽 아래로)
(2) i의 위치를 선택하는 알고리즘 -번째 퀸은 다음과 같습니다:
for(j=1;j<=8;j++) /*i번째 퀸은 j번째 행에 있습니다*/
if ((i,j) position is 비어 있음)) /*즉, 해당 3개 배열의 해당 요소 값은 1*/
{Occupy position (i, j) /*Set 해당 세 배열의 해당 요소 값을 0*/으로 설정합니다.
if<8
i+1 퀸에 대한 적절한 위치를 선택합니다.
else; 해결책 출력
}
2. 그래픽 액세스
Turbo C 언어에서는 다음 표준 함수를 사용하여 그래픽 액세스를 구현할 수 있습니다.
size=imagesize(x1,y1,x2,y2) 저장 영역 번호를 반환합니다. 필요한 바이트 수입니다.
arrow=malloc(size); 지정된 크기의 동적 영역 비트맵을 만들고 포인터 화살표를 설정합니다.
getimage(x1,y1,x2,y2,arrow); 지정된 영역의 비트맵을 버퍼에 저장합니다.
putimage(x,y,arrow,copy)는 비트맵을 화면의 왼쪽 상단 모서리(x, y)에 배치합니다.
3. 프로그램 목록은 다음과 같습니다.
#i nclude
#i nclude
#i nclude
#i include
char n[3]={0,0};/*어떤 솔루션 그룹을 기록하는 데 사용됩니다*/
int a[8],b[15],c[24],i;
int h[8]={127,177,227,277,327,377,427,477};/*각 퀸의 행 좌표*/
int l[8]={252,217,182,147,112,77,42,7};/*각 퀸의 열 좌표*/
void *arrow; try(int i)
{int j;
for (j=1;j<=8;j++)
if (a[j-1 ]+b [i+j-2]+c[i-j+7]==3) /*i번째 열과 j번째 행이 비어 있는 경우*/
{a[ j-1]=0;b [i+j-2]=0;c[i-j+7]=0;/*i열과 j행을 차지합니다*/
putimage(h[ i-1],l[ j-1],arrow,COPY_PUT);/*퀸 그래픽 표시*/
delay(500);/*Delay*/
if( i<8) try( i+1);
else /*해결책 세트 출력*/
{n[1]++;if (n[1]> 9) {n[0] ++;n[1]=0;}
bar(260,300,390,340);/*n번째 솔루션 그룹 표시*/
outtextxy(275,300 ,n);
지연(3000)
}
a[j-1]=1;b[i+j-2]=1 ;c[i-j+7 ]=1;
putimage(h[i-1],l[j-1],arrow,XOR_PUT);/*퀸을 제거하고 계속해서 찾기 다음 솔루션 세트*/
delay(500)
}
}
int main(void)
{int gdrive=DETECT,gmode, errorcode;
부호 없는 정수 크기
initgraph(&gdrive,&gmode,"")
errorcode= graphresult();
if (errorcode!=grOk)
{printf("그래픽 오류\n");exit(1);}
직사각형 (50,5,100,40);
사각형(60,25,90,33)
/*왕관 그리기*/
line(60 ,28,90,28);라인(60, 25,55,15)
라인(55,15,68,25);라인(68,25,68,10); p>
라인(68,10,75,25);라인(75,25,82,10)
라인(82,10,82,25);라인(82,25 ,95,15);
line(95,15,90,25)
size=imagesize(52,7,98,
38); arrow=malloc(size);
getimage(52,7,98,38,arrow);/*크라운을 버퍼에 저장*/
clearviewport() ;
settextstyle(TRIPLEX_FONT, HORIZ_DIR, 4)
setusercharsize(3, 1, 1, 1)
setfillstyle(1,4); /p>
(i=0;i<=7;i++) a[i]=1
(i=0;i<=14;i++) b[i] =1;
(i=0;i<=23;i++) c[i]=1
(i=0;i<=8;i++) line(125,i*35+5,525,i*35+5);/*체스판을 그립니다*/
for (i=0;i<=8;i++) line(125+i* 50 ,5,125+i*50,285);
try(1);/*재귀 함수 호출*/
delay(3000)
closegraph() ;
free(arrow);
}
8개의 여왕 문제에 대한 직렬 알고리즘
1 8개의 여왕 문제
소위 8개의 퀸 문제는 8*8 격자 체스판에 8개의 퀸을 놓는 문제입니다. 각 행과 각 열에는 하나의 퀸이 배치되어야 하며 각 대각선과 각 대각선 반대선에는 하나 이상의 퀸이 배치될 수 없습니다. 동시에 체스판에서 (column1-column2)=(row1-row2) 또는 (column1+row1)=(column2+row2)의 상황은 허용되지 않습니다.
2 여덟 여왕 문제의 직렬 재귀 알고리즘
8 여왕 문제에 대한 가장 간단한 직렬 솔루션은 다음 재귀 알고리즘입니다:
(2.1) 심층 재귀 함수:
go(int step,int 열)
{int i,j,place
row[step]=column;
if (step==8)
outputresult( ); /*재귀를 종료하고 결과를 인쇄합니다*/
else /*재귀를 계속합니다*/
{for(place=1;place<=8;place++)
{for(j=1;j<=step;j++)
if(collision(j ,row [ j],step+1,place))
/*열 충돌, 대각선 또는 역대각선이 있는지 확인*/
goto Skip_this_place; p >go(단계+1,장소);
skip_this_place:;
}
}
}/* go
(2.2) 주요 기능:
void main( )
{int place,j
for(place=1; place <=8;place++)
go(1,place);
}/* main */
8개의 퀸 문제에 대한 병렬 알고리즘
p>이 알고리즘은 해당 체스판에 8개의 퀸의 가능한 모든 자유를 배치하는 것입니다. 메인 프로세스는 초기화된 체스판을 생성하고 체스판을 유휴 하위 프로세스로 보내는 역할을 합니다. 초기화 조건에 대한 모든 솔루션을 만족하는 체스판의 요구 사항입니다.
여기서는 메인 프로세스가 체스판의 처음 두 열만 초기화한다고 가정합니다. 즉, 체스판의 처음 두 열에 퀸 2개를 넣어 8*8=64개의 체스판을 생성할 수 있다고 가정합니다.
1 메인 프로세스 알고리즘
메인 프로세스는 모든 하위 프로세스를 기다립니다. 하위 프로세스가 유휴 상태일 때마다 메인 프로세스에 준비 신호를 보냅니다. 메인 프로세스는 자식 프로세스로부터 Ready 신호를 받은 후 자식 프로세스에 체스판을 보냅니다. 기본 프로세스가 모든 체스판을 생성한 후 모든 하위 프로세스가 작업을 완료할 때까지 기다립니다. 그런 다음 각 하위 프로세스에 완료 신호를 보내고 각 하위 프로세스에서 찾은 솔루션의 합계를 인쇄한 후 종료합니다. 자식 프로세스도 Finished 신호를 받은 후 종료됩니다.
2 하위 프로세스 알고리즘
메인 프로세스에서 보낸 체스판을 받은 후 각 하위 프로세스는 체스판을 확인합니다. 불법이라면 보드를 버리세요. 하위 프로세스는 유휴 상태로 돌아온 다음 새 체스판을 신청하기 위해 준비 신호를 메인 프로세스에 보냅니다. 합법적인 경우 move_to_right(board, rowi, colj)를 호출하여 나머지 6개의 퀸이 있는 모든 위치를 찾습니다. move_to_right(board,rowi,colj)는 colj 열 rowi 행 다음 위치에 퀸을 배치할 수 있는지 확인하는 재귀 프로세스입니다.
1) 먼저 more_queen을 FALSE로 설정합니다.
LEAF, TRUE 및 FLASE를 사용하여 다음 세 가지 상황을 구분합니다.
A) LEAF: 성공적으로 배치되었지만 가장자리에서 colj는 이제 열의 최대값보다 1 더 큽니다. 두 열로 돌아가서 확인할 퀸이 어느 행에 배치될 수 있는지 확인하세요. 그렇다면 more_queen을 TRUE로 설정하세요. p>B)TRUE: 퀸을 성공적으로 배치했습니다. 이 열에 퀸을 배치할 수 있는 다른 방법이 있는지 확인하세요. 그렇다면 more_queen을 TRUE로 설정하세요.
C) FALSE: 배치할 수 없습니다. 돌아가세요. 한 열을 다시 시도하고 more_queen을 배치할 수 있는 경우 TRUE로 설정하고 퀸이 이미 마지막 행에 있는 경우 이전 열을 다시 확인해야 합니다.
2) more_queens=TRUE인 경우 새 체스판을 위한 공간을 할당하려면 move_to_right()를 다시 호출해야 하며, xfer()를 사용하여 기존 체스판을 nextboard에 복사하고 다음 상황을 처리해야 합니다.
TRUE: 퀸의 위치를 확인하고 열 수를 늘린 후 다시 시도하세요.
FALSE: 실패, more_queen이 true인 경우 체스판을 검색하고 마지막으로 호출된 체스판을 저장합니다. 열 수를 줄이고, 퀸을 제거하고, 행 수를 늘린 다음 move_to_right()를 호출합니다.
LEAF: 해를 구하고 해를 1만큼 늘린 다음 해를 log_file에 씁니다. 가장자리에 도달하면 열이 1로 돌아가서 퀸이 배치되었는지 확인합니다. 가능하다면 move_to_right를 호출하고, 그렇지 않은 경우 more_queen을 확인하여 체스판을 저장된 체스판으로 복원합니다. 마지막 호출이 이루어졌을 때 퀸을 확인하도록 변경하고 아래로 이동하려면 move_to_right를 호출하세요.
Eight Queens 문제에 대한 효율적인 솔루션 - 재귀 버전
// Yifi 2003 재미있게 보내세요! : )
//8 Queen 재귀 알고리즘
//체스에 대한 Q가 있는 경우[i]=j;
//안전하지 않은 위치는 k행의 j 위치, j+k-i 위치 및 j-k+입니다. i position
class Queen8{
static final int QueenMax = 8
static int oktimes = 0
static int chess[ ] = new int[ QueenMax];//각 Queen의 배치 위치
public static void main(String args[]){
for (int i=0;i< QueenMax;i++)chess [i]=-1;
placequeen(0)
System.out.println("\n\n\n"+oktimes+" 8개가 있습니다. queens Solution made by yifi 2003");
}
public static void placequeen(int num){ //num은 지금 배치할 행 수입니다
int i=0;
boolean qsave[] = new boolean[QueenMax]
for(;i //이제 안전한 비트 배열을 먼저 완성 i=0;//i는 지금 확인할 배열 값입니다. while (i qsave[chess[i]]=false; int k=num-i; if ( (chess[i]+k >= 0 ) && (체스 [i]+k < QueenMax) ) qsave[chess[i]+k]=false if ( (체스[i]-k >= 0) && (체스[i; ]-k < QueenMax) ) qsave[chess[i]-k]=false; i++; } //안전 비트 반복 아래 for(i=0;i if (qsave[i]==false)continue; chess[num]=i; placequeen(num+1) } else { //번호는 마지막 번호입니다 chess[num]=i; oktimes++ System.out.println("이것은 "+oktimes+ " 다음과 같이 해결하세요: "); System.out.println("Line n: 1 2 3 4 5 6 7 8") for (i=0;i String row="Row "+(i+1)+": " if (chess[i]==0) else for(int j=0;j< 체스[i];j++) row+="--"; row+="++"; int j = 체스[i]; while(j System.out.println(row) } } } //순회가 완료되면 중지