前提・実現したいこと
Pythonで数独ソルバーを作成しています.おおよその構図はできたと思ったのですが,動かしてみたらうまくいかず,試していく打ちに,間違いの所に数字を入れてしまい,問題が解けなくなっていました.
数独ソルバーのアルゴリズムとしては,
1.データの読み込み
2.値が空欄のところの座標を取得する.
3.1から9までが入ったcandidatesリストを作成し,縦・横・ボックスと比較して,値がすでに存在すれば,リストからその値を削除する.
4.candidatesリストのようそcandidateの要素が1つとなったところから埋めていく.
5.2~4を繰り返す.
といった感じです.
発生している問題・エラーメッセージ
数独ソルバーが正しく動作しない.具体的には,正しい答えではない所に数字を入れてしまい,数独を解けなくしている.無限ループに陥っています.
該当のソースコード
Python
1 2import numpy as np 3 4grid = '27.....163..574..8.....2....637.5.2..5.....6..8.2.345....1.....6..348..114.....85' 5 6def values_from_grid(grid): 7 "テキストから二次元配列のValuesを作成する" 8 values = [] 9 digits = "123456789" 10 chars = [c for c in grid if c in digits or c in '0.'] #01234567890.のみ取得.空欄は'0.'に対応 11 assert len(chars) == 81 #charsが81文字分ないと,エラーを発して強制終了 12 grid_int = list(map(lambda x: int(x) if x != "." else 0, chars)) #数字をcharからintへ.'.'があれば0にする 13 values = np.array(grid_int).reshape(9, 9) 14 15 return values 16 17def index_not_solved(values): #i:y, j:x 18 "空欄のインデックスを取得" 19 pair_indices = [] 20 for y in range(9): 21 for x in range(9): 22 if values[y,x] == 0: 23 pair_indices.append([y,x]) 24 25 return pair_indices 26 27def find_candidate(values, y, x): 28 "空欄に入る候補を探索" 29 candidates = [1,2,3,4,5,6,7,8,9] 30 31 candidates = list(set(candidates) - set(values[:,x])) 32 33 candidates = list(set(candidates) - set(values[y,:])) 34 35 box_tmp = values[(3*(y//3)):(3*(y//3) + 3),(3*(x//3)):(3*(x//3) + 3)].flatten() 36 candidates = list(set(candidates) - set(box_tmp)) 37 38 return candidates 39 40def unique_candidate(candidates, pair_indices, values): 41 "単一候補を埋める" 42 cnt_delete = 0 43 for i, (candidate, pair_index) in enumerate(zip(candidates, pair_indices)): 44 if len(candidate) == 1: 45 values[pair_index[0], pair_index[1]] = candidate[0] 46 candidates.pop(i - cnt_delete) 47 pair_indices.pop(i - cnt_delete) 48 cnt_delete += 1 49 return [candidates, pair_indices, values] 50 51values = values_from_grid(grid) 52pair_indices = index_not_solved(values) 53 54cnt = 1 55while len(pair_indices) > 0: 56 57 candidates = [] 58 for pair_index in pair_indices: 59 candidates.append(find_candidate(values, *pair_index)) 60 pair_indices = index_not_solved(values) 61 62 candidates, pair_indices, values = unique_candidate(candidates, pair_indices, values) 63 64 cnt += 1 65 if cnt > 50: 66 print('I cannot solve...') 67 print('Cuurent solution is') 68 print(values) 69 break 70 71else : 72 print('final solution is') 73 print(values) 74
試したこと
candidatesやvaluesを適宜,print()しながら中身をチェックしたところ,unique_canidiate()のところあたりが原因のような気がすることはわかったのですが,それ以上はわかりませんでした.
values_from_grid,index_not_solved,find_candidateの関数はおそらく問題はないと思われました.
補足情報(FW/ツールのバージョンなど)
Python3.x系を使っています.
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。