mip05.gms : 최대 퀸즈 체스 문제

설명

이 모델은 체스에서 8명의 여왕을 배열하는 가능한 모든 방법을 찾습니다.
두 명의 여왕이 서로를 확인하지 않는 방식으로 탑승하십시오.
루프 내에서 해결을 사용하면 다음까지 연속 솔루션이 차단됩니다.
모델이 실행 불가능해집니다.  이 시점에서 모든 솔루션은
열거되었습니다.  이 문제는 오랜 역사를 가지고 있습니다. 1850년
C.F.에 의해 조사되었습니다. 가우스, 그러나 그는 그것을 풀지 못했다
완전히. 표준 8x8 체스판에는 92가지 가능한 솔루션이 있습니다.
대체 NxN 체스판을 쉽게 사용할 수 있습니다. 아래 numSols를 참조하세요.

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

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

슬롯 게임 모델 라이브러리, queens.103

기고자: Steve Dirkse, 2012년 1월

소형 모델 유형 :MIP

카테고리 : 슬롯 게임 테스트 라이브러리

메인 파일 : mip05.gms

$title 최대 퀸즈 체스 문제 (MIP05,SEQ=549)
$eolCom !

$onText

   이 모델은 체스에서 8개의 퀸을 배열하는 가능한 모든 방법을 찾습니다.
   두 명의 여왕이 서로를 확인하지 않는 방식으로 탑승하십시오.
   루프 내에서 해결을 사용하면 다음까지 연속 솔루션이 차단됩니다.
   모델이 실행 불가능해집니다.  이 시점에서 모든 솔루션은
   열거되었습니다.  이 문제는 오랜 역사를 가지고 있습니다. 1850년
   C.F.에 의해 조사되었습니다. 가우스, 그러나 그는 그것을 풀지 못했다
   완전히. 표준 8x8 체스판에는 92가지 가능한 솔루션이 있습니다.
   대체 NxN 체스판을 쉽게 사용할 수 있습니다. 아래 numSols를 참조하세요.

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

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

슬롯 게임 모델 라이브러리, queens.103

기고자: Steve Dirkse, 2012년 1월

$offText

* 컷 생성 없이 실행하려면 명령줄에서 --SKIPCUTS=1을 사용하세요.
* 이렇게 하면 문제가 해결되지 않고 기본적으로 해결됩니다.
* 하나의 솔루션만 반환
$설정되지 않은 경우 SKIPCUTS $set SKIPCUTS 0

$ifThen %DEMOSIZE% == 1
  i '체스판 크기' / 1*6 / 설정;
$else
  i '체스판 크기' / 1*8 / 설정;
$endIf
$eval NS 2 * 카드(i) - 3
세트
  s '대각선 오프셋' / 1*%NS% / ! 2i-3 대각선
  nn '최대 솔루션 수' / s1*s1000 /
  n(nn) '해결책을 찾았습니다'
  희미한 '알려진 크기' / d1 * d10 /
  ;
별칭(i,j);

매개변수
  sh(s) '대각선 이동 값'
  rev(i) '역순'
  sols(nn,i,j) '이전에 찾은 컷 생성 솔루션'
  numSols(어두움) /
    d4 2
    d5 10
    d6 4
    d7 40
    d8 92
    d9 352
    d10 724
  /
  ;
스칼라
  nI '체스판의 크기'
  nSols '발견된 솔루션 수'
  ;
sh(s) = ord(s) - 카드(i) + 1 ;
rev(i) = 카드(i) + 1 - 2*ord(i);
sh, rev를 표시합니다.

이진 변수 x(i,j) '사각형은 여왕에 의해 점유됩니다'
       변수 tot '퀸이 차지하는 사각형의 수'

방정식
  a(i) '두 명의 여왕이 같은 순위에 있을 수 없습니다.'
  b(j) '같은 파일에 두 개의 퀸이 있을 수 없습니다'
  c(s) '같은 대각선(앞으로)에 두 개의 퀸이 있을 수 없습니다.'
  d(s) '같은 대각선(뒤쪽)에는 두 개의 퀸이 있을 수 없습니다.'
  obj '객관적 정의'
  cut(nn) '제거할 알려진 솔루션'
  ;

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;

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

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

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

n(nn) = 아니오;     ! 명확한 컷 세트
솔(nn,i,j) = 0;
옵션 optcr=0;
mip를 사용하여 tot를 최대화하는 퀸을 해결합니다.

$if %SKIPCUTS% == 1 $종료

옵션 limrow=0, limcol=0, solprint=off;
옵션solveLink = %solveLink.loadLibrary%;
루프nn$(queens.solvestat=%solveStat.normalCompletion% 및
         queens.modelstat=%modelStat.optimal%),

   n(nn) = 예;   ! 세트에 요소 추가
   sols(nn,i,j) = round(x.l(i,j));
   밉을 사용하여 최대화하는 퀸을 해결하세요.
;
abort$[card(n) eq 카드(nn)] 'nn을 너무 작게 설정';
nI = 카드(i);
nSols = 카드(n);
nI, nSols를 표시합니다.
abort$[nSols <> sumdim$(ord(dim) eq nI), numSols(dim)] '잘못된 nSols', nSols, numSols, nI;
Execute_unload 'queensSolsCuts', n, I, sols;