Q&A
背景
#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件
0
ベストアンサー
コード内容は全く理解できていませんが、わかる範囲で回答します。
まず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]]
投稿2020/07/25 16:43
編集2020/07/25 17:05
総合スコア38341
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2020/07/26 06:00