###前提・実現したいこと
参考ページ
上記のURLを参考にナンプレ(数独)を解くプログラムを作成しています。
上記のURLのコードをつなぎ合わせると確かに答えを導き出せることも確認できましたので、自分なりに書いてみようと思い同じようなコードを書いたのですが、探索の途中で探索が終了していまい、答えにたどりつくことができません。print()やステップ実行を使って原因を探ってみたのですが、自分の力では解決に至りませんでした。
探索が途中で終了してしまうのがなぜかを知りたいです。
###該当のソースコード
Python
1import csv 2 3def main(): 4 pass 5 6def import_csv(filename): 7 """ 8 csvファイルから問題の読み込み 9 """ 10 with open(filename, 'r') as f: 11 reader = csv.reader(f) 12 rows = [] 13 for row in reader: 14 for index, value in enumerate(row): 15 if value == '': 16 row[index] = 0 17 else: 18 row[index] = int(value) 19 rows.append(row) 20 return rows 21 22def export_quiz(filename, quiz): 23 """ 24 csvファイルへ出力 25 """ 26 with open(filename, 'w') as f: 27 writer = csv.writer(f, lineterminator='\n') 28 for row in quiz: 29 writer.writerow(row) 30 31def display_quiz(quiz): 32 """ 33 ナンプレ風に表示 34 """ 35 for row_index, row in enumerate(quiz): 36 for index, value in enumerate(row): 37 if value == '': 38 value = '0' 39 if index == 8: 40 print(value) 41 else: 42 print(value, end=' ') 43 44 if index in (2, 5): 45 print('|', end='') 46 47 if row_index in (2, 5): 48 print('------+------+------') 49 50def solve(quiz, point=[0, 0]): 51 """ 52 再帰的にナンプレを解く 53 """ 54 # global count 55 # count += 1 56 # print(count) 57 # export_quiz('quiz1_ans_count_' + str(count) + '.csv', quiz) 58 59 if point[0] > 8: 60 return True 61 62 if quiz[point[0]][point[1]] != 0: 63 if solve(quiz, next_point(point)): 64 return True 65 else: 66 for number in range(1, 10): 67 if check(quiz, point, number): 68 quiz[point[0]][point[1]] = number 69 if solve(quiz, next_point(point)): 70 return True 71 quiz[point[0]][point[1]] = 0 72 return False 73 print('×') 74 # display_quiz(quiz) 75 76def check(quiz, point, number): 77 """ 78 quizのpointにnumberを入れられるかを判定する 79 return boolean 80 """ 81 return all([check_row(quiz, point[0], number), check_column(quiz, point[1], number), check_block(quiz, point, number)]) 82 83def check_row(quiz, row_index, number): 84 """ 85 quizのrow_indexにnumberを入れられるかを判定する 86 """ 87 88 return number not in quiz[row_index] 89 90def check_column(quiz, column_index, number): 91 """ 92 quizのcolumn_indexにnumberを入れられるかを判定する 93 """ 94 column = [] 95 for row_index in range(9): 96 column.append(quiz[row_index][column_index]) 97 98 return number not in column 99 100def check_block(quiz, point, number): 101 """ 102 quizのpointにnumberを入れられるかを判定する 103 """ 104 block = [] #同一ブロックに属する要素を抽出して格納する 105 row_start = (point[0] // 3) * 3 106 column_start = (point[1] // 3) * 3 107 for row_index in range(row_start, row_start + 3): 108 for column_index in range(column_start, column_start + 3): 109 block.append(quiz[row_index][column_index]) 110 111 return number not in block 112 113def next_point(point): 114 """ 115 次の座標を返す 116 [0, 0] → [0, 1] → ・・・ → [0, 8] → [1, 0] → ・・・ 117 point[0]: row 118 point[1]: column 119 """ 120 if point[1] == 8: 121 point[0] += 1 122 point[1] = 0 123 else: 124 point[1] += 1 125 126 return point 127 128if __name__ == '__main__': 129 filename = 'quiz1' 130 quiz = import_csv(filename + '.csv') 131 export_quiz(filename + '_ans.csv', quiz) 132 133 display_quiz(quiz) 134 count = 0 135 quiz = solve(quiz) 136 # print(quiz) 137 # display_quiz(quiz)
##quiz1.csv
8,5,,,,2,4,, ,,2,,,,,,9 ,,4,,,,,, ,,,1,,7,,,2 3,,5,,,,9,, ,4,,,,,,, ,,,,8,,,7, ,1,7,,,,,, ,,,,3,6,,4,
###試したこと
関数のテストコードの実装,printデバッグ、ステップ実行デバッグ
Python
1import unittest 2import number_place 3 4class TestNumberPlace(unittest.TestCase): 5 quiz = number_place.import_csv('quiz.csv') 6 number_place.display_quiz(quiz) 7 8 def test_next_point(self): 9 self.assertEqual(number_place.next_point([0, 0]), [0, 1]) 10 self.assertEqual(number_place.next_point([0, 8]), [1, 0]) 11 self.assertEqual(number_place.next_point([2, 8]), [3, 0]) 12 self.assertEqual(number_place.next_point([8, 8]), [9, 0]) 13 14 # point = [0, 0] 15 # for n in range(1, 101): 16 # point = number_place.next_point(point) 17 # print(point) 18 19 def test_check_row(self): 20 self.assertEqual(number_place.check_row(TestNumberPlace.quiz, 0, 1), False) 21 self.assertEqual(number_place.check_row(TestNumberPlace.quiz, 0, 4), True) 22 self.assertEqual(number_place.check_row(TestNumberPlace.quiz, 0, 7), False) 23 self.assertEqual(number_place.check_row(TestNumberPlace.quiz, 1, 7), True) 24 self.assertEqual(number_place.check_row(TestNumberPlace.quiz, 1, 1), True) 25 26 def test_check_column(self): 27 self.assertEqual(number_place.check_column(TestNumberPlace.quiz, 0, 1), True) 28 self.assertEqual(number_place.check_column(TestNumberPlace.quiz, 0, 5), False) 29 self.assertEqual(number_place.check_column(TestNumberPlace.quiz, 1, 9), True) 30 self.assertEqual(number_place.check_column(TestNumberPlace.quiz, 1, 7), False) 31 32 def test_check_block(self): 33 self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [3, 6], 1), True) 34 self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [3, 7], 1), True) 35 self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [3, 8], 1), True) 36 self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [4, 6], 1), True) 37 self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [4, 7], 1), True) 38 self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [4, 8], 1), True) 39 self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [5, 6], 1), True) 40 self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [5, 7], 1), True) 41 self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [5, 8], 1), True) 42 43 self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [5, 8], 2), False) 44 45 def test_check(self): 46 self.assertEqual(number_place.check(TestNumberPlace.quiz, [1, 0], 1), True) 47 48 49if __name__ == '__main__': 50 unittest.main()
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2017/07/11 07:28