Kakuro 및 Subset Sum (수퍼 세트에 연속적인 양의 정수가 포함되고 부분 집합의 크기가 고정되어 있습니다) k

Question

자바에서 Kakuro 게임을하고 있습니다. Kakuro는 스도쿠와 비슷한 게임 종류입니다.

Kakuro의 목표는 1에 정수와 그 빈 블록을 작성하는 것입니다

각각 "지역"에서 그 중복 번호가 없도록 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를 포함한 모든 프로그래밍 언어를 환영한다.

Answer 1

2에서 = 1부터 9까지의 정수 집합 중 512 개의 하위 집합이 있습니다. 실제로이 중 502 개만 크기 0과 1의 집합이 발생하지 않으므로 흥미 롭습니다. afaik를 미리 계산하는 것은 꽤 쉽습니다. 합계 (3에서 45까지)와 크기로 구성하십시오. 그런 다음 대상 집합을 얻는 간단한 조회 일뿐입니다.

표준 9 정수 Kakuro의 경우 setsize/sum 조합에는 12 가지 이상의 해결 방법이 없습니다. 12 개의 해를 가진 두 개의 조합은 k = 5/sum = 25이고 k = 4/sum = 20이다. (이 이중성은 우발적 인 것이 아니므로 사전 계산 된 세트의 절반을 저장하지 않아도됩니다. 주어진 n (이 경우 9)에 대해 k 숫자의 합은 s의 합으로 솔루션으로 변환 될 수 있습니다 n-k에 대한 숫자 합은 n*(n+1)/2 - s으로 간단히 모든 하위 집합의 보수를 취합니다.)

그러나, n이 증가하면 최대 부분 집합 수가 기하 급수적으로 증가합니다. 나는이 Python3 "한 줄"을 사용하여, 최대 30 최대 값을 계산 :

for j in range(9,31): 
    print(j, Counter((len(k),sum(k)) 
        for k in combinations(range(1,j+1), j//2) 
       ).most_common(1)) 

마지막 두 값을 계산하는 데 몇 초 걸렸습니다, 그래서 이것은 확실히 가능성을 열거하기위한 가장 효율적인 전략이 아니다. 가독성을 위해 약간의 출력을 정리했습니다.

N  k  sum  count 
--  --  ---  ----- 
9  4  20   12 
10  5  28   20 
11  5  31   32 
12  6  39   58 
13  6  42   94 
14  7  52   169 
15  7  56   289 
16  8  68   526 
17  8  72   910 
18  9  86  1667 
19  9  90  2934 
20  10  105  5448 
21  10  110  9686 
22  11  126  18084 
23  11  132  32540 
24  12  150  61108 
25  12  156  110780 
26  13  175  208960 
27  13  182  381676 
28  14  203  723354 
29  14  210  1328980 
30  15  233  2527074 

엄청난 가능성으로 완전한 솔루션으로 가쿠로를 생성하는 것이 훨씬 어려워졌습니다.물론, 가능한 k/sum 조합의 대부분을 피할 수는 있지만, 퍼즐 자체가 unscalability를 내장하고있는 것처럼 보입니다.

(참고 :이 정수 시퀀스의 온라인 백과 사전 Sequence A277218이며,이 Magic Carpets과 관련이있다 Sequence A055606, 관련이있다.)

Answer 2

나는 부분 집합의 합을 무시하고 대신 치료 제안 제약 조건 만족 문제. 그리고 내 첫 번째 패스는 최적화를 가진 백 트랙킹 알고리즘이 될 것이고, 가장 작은 가능성을 가진 사각형에 대해 다음 추측이 이루어질 것입니다.

NP 하드 문제입니다. 아니요 솔루션은 확장 성이 좋습니다.