背景

#atgm_2020という集団戦型のクイズで出題された問題のなかで特殊な数独を解く必要が出てきました。問題の答え自体は別の人によってすでに導き出されたのですが、せっかく自分で解きかけたのでやりきりたいという状況です。

質問

今、下に示すような16x16でかつ、対角線上の数字も重複しないという制約の付いた特殊な数独を解こうとしています。

数独問題を解くアルゴリズムと実装 - Qiitaの
「3. Pulp使ったConstraint programming」
を参考に次のようにプログラムを書いたところ、

python
1# -*- coding: utf-8 -*-
2import argparse
3import csv
4from pulp import LpVariable, LpInteger, LpProblem, LpMinimize, LpStatus, lpSum, value
5
6
7def main(inp):
8    n = 16
9    b = 4
10    digits = [str(d + 1) for d in range(n)]
11    values = rows = columns = digits
12    answers = []
13
14    choices = LpVariable.dicts("Choice", (values, rows, columns), 0, 1, LpInteger)
15    boxes = [[(rows[b * i + k], columns[b * j + l]) for k in range(b) for l in range(b)] for j in range(b) for i in range(b)]
16    # 問題提議
17    problem = LpProblem("SolvingSudoku", LpMinimize)  # MinimizeでもMaximizeでもOK
18    problem += 0, "Arbitrary Objective Function"
19
20    # 制約追加
21    for r in rows:
22        for c in columns:
23            problem += lpSum([choices[v][r][c] for v in values]) == 1, ""
24
25    for v in values:
26        for r in rows:
27            problem += lpSum([choices[v][r][c] for c in columns]) == 1, ""
28
29        for c in columns:
30            problem += lpSum([choices[v][r][c] for r in rows]) == 1, ""
31
32        for b in boxes:
33            problem += lpSum([choices[v][r][c] for (r, c) in b]) == 1, ""
34
35        problem += lpSum([choices[v][i][i] for i in range(n)]) == 1, ""
36        problem += lpSum([choices[v][r][c] for (r, c) in zip(range(n), reversed(range(n)))]) == 1, ""
37
38    for i in range(n**2):
39        val = inp[i]
40        if val != '0':
41            problem += choices[str(val)][str(i/n + 1)][str(i % n + 1)] == 1, ""
42
43    while True:
44        # cbcソルバー利用
45        problem.solve()
46        if LpStatus[problem.status] == "Optimal":
47            answers.append(''.join([v for r in rows for c in columns for v in values if value(choices[v][r][c]) == 1]))
48            # 見つけた解を制約として追加
49            problem += lpSum(
50                [choices[v][r][c] for v in values for r in rows for c in columns if value(choices[v][r][c]) == 1]
51            ) <= 80
52        else:
53            break
54
55    if answers:
56        # 最初の解だけ表示
57        print(answers[0])
58
59
60if __name__ == '__main__':
61    f = csv.reader("input.csv", delimiter=",", doublequote=True, lineterminator="\r\n", quotechar='"', skipinitialspace=True)  
62    main(f)

csv
10,4,6,9,13,14,0,11,0,16,15,8,12,0,0,3
28,0,0,16,0,0,0,0,13,7,0,0,0,0,0,10
311,0,0,0,7,0,3,0,0,0,9,0,0,0,1,0
414,0,0,0,1,0,16,0,0,3,0,6,0,0,0,8
50,0,1,14,0,3,0,0,9,0,0,0,7,0,0,5
616,7,0,0,15,0,0,0,0,5,0,0,0,3,0,6
76,0,4,11,0,2,0,7,0,0,0,16,0,0,10,9
80,13,0,0,16,0,14,0,0,8,6,0,1,0,0,15
90,0,10,0,5,0,8,0,0,11,0,0,9,0,6,0
105,6,0,15,0,13,0,0,14,0,16,9,0,0,0,11
110,0,0,0,0,0,11,0,6,0,0,0,2,0,5,0
129,0,11,0,0,0,0,0,0,0,0,0,0,14,0,0
137,11,0,8,9,1,0,0,16,0,0,0,0,13,0,0
1410,0,0,0,0,0,13,16,8,9,7,15,0,0,0,2
1513,0,0,0,3,15,0,0,0,12,0,2,8,0,0,7
1615,9,2,4,0,7,12,0,5,0,3,0,0,1,0,0

