설명

이 모델은 체스에서 8명의 여왕을 배열하는 가능한 모든 방법을 찾습니다.
두 명의 퀸이 다른 퀸을 상대로 체크하지 않는 방식으로 보드에 탑승하세요.
해결은 두 단계로 진행됩니다. 첫 번째 단계에서 우리는
솔루션. 두 번째 단계에서는 컷을 추가하여 모든 솔루션을 찾습니다.
원래 문제 세트로 이동합니다. 마지막으로 보고 단계가 추가됩니다.
찾은 모든 솔루션을 인쇄합니다. 이 문제는 오랜 역사를 가지고 있습니다. 1850년
C.F.에 의해 조사되었습니다. 가우스, 그러나 그는 그것을 풀지 못했다
완전히. 가능한 해결 방법은 92개입니다.

대형 모델 유형 :MIP 게임

카테고리 : 크레이지 슬롯 모델 라이브러리

메인 파일 : queens.gms

$title 최대 퀸즈 체스 문제(QUEENS,SEQ=103)

$onText
이 모델은 체스에서 8개의 퀸을 배열하는 가능한 모든 방법을 찾습니다.
두 명의 퀸이 다른 퀸을 상대로 체크하지 않는 방식으로 보드에 탑승하세요.
해결은 두 단계로 진행됩니다. 첫 번째 단계에서 우리는
솔루션. 두 번째 단계에서는 컷을 추가하여 모든 솔루션을 찾습니다.
원래 문제 세트로 이동합니다. 마지막으로 보고 단계가 추가됩니다.
찾은 모든 솔루션을 인쇄합니다. 이 문제는 오랜 역사를 가지고 있습니다. 1850년
C.F.에 의해 조사되었습니다. 가우스, 그러나 그는 그것을 풀지 못했다
완전히. 가능한 해결 방법은 92개입니다.

Dudeney, HE, 수학의 즐거움. 1970년 뉴욕 도버.

Beauvais, J, OSL로 최대 퀸즈 체스 문제 해결. IBM
킹스턴, EKKNEWS 2 (1991).

키워드: 혼합 정수 선형 계획법, 최대 퀸 체스 문제, n-퀸
          문제, 수학 게임, 조합 최적화, 제약 조건
          만족도 문제
$offText

$eolCom //
$iMax가 설정되지 않은 경우 $set iMax 8
$eval s 2*%iMax%-3

세트
   i '체스판의 크기' / 1*%iMax% /
   s '대각선 오프셋' / 1*%s% /;

별칭(i,j);

매개변수
   sh(s) '대각선 이동 값'
   rev(i) '역순';

sh(들) = ord(들) - 카드(i) + 1;
rev(i) = 카드(i) + 1 - 2*ord(i);
sh, rev 표시;

이진 변수 x(i,j) '퀸이 차지하는 정사각형';

변수 총계는 '여왕이 차지하는 총 제곱'입니다.

방정식
   a(i) '아니요, 여왕은 같은 순위에 있을 수 있습니다.'
   b(j) '아니요, 퀸즈는 같은 파일에 있을 수 있습니다.'
   c(s) '아니요 퀸은 같은 대각선에 있을 수 있습니다(앞으로)'
   d(s) '아니요, 퀸은 같은 대각선(뒤쪽)에 있을 수 있습니다.'
   obj '객관적 정의';

a(i)..sum(j, x(i,j)) =e= 1;

b(j)..sum(i, x(i,j)) =e= 1;

c(s)..sum(i, x(i,i+sh(s))) =l= 1;

d(s).. sum(i, x(i,i+(rev(i)+sh(s)))) =l= 1;

obj..tot =e= sum((i,j), x(i,j));

모델 queen1 '퀸즈를 위한 첫 번째 모델' /모두/;

옵션 optCr = 0;

mip를 사용하여 tot를 최대화하는 queen1을 해결합니다.

$sTitle 나머지 솔루션 모두 찾기
세트
   nn '최대 솔루션 그룹 수' / 1*20 /
   n(nn) '솔루션 그룹에 대한 동적 세트'
   t '회전과 반사를 통한 다중 솔루션'
         / '원래 솔루션'을 찾았습니다.
           rot-90 '원래 솔루션이 90도 회전했습니다'
           rot-180 '180도 회전된 원래 솔루션'
           rot-270 '원래 솔루션이 270도 회전했습니다'
           ref-h '원래 솔루션이 수평으로 반사됨'
           ref-v '수직으로 반사된 원래 솔루션'
           ref-r '원래 솔루션이 대각선으로 반영됨'
           ref-l '원래 솔루션이 대각선 방향으로 반사됨' /;

스칼라 saverow, coloff;

매개변수 cutval '컷 생성을 위한 가능한 모든 솔루션';

방정식 cut(nn,t) '제거할 알려진 솔루션';

cut(n,t).. sum((i,j), cutval(n,t,i,j)*x(i,j)) =l= 카드(i) - 1;

모델퀸즈 '컷이 있는 퀸즈모델' /모두/;

옵션 limRow = 0, limCol = 0, solPrint = off;

n(nn) = 아니오;  // 컷 세트 지우기;

queens.solveStat = %solveStat.normalCompletion%;
queens.modelStat = %modelStat.optimal%;

loop(nn$(queens.solveStat = %solveStat.normalCompletion% 및
         queens.modelStat = %modelStat.optimal%),
   n(nn) = 예;   // 세트에 요소를 추가합니다.
   cutval(nn,'found' ,i,j) = x.l(i ,j );
   cutval(nn,'rot-90' ,i,j) = x.l(j+rev(j),i );
   cutval(nn,'rot-180' ,i,j) = x.l(i+rev(i),j+rev(j));
   cutval(nn,'rot-270' ,i,j) = x.l(j ,i+rev(i));
   cutval(nn,'ref-h' ,i,j) = x.l(i+rev(i),j );
   cutval(nn,'ref-v' ,i,j) = x.l(i ,j+rev(j));
   cutval(nn,'ref-r',i,j) = x.l(j,i);
   cutval(nn,'ref-l' ,i,j) = x.l(j+rev(j),i+rev(i));
   mip를 사용하여 tot를 최대화하는 퀸을 해결합니다.
);

옵션 컷발:0:3:1;
디스플레이 컷발;

$sTitle 솔루션 보고서를 PUT 파일에 쓰기
파일 퀸 '솔루션 그룹에 대한 보고서 파일';
여왕을 넣어;
queen.pc = 3;

스칼라
   saverow '두 번째 보고서 열을 시작할 행 위치'
   coloff '보드 디스플레이의 열 오프셋';

puttl '퀸즈 솔루션 요약' system.date ' ' system.time
루프(n(nn),
   putPage;
   put @12 / / ' 카드(n):<3:0;의 '솔루션 번호 ' ord(nn):3:0 '
   saverow = File.cr;
   콜로프 = 1;
   루프(t,
      if(ord(t) = 5,
         File.cr = 저장 행;
         콜로프 = 31
      );
      put / / @coloff 'Type = ' t.tl / / @(coloff+2);
      loop(j, j.tl을 넣으세요:>2);
      루프(나,
         넣어 / @coloff i.tl:>2;
         루프(j,
            if(cutval(n,t,i,j), put ' x';
            그렇지 않으면 '';);
         );
      );
   );
);