質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

1回答

1429閲覧

枝分かれの探索がうまく動作しない

go55555

総合スコア21

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

1クリップ

投稿2017/07/11 02:41

###前提・実現したいこと
参考ページ
上記の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()

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

説明の前に、まずは下のコードを見てください。

sample1.py

Python

1def next_num(num): 2 num += 1 3 return num 4 5num = 0 6next_num(num) 7print(num) 8# => 0

sample2.py

Python

1def next_list_num(lst): 2 lst[0] += 1 3 return lst 4 5lst = [0] 6next_list_num(lst) 7print(lst[0]) 8# => 1

上記2つは、ほぼ同じことを数値型リスト内の数値に対して行った結果となります。

これを見ると分るように、数値型では呼び出し先の関数内で変数(num)の値を変更しても呼び出し元の変数に影響することはありませんが、リスト型では変数の値を変更すると呼び出し元の変数にも影響してしまいます。

Pythonでは前者のような型を 「変更不可(Immutable)な型」、後者を「変更可能(Mutable)な型」と呼んでおります。

で、添付されているコードが動かない原因ですが、(参考にしたコードと比較して)Positionデータの型を数値型からリスト型に変更したことが原因となっております。

本来solve()関数では、再帰的に呼び出されたsolve()関数からFalse が戻ってきた際に、前回の続きから実行することで新しい分岐を探索できるのですが、pointデータをリスト化 したことにより、肝心の pointデータ自体の値が更新されており、元の状態を復元することが出来ずに想定外の動作になってしまっております。

対策方法としては(対処療法的となりますが・・)、とりあえずpointデータを更新している関数next_point()に対して、pointデータそのものではなく、pointデータのコピーpoint[:] を渡すように変更すると動作するようになると思います。

Python

1def solve(quiz, point=[0, 0]): 2 """ 3 再帰的にナンプレを解く 4 """ 5 # global count 6 # count += 1 7 # print(count) 8 # export_quiz('quiz1_ans_count_' + str(count) + '.csv', quiz) 9 10 if point[0] > 8: 11 return True 12 13 if quiz[point[0]][point[1]] != 0: 14 if solve(quiz, next_point(point[:])): # <= コピーを渡す 15 return True 16 return False # <= これも追加が必要 17 else: 18 for number in range(1, 10): 19 if check(quiz, point, number): 20 quiz[point[0]][point[1]] = number 21 if solve(quiz, next_point(point[:])): # <= コピーを渡す 22 return True 23 quiz[point[0]][point[1]] = 0 24 return False 25 print('×') 26 # display_quiz(quiz)

投稿2017/07/11 06:54

magichan

総合スコア15898

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

go55555

2017/07/11 07:28

ありがとうございます。Immutable、Mutableという概念があることすら知らなかった。。デバッグを繰り返すうちになんだかpointの値がおかしいというか戻ってくれないというような感覚はあったんですが、原因はそこにあったんですね。 モヤモヤしていたのが解決しました、ありがとうございます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問