データ整理
WEB
ゲーム
パズル
プログラム例パズル
パズルを解くプログラム例を示します．
目次
数独
数独は暇つぶしに調度良いパズルです．単純なルールなので，結構ハマります．ルールについては，「数独-Wikipedia」を参照下さい．
プログラム
数独を解くプログラムです (sudoku.py)．
001 '''数独を計算するモジュール''' 002 import itertools 003 import numpy as np 004 import copy 005 import sys 006 import time 007 008 009 class Solution: 010 '''数独を計算するクラス''' 011 def __init__(self, argv): 012 ''' コンストラクター: 引数のチェックとファイルの読み込み ''' 013 def error_arg(): 014 print('エラー !! 入力の引数の数が違います') 015 print(argv) 016 exit() 017 018 def error_num(): 019 print('入力が 9X9 ではありません') 020 print(self.data_org) 021 exit() 022 023 def error_input_element(): 024 print('入力に 整数: 0 - 9 と異なるものがあります') 025 print(self.data_org) 026 exit() 027 028 allowed = [x for x in range(10)] 029 check = [[False for j in range(9)] for i in range(9)] 030 if len(argv) != 2: error_arg() 031 self.file = argv[1] 032 self.data_org = np.genfromtxt(self.file, delimiter=' ', dtype=int) 033 if(self.data_org.shape[0] != self.data_org.shape[0] != 9):error_num() 034 self.N = self.data_org.shape[0] 035 for i, j in itertools.product(range(9), range(9)): 036 check[i][j] = self.data_org[i][j] in allowed 037 check = np.array(check) 038 if not check.all(): error_input_element() 039 040 041 def print_Question(self): 042 '''読み込んだデータを表示する''' 043 print('問題はつぎのとおり') 044 print(20*'-') 045 for i in range(self.N): 046 for j in range(self.N): 047 if j==self.N-1: 048 if self.data_org[i][j] == 0: 049 print('{0:s}\n'.format('.'), end='') 050 else: 051 print('{0:1d}\n'.format(self.data_org[i][j]), end='') 052 else: 053 if self.data_org[i][j] == 0: 054 print('{0:s} '.format('.'), end='') 055 else: 056 print('{0:1d} '.format(self.data_org[i][j]), end='') 057 print(20*'-') 058 print('\n') 059 060 061 def print_Soluiton(self, sol): 062 '''解を表示する''' 063 print('解はつぎのとおり') 064 print(20*'-') 065 for i in range(self.N): 066 for j in range(self.N): 067 if j==self.N-1: 068 print('{0:1d}\n'.format(sol[i][j][0]), end='') 069 else: 070 print('{0:1d} '.format(sol[i][j][0]), end='') 071 print(20*'-') 072 print('\n') 073 074 075 def Num_det(self, sol): 076 '''確定している要素数を数える''' 077 n = 0 078 for i, j in itertools.product(range(self.N), range(self.N)): 079 if len(sol[i][j]) == 1: n += 1 080 return n 081 082 083 def Num_item(self, sol): 084 '''確定および候補の要素の合計数を数える''' 085 N_arr = [[len(sol[i][j]) for j in range(self.N)] for i in range(self.N)] 086 return int(np.sum(np.array(N_arr))) 087 088 089 def Num_zero(self, sol): 090 '''確定や候補の要素の数がゼロを数える''' 091 N_zero = 0 092 for i, j in itertools.product(range(self.N), range(self.N)): 093 if len(sol[i][j]) == 0: 094 N_zero += 1 095 return N_zero 096 097 098 def is_finished(self, sol): 099 '''解が求められたか否かの判断を行う''' 100 return bool(self.Num_zero(sol)==0 and self.Num_item(sol) == self.N*self.N) 101 102 103 def change_solution(self, is_print=False): 104 '''読み込んだデータを解のデータに変換''' 105 sol = [[0]*self.N for i in range(self.N)] 106 for i, j in itertools.product(range(self.N), range(self.N)): 107 if self.data_org[i][j] == 0: 108 sol[i][j] = [x for x in range(1, self.N+1)] 109 else: 110 sol[i][j] = [self.data_org[i][j]] 111 if is_print: 112 print(sol) 113 return sol 114 115 116 def check_simple(self, sol): 117 '''縦と横，小行列で確定要素を削除''' 118 N_item_old = self.Num_item(sol) 119 while(True): 120 for i, j in itertools.product(range(self.N), range(self.N)): 121 if len(sol[i][j]) == 1: # 確定している値を行の値を削除 122 del_num = sol[i][j][0] 123 for k in range(0, self.N): 124 if k != j and del_num in sol[i][k]: 125 sol[i][k].remove(del_num) 126 if k != i and del_num in sol[k][j]: 127 sol[k][j].remove(del_num) 128 i0, j0 = i//3, j//3 129 for i_sft, j_sft in itertools.product(range(3), range(3)): 130 ki,kj = 3*i0+i_sft, 3*j0+j_sft 131 if ki != i and kj != j and del_num in sol[ki][kj]: 132 sol[ki][kj].remove(del_num) 133 N_item_new = self.Num_item(sol) 134 if N_item_old == N_item_new: 135 break 136 else: 137 N_item_old = N_item_new 138 return sol 139 140 141 def check_same_item(self, sol): 142 '''縦と横，3x3の中の要素に独立した値を確定させる''' 143 N_item_old = self.Num_item(sol) 144 while(True): 145 for i, j in itertools.product(range(self.N), range(self.N)): 146 for test in sol[i][j]: 147 for k in range(self.N): 148 if k!=j and test in sol[i][k]: break 149 else: 150 sol[i][j] = [test] 151 152 for k in range(self.N): 153 if k!=i and test in sol[k][j]: break 154 else: 155 sol[i][j] = [test] 156 157 i0, j0 = i//3, j//3 158 for i_sft, j_sft in itertools.product(range(3), range(3)): 159 ki,kj = 3*i0+i_sft, 3*j0+j_sft 160 if not (ki==i and kj==j) and test in sol[ki][kj]: break 161 else: 162 sol[i][j] = [test] 163 N_item_new = self.Num_item(sol) 164 if N_item_old == N_item_new: 165 break 166 else: 167 N_item_old = N_item_new 168 return sol 169 170 171 172 def candidate(self, sol): 173 '''解の候補を返す''' 174 cnddt = [] 175 for i, j in itertools.product(range(self.N), range(self.N)): 176 nk = len(sol[i][j]) 177 if 1 < nk: 178 for k in range(nk): 179 cnddt.append([i,j, sol[i][j][k]]) 180 return cnddt 181 182 183 '''メイン''' 184 if __name__ == "__main__": 185 start = time.time() 186 sudoku = Solution(argv=sys.argv) 187 sudoku.print_Question() 188 solution = sudoku.change_solution(is_print=False) 189 190 while(True): 191 N_item_old = sudoku.Num_item(solution) 192 solution = sudoku.check_simple(solution) 193 solution = sudoku.check_same_item(solution) 194 N_item_new =sudoku.Num_item(solution) 195 if N_item_old == N_item_new: break 196 197 if not sudoku.is_finished(solution): 198 while(True): 199 solution_org = copy.deepcopy(solution) 200 candidate = sudoku.candidate(solution_org) 201 N_item_org_old = sudoku.Num_item(solution_org) 202 for i in range(len(candidate)): 203 solution = copy.deepcopy(solution_org) 204 solution[candidate[i][0]][candidate[i][1]]=[candidate[i][2]] 205 while(True): 206 N_item_old = sudoku.Num_item(solution) 207 solution = sudoku.check_simple(solution) 208 solution = sudoku.check_same_item(solution) 209 N_item_new =sudoku.Num_item(solution) 210 if sudoku.Num_zero(solution)!=0: 211 d_elem = np.array(solution_org[candidate[i][0]][candidate[i][1]]) 212 d_elem = np.delete(d_elem, np.argwhere(d_elem==candidate[i][2])) 213 solution_org[candidate[i][0]][candidate[i][1]]=list(d_elem) 214 break 215 if N_item_old == N_item_new: break 216 if sudoku.is_finished(solution) == True: break 217 if sudoku.is_finished(solution) == True: break 218 N_item_org_new = sudoku.Num_item(solution_org) 219 print('N: {0:d}\t{1:d}'.format(N_item_org_old, N_item_org_new)) 220 if N_item_org_old == N_item_org_new: break 221 222 if sudoku.is_finished(solution): 223 sudoku.print_Soluiton(solution) 224 else: 225 print('解を求めることができませんでした．') 226 print(solution_org) 227 228 elapsed_time = time.time() - start 229 print("計算時間: {0} [秒]".format(elapsed_time))
インプットと実行方法
プログラムのインプットデータの例を以下に示します．
インプットデータ:問題の例 (Q100.txt)．
#ナンプレ 7 上級編 Question 100
0 0 0 0 0 0 0 0 0
1 6 0 0 0 0 0 5 7
8 0 0 6 0 3 0 0 4
3 0 0 5 0 4 0 0 1
0 2 0 0 9 0 0 6 0
0 0 8 0 0 0 5 0 0
0 0 7 0 0 0 2 0 0
0 0 0 7 0 6 0 0 0
0 0 0 3 4 1 0 0 0
実行コマンドは以下のとおりです．
$ python3 Q100.txt
実行結果は，以下のとおりです．
問題はつぎのとおり -------------------- . . . . . . . . . 1 6 . . . . . 5 7 8 . . 6 . 3 . . 4 3 . . 5 . 4 . . 1 . 2 . . 9 . . 6 . . . 8 . . . 5 . . . . 7 . . . 2 . . . . . 7 . 6 . . . . . . 3 4 1 . . . -------------------- 解はつぎのとおり -------------------- 7 9 3 4 1 5 6 8 2 1 6 4 2 8 9 3 5 7 8 5 2 6 7 3 9 1 4 3 7 9 5 6 4 8 2 1 5 2 1 8 9 7 4 6 3 6 4 8 1 3 2 5 7 9 4 1 7 9 5 8 2 3 6 9 3 5 7 2 6 1 4 8 2 8 6 3 4 1 7 9 5 -------------------- 計算時間: 0.13692736625671387 [秒]
ページ作成情報
参考資料
更新履歴
| 2018年5月22日 | ページの新規作成 |