자바에서 Kakuro 게임을하고 있습니다. Kakuro는 스도쿠와 비슷한 게임 종류입니다. Kakuro 및 Subset Sum (수퍼 세트에 연속적인 양의 정수가 포함되고 부분 집합의 크기가 고정되어 있습니다) k
각각 "지역"에서 그 중복 번호가 없도록 9까지 지역 합계에서 빈 블록의 모든 숫자 지역의 "hintblock"에있는 숫자. 지역의 예는 위의 그림에서 빨간색으로 표시됩니다.
이제 내가하려는 것은 주어진 kakuro 퍼즐을 자동으로 해결할 수있는 인공 지능을 작성하는 것입니다. 먼저 K 요소의 합계가 해당 영역의 "hintblock"에 표시된 수와 같도록 정수 범위 집합 (1,9)에서 K 요소 수의 가능한 모든 조합을 찾아야합니다. (이 경우 K는 해당 영역의 블랭크 블록 수입니다.) 이것은 수퍼 세트가 훨씬 더 균일하고 (1-9의 연속 정수) 서브 세트가 고정 크기임을 제외하고는 "서브 세트 문제점"의 변형입니다 K. 더 나은 점은 수퍼 셋의 범위를 손에서 줄일 수 있다는 것입니다. 예를 들어 그림의 오른쪽 부분에있는 블록을 참조하십시오. 이 경우의 합계는 24이고 K는 3입니다.이 영역에서 임의의 블록을 선택하고 다른 모든 블록이 가능한 가장 큰 값이라고 가정하면 임의의 블록이 (24- 9 + 8)) = 7이다. 21> 9이므로 문제가되지 않는 (24- (1 + 2)) = 21을 계산하여 최대 값에 대해 동일한 작업을 수행 할 수 있습니다. 따라서, 수퍼 세트는 {7,8,9}가된다.
이 영역은 K = Superset 크기이므로 쉬운 경우입니다. 그러나 K가 수퍼 셋 크기보다 훨씬 작 으면 모든 조합을 검사하면 (SuperSize-K)가 계산됩니다. 시각. 이것은 비효율적이다. 내 질문은 지금 거기에 솔루션의 유사 콘텐츠입니다 부분 집합 합계 문제이 경우에 가장 적합한 무엇입니까? 나는 자바로 코딩하지만, SPL과 BrainF * ck를 포함한 모든 프로그래밍 언어를 환영한다.
이것은 좋은 생각이며 꼭 시도해 보겠습니다! 그러나 숫자가 더 커지면 어떨까요? 정수 집합의 범위가 1에서 30 사이라고 가정하면이 방법이 얼마나 효과적일까요? – Ptolemorphism
그것은 겨우 n == 30에서 작동 할 것입니다. 대칭을 통해 저장 공간의 절반을 절약 할 수 있습니다 (크기 k 및 sum s의 모든 집합은 크기 n-k 및 합계 n (n + 1)/2-s 세트의 역입니다). 집합을 4 바이트 비트 마스크로 나타내면이 모두를 유지하는 데 2GB가 필요합니다. 그러나 그것은 아마도 최적의 솔루션이 아닙니다. Otoh, n == 30 인 고유 솔루션 kakuros는 많은 사각형을 채우지 않는 한 쉽게 찾을 수 없으며 솔루션을 찾는 것이 어려울 수 있습니다. – rici
귀하의 대답은 매우 통찰력 있고 도움이됩니다! N = 30은 너무 복잡해집니다. 이제 N을 9 또는 15로 제한하려면 가장 좋은 해결책은 솔루션을 미리 계산하는 것입니다. 나는 그들의 크기 (k)와 그들의 합계에 기초하여 2 차원리스트 또는 배열에서 사전 계산 된 부분 집합을 구성하는 것에 대해 생각하고 있습니다. 솔루션을 찾아야 할 때마다 크기와 합계를 사용하여 잠재적 솔루션을 신속하게 찾습니다. 이 아이디어에 대해 어떻게 생각하십니까? 프로그래밍에 익숙하지는 않지만 해시 테이블과 비슷합니다. 내가 틀렸다면 나를 바로 잡아주세요. – Ptolemorphism