Traceback (most recent call last):
  File "solve.py", line 62, in <module>
    main(f)
  File "solve.py", line 35, in main
    problem += lpSum([choices[v][i][i] for i in range(n)]) == 1, ""
  File "solve.py", line 35, in <listcomp>
    problem += lpSum([choices[v][i][i] for i in range(n)]) == 1, ""
KeyError: 0

と言われます。
KeyError自体はググった感じでは辞書構造のものでkeyが見つからなかったときに発生する例外だと思うのですが、pulpはおろか、python自体殆ど触ったことがないため、解決策が検討も付きません。

環境

$cat /etc/os-release
NAME="Ubuntu"
VERSION="18.04.4 LTS (Bionic Beaver)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 18.04.4 LTS"
VERSION_ID="18.04"
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
VERSION_CODENAME=bionic
UBUNTU_CODENAME=bionic

$python3 -V
Python 3.6.9

$python3 -m pip -V
pip 20.1.1 from /usr/local/lib/python3.6/dist-packages/pip (python 3.6)

試したこと

デバッガーでステップインすればなんとかならないかと思いましたがなんの成果も得られませんでした

行動規範の内容に同意します

回答1件

ベストアンサー

コード内容は全く理解できていませんが、わかる範囲で回答します。
まずchicesの中身を覗いたところ、キーは'1'～'16'の文字列だったので
problem += lpSum([choices[v][i][i] for i in range(n)]) == 1, ""は
problem += lpSum([choices[v][str(i+1)][str(i+1)] for i in range(n)]) == 1, ""であるべきかと思います。
次の行のr、cも同様です。

上記を修正後、次にはval = inp[i]でTypeError: '_csv.reader' object is not subscriptableが発生します。
ここは素直に呼び出し元で以下のように書き換えます。

Python
1    with open('input.csv') as fp:
2        f = []
3        lines = fp.read().splitlines()
4        for line in lines:
5            f += line.split(',')

最後にproblem += choices[str(val)][str(i / n + 1)][str(i % n + 1)] == 1, ""にてKeyError: '1.0625'が発生します。
i / nの結果がfloatだからです。
ここは整数であるべきなのですが、コード内容が全く分からないので勘で//に修正します。
Pythonでは//は商を整数で返します。
すると以下のような結果を得ることができました。
繰り返しになりますが、内容理解していないので正しいかはわかりません。

14691314101121615812573835162129151371411164101121312783641095151611414101571516411312613298281141036139154117121651679101511181252144313661541112257311316148109313125164149108671112154141025168121511139761356815413711421693101211121671314911364810215519111361015271351216148471138912516141046131512101214111613168971554321351663154101121128914715924871214563131011116

追記

結果が見づらかったので、そのままnumpy配列で保持しprintするように修正しました。

Python
1            #answers.append(','.join([v for r in rows for c in columns for v in values if value(choices[v][r][c]) == 1]))
2            import numpy as np
3            ans = np.array([int(v) for r in rows for c in columns for v in values if value(choices[v][r][c]) == 1]).reshape(16,-1)
4            answers.append(ans)

Python
1[[ 1  4  6  9 13 14 10 11  2 16 15  8 12  5  7  3]
2 [ 8  3  5 16  2 12  9 15 13  7 14  1 11  6  4 10]
3 [11  2 13 12  7  8  3  6  4 10  9  5 15 16  1 14]
4 [14 10 15  7  1  5 16  4 11  3 12  6 13  2  9  8]
5 [ 2  8  1 14 10  3  6 13  9 15  4 11  7 12 16  5]
6 [16  7  9 10 15 11  1  8 12  5  2 14  4  3 13  6]
7 [ 6 15  4 11 12  2  5  7  3  1 13 16 14  8 10  9]
8 [ 3 13 12  5 16  4 14  9 10  8  6  7  1 11  2 15]
9 [ 4 14 10  2  5 16  8 12 15 11  1  3  9  7  6 13]
10 [ 5  6  8 15  4 13  7  1 14  2 16  9  3 10 12 11]
11 [12 16  7 13 14  9 11  3  6  4  8 10  2 15  5  1]
12 [ 9  1 11  3  6 10 15  2  7 13  5 12 16 14  8  4]
13 [ 7 11  3  8  9  1  2  5 16 14 10  4  6 13 15 12]
14 [10 12 14  1 11  6 13 16  8  9  7 15  5  4  3  2]
15 [13  5 16  6  3 15  4 10  1 12 11  2  8  9 14  7]
16 [15  9  2  4  8  7 12 14  5  6  3 13 10  1 11 16]]