다음은 NP-hard 문제입니까?

국제 초안에 대한 보드 구성이 주어지면 단일 법적 조치를 찾으십시오.n × n

$n\times n$

$n\times n$

미국 체커 (일명 영어 draughts)에 해당하는 문제 는 다항식 시간으로 사소하게 해결 될 수 있습니다. 이 두 게임 사이에는 세 가지 주요 차이점이 있습니다.n × n

$n\times n$

첫 번째이자 가장 중요한 차이점은“비행 왕”규칙입니다. 체커에서, 왕은 인접한 상대방의 조각을 대각선 방향으로 2 단계 떨어진 빈 사각형으로 뛰어 넘을 수 있습니다 . 국제 드래프트에서 왕은 대각선을 따라 임의의 거리를 움직여 상대방의 조각을 임의의 거리만큼 뛰어 넘을 수 있습니다 .

체커에서와 같이 동일한 조각을 사용하여 한 번에 일련의 조각을 캡처 할 수 있습니다. 그러나 체커와 달리 국제 초안에서 캡처 한 작품은 전체 시퀀스가 ​​끝날 때까지 제거되지 않습니다. 캡처 한 조각이 같은 빈 사각형에 여러 번 뛰어 오거나 떨어질 수 있지만 상대방의 조각을 두 번 이상 뛰어 넘을 수는 없습니다.

마지막으로 체커와 국제 초안 모두 강제 캡처 규칙이 있습니다. 상대방의 조각을 캡처 할 수 있다면 반드시해야합니다. 그러나 여러 옵션이 여러 개있는 경우 규칙 규칙에 동의하지 않습니다. 체커에서는 최대 캡처 순서를 선택할 수 있습니다 . 즉, 캡처 피스가 더 이상 캡처 할 수 없을 때 끝나는 캡처 시퀀스를 선택할 수 있습니다. 국제 드래프트에서는 가장 긴 캡처 순서를 선택 해야 합니다 . 따라서, 내 문제는 해당 다음과 :

국제 초안에 대한 보드 구성이 주어지면, 반대편의 최대 수를 포착하는 움직임을 찾으십시오.n × n

$n\times n$

$n\times n$

다음 문제가 NP- 완전하다는 것을 증명하는 것으로 충분합니다. (확실히 NP에 있습니다.)

왕만 포함 된 국제 초안 의 보드 구성을 감안할 때 한 명의 플레이어가 한 번에 상대방의 모든 조각을 캡처 할 수 있습니까?n × n

$n\times n$

$n\times n$

해당 체커 문제는 다항식 시간으로 답변 될 수 있습니다. 이것은 재미있는 숙제 운동입니다. 문제는 Demaine, Demaine 및 Eppstein의 Phutball endgames 분석과 유사합니다 . 재미있는 숙제 연습에 대한 해결책이 논문 끝에 나타납니다. 해결책은 Frankel 등 의 FOCS 1978 논문에도 나와 있습니다. 그것은 체커를 최적으로 플레이하는 것이 PSPACE-hard임을 증명합니다. 체커가 실제로 EXPTIME-complete라는 Robson의 1984 증거 를 참조하십시오 .

답변