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

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

ただいまの
回答率

88.62%

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

解決済

回答 1

投稿

  • 評価
  • クリップ 1
  • VIEW 745

go55555

score 21

前提・実現したいこと

参考ページ
上記の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ページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

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)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/07/11 16:28

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

    キャンセル

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

  • ただいまの回答率 88.62%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る