枝分かれの探索がうまく動作しない
解決済
回答 1
投稿
- 評価
- クリップ 1
- VIEW 780
前提・実現したいこと
参考ページ
上記のURLを参考にナンプレ(数独)を解くプログラムを作成しています。
上記のURLのコードをつなぎ合わせると確かに答えを導き出せることも確認できましたので、自分なりに書いてみようと思い同じようなコードを書いたのですが、探索の途中で探索が終了していまい、答えにたどりつくことができません。print()やステップ実行を使って原因を探ってみたのですが、自分の力では解決に至りませんでした。
探索が途中で終了してしまうのがなぜかを知りたいです。
該当のソースコード
import csv
def main():
pass
def import_csv(filename):
"""
csvファイルから問題の読み込み
"""
with open(filename, 'r') as f:
reader = csv.reader(f)
rows = []
for row in reader:
for index, value in enumerate(row):
if value == '':
row[index] = 0
else:
row[index] = int(value)
rows.append(row)
return rows
def export_quiz(filename, quiz):
"""
csvファイルへ出力
"""
with open(filename, 'w') as f:
writer = csv.writer(f, lineterminator='\n')
for row in quiz:
writer.writerow(row)
def display_quiz(quiz):
"""
ナンプレ風に表示
"""
for row_index, row in enumerate(quiz):
for index, value in enumerate(row):
if value == '':
value = '0'
if index == 8:
print(value)
else:
print(value, end=' ')
if index in (2, 5):
print('|', end='')
if row_index in (2, 5):
print('------+------+------')
def solve(quiz, point=[0, 0]):
"""
再帰的にナンプレを解く
"""
# global count
# count += 1
# print(count)
# export_quiz('quiz1_ans_count_' + str(count) + '.csv', quiz)
if point[0] > 8:
return True
if quiz[point[0]][point[1]] != 0:
if solve(quiz, next_point(point)):
return True
else:
for number in range(1, 10):
if check(quiz, point, number):
quiz[point[0]][point[1]] = number
if solve(quiz, next_point(point)):
return True
quiz[point[0]][point[1]] = 0
return False
print('×')
# display_quiz(quiz)
def check(quiz, point, number):
"""
quizのpointにnumberを入れられるかを判定する
return boolean
"""
return all([check_row(quiz, point[0], number), check_column(quiz, point[1], number), check_block(quiz, point, number)])
def check_row(quiz, row_index, number):
"""
quizのrow_indexにnumberを入れられるかを判定する
"""
return number not in quiz[row_index]
def check_column(quiz, column_index, number):
"""
quizのcolumn_indexにnumberを入れられるかを判定する
"""
column = []
for row_index in range(9):
column.append(quiz[row_index][column_index])
return number not in column
def check_block(quiz, point, number):
"""
quizのpointにnumberを入れられるかを判定する
"""
block = [] #同一ブロックに属する要素を抽出して格納する
row_start = (point[0] // 3) * 3
column_start = (point[1] // 3) * 3
for row_index in range(row_start, row_start + 3):
for column_index in range(column_start, column_start + 3):
block.append(quiz[row_index][column_index])
return number not in block
def next_point(point):
"""
次の座標を返す
[0, 0] → [0, 1] → ・・・ → [0, 8] → [1, 0] → ・・・
point[0]: row
point[1]: column
"""
if point[1] == 8:
point[0] += 1
point[1] = 0
else:
point[1] += 1
return point
if __name__ == '__main__':
filename = 'quiz1'
quiz = import_csv(filename + '.csv')
export_quiz(filename + '_ans.csv', quiz)
display_quiz(quiz)
count = 0
quiz = solve(quiz)
# print(quiz)
# 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デバッグ、ステップ実行デバッグ
import unittest
import number_place
class TestNumberPlace(unittest.TestCase):
quiz = number_place.import_csv('quiz.csv')
number_place.display_quiz(quiz)
def test_next_point(self):
self.assertEqual(number_place.next_point([0, 0]), [0, 1])
self.assertEqual(number_place.next_point([0, 8]), [1, 0])
self.assertEqual(number_place.next_point([2, 8]), [3, 0])
self.assertEqual(number_place.next_point([8, 8]), [9, 0])
# point = [0, 0]
# for n in range(1, 101):
# point = number_place.next_point(point)
# print(point)
def test_check_row(self):
self.assertEqual(number_place.check_row(TestNumberPlace.quiz, 0, 1), False)
self.assertEqual(number_place.check_row(TestNumberPlace.quiz, 0, 4), True)
self.assertEqual(number_place.check_row(TestNumberPlace.quiz, 0, 7), False)
self.assertEqual(number_place.check_row(TestNumberPlace.quiz, 1, 7), True)
self.assertEqual(number_place.check_row(TestNumberPlace.quiz, 1, 1), True)
def test_check_column(self):
self.assertEqual(number_place.check_column(TestNumberPlace.quiz, 0, 1), True)
self.assertEqual(number_place.check_column(TestNumberPlace.quiz, 0, 5), False)
self.assertEqual(number_place.check_column(TestNumberPlace.quiz, 1, 9), True)
self.assertEqual(number_place.check_column(TestNumberPlace.quiz, 1, 7), False)
def test_check_block(self):
self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [3, 6], 1), True)
self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [3, 7], 1), True)
self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [3, 8], 1), True)
self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [4, 6], 1), True)
self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [4, 7], 1), True)
self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [4, 8], 1), True)
self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [5, 6], 1), True)
self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [5, 7], 1), True)
self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [5, 8], 1), True)
self.assertEqual(number_place.check_block(TestNumberPlace.quiz, [5, 8], 2), False)
def test_check(self):
self.assertEqual(number_place.check(TestNumberPlace.quiz, [1, 0], 1), True)
if __name__ == '__main__':
unittest.main()
-
気になる質問をクリップする
クリップした質問は、後からいつでもマイページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
クリップを取り消します
-
良い質問の評価を上げる
以下のような質問は評価を上げましょう
- 質問内容が明確
- 自分も答えを知りたい
- 質問者以外のユーザにも役立つ
評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。
質問の評価を上げたことを取り消します
-
評価を下げられる数の上限に達しました
評価を下げることができません
- 1日5回まで評価を下げられます
- 1日に1ユーザに対して2回まで評価を下げられます
質問の評価を下げる
teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。
- プログラミングに関係のない質問
- やってほしいことだけを記載した丸投げの質問
- 問題・課題が含まれていない質問
- 意図的に内容が抹消された質問
- 過去に投稿した質問と同じ内容の質問
- 広告と受け取られるような投稿
評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。
質問の評価を下げたことを取り消します
この機能は開放されていません
評価を下げる条件を満たしてません
質問の評価を下げる機能の利用条件
この機能を利用するためには、以下の事項を行う必要があります。
- 質問回答など一定の行動
-
メールアドレスの認証
メールアドレスの認証
-
質問評価に関するヘルプページの閲覧
質問評価に関するヘルプページの閲覧
checkベストアンサー
+2
説明の前に、まずは下のコードを見てください。
sample1.py
def next_num(num):
num += 1
return num
num = 0
next_num(num)
print(num)
# => 0
sample2.py
def next_list_num(lst):
lst[0] += 1
return lst
lst = [0]
next_list_num(lst)
print(lst[0])
# => 1
上記2つは、ほぼ同じことを数値型とリスト内の数値に対して行った結果となります。
これを見ると分るように、数値型では呼び出し先の関数内で変数(num)の値を変更しても呼び出し元の変数に影響することはありませんが、リスト型では変数の値を変更すると呼び出し元の変数にも影響してしまいます。
Pythonでは前者のような型を 「変更不可(Immutable)な型」、後者を「変更可能(Mutable)な型」と呼んでおります。
で、添付されているコードが動かない原因ですが、(参考にしたコードと比較して)Positionデータの型を数値型からリスト型に変更したことが原因となっております。
本来solve()
関数では、再帰的に呼び出されたsolve()
関数からFalse
が戻ってきた際に、前回の続きから実行することで新しい分岐を探索できるのですが、point
データをリスト化 したことにより、肝心の point
データ自体の値が更新されており、元の状態を復元することが出来ずに想定外の動作になってしまっております。
対策方法としては(対処療法的となりますが・・)、とりあえずpoint
データを更新している関数next_point()
に対して、point
データそのものではなく、point
データのコピーpoint[:]
を渡すように変更すると動作するようになると思います。
def solve(quiz, point=[0, 0]):
"""
再帰的にナンプレを解く
"""
# global count
# count += 1
# print(count)
# export_quiz('quiz1_ans_count_' + str(count) + '.csv', quiz)
if point[0] > 8:
return True
if quiz[point[0]][point[1]] != 0:
if solve(quiz, next_point(point[:])): # <= コピーを渡す
return True
return False # <= これも追加が必要
else:
for number in range(1, 10):
if check(quiz, point, number):
quiz[point[0]][point[1]] = number
if solve(quiz, next_point(point[:])): # <= コピーを渡す
return True
quiz[point[0]][point[1]] = 0
return False
print('×')
# display_quiz(quiz)
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
15分調べてもわからないことは、teratailで質問しよう!
- ただいまの回答率 88.35%
- 質問をまとめることで、思考を整理して素早く解決
- テンプレート機能で、簡単に質問をまとめられる
2017/07/11 16:28
モヤモヤしていたのが解決しました、ありがとうございます。