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

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

ただいまの
回答率

87.61%

pythonについて

受付中

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 1,781
退会済みユーザー

退会済みユーザー

Python言語

前提・実現したいこと

is_goal と next_states の2つのメソッドを実装し、あとは深さ優先探索dfsにSudokuオブジェクトを渡し、初期状態からすべて数字が埋まった終状態への 道順を示す。is_goalメソッドとnext_statesメソッドに関しては以下に記しておきます。

is_goal(self, board) boardオブジェクトで表わされる状態(数字の配置)が数独の解になってい るかどうかをTrueまたはFalseで返す 
next_states(self, board) boardオブジェクトで表わされる状態(数字の配置)においてどれか空いて いるマスを選んで、そこに数独のルール上許される数字を記入して得られる状態(Boardオブジェクト)の リストを返す(先読みして、さらに候補を減らしても可) 

質問の内容

学校で出された課題なのですが、どのような手順でコードを作成していけばいいのかが全く分かりません。また、先生方はテスト作成で忙しいため先生に質問することはできません。is_goalメソッドは一応手は付けましたが、合っているのか間違っているのかわかっていません。next_statesメソッドの中身に関しては見当もつかない状態です。

発生している問題・エラーメッセージ

Traceback (most recent call last):
File "c:/Users/Documents/2年後学期/newton/sudoku.py", line 62, in <module>
boards = dfs(sudoku)
File "c:\Users\Documents\2年後学期\newton\dfs.py", line 7, in dfs
for v in problem.next_states(u):
TypeError: 'NoneType' object is not iterable

該当のソースコード

###<sudoku.py>(呼び出すboard.pyとdfs.pyは下に記してあります。)
from board import Board
from dfs import dfs

class SearchProblem:
    '''探索問題を定義する抽象クラス'''
    def get_start_state(self):
        '''初期状態を返す関数'''
        raise NotImplementedError

    def next_states(self, state):
        '''与えられた状態 state から遷移できる状態のリストを返す関数'''
        raise NotImplementedError

    def is_goal(self, state):
        '''与えられた状態 state がゴールかどうかを True/False で返す関数'''
        raise NotImplementedError


class Sudoku(SearchProblem):
    def __init__(self, board):
        self.board = board

    def get_start_state(self):
        return self.board

    def is_goal(self, board):
         for x in range(9):
            for y in range(9):
                if self.board[x][y] != 0:
                    pass
                else:
                    return False
            return True

    def next_states(self, board):
        pass


if __name__ == '__main__':
    problem_data = \
        [[5, 3, 0, 0, 7, 0, 0, 0, 0],
         [6, 0, 0, 1, 9, 5, 0, 0, 0],
         [0, 9, 8, 0, 0, 0, 0, 6, 0],
         [8, 0, 0, 0, 6, 0, 0, 0, 3],
         [4, 0, 0, 8, 0, 3, 0, 0, 1],
         [7, 0, 0, 0, 2, 0, 0, 0, 6],
         [0, 6, 0, 0, 0, 0, 2, 8, 0],
         [0, 0, 0, 4, 1, 9, 0, 0, 5],
         [0, 0, 0, 0, 8, 0, 0, 7, 9]]
    solution_data = \
        [[5, 3, 4, 6, 7, 8, 9, 1, 2],
         [6, 7, 2, 1, 9, 5, 3, 4, 8],
         [1, 9, 8, 3, 4, 2, 5, 6, 7],
         [8, 5, 9, 7, 6, 1, 4, 2, 3],
         [4, 2, 6, 8, 5, 3, 7, 9, 1],
         [7, 1, 3, 9, 2, 4, 8, 5, 6],
         [9, 6, 1, 5, 3, 7, 2, 8, 4],
         [2, 8, 7, 4, 1, 9, 6, 3, 5],
         [3, 4, 5, 2, 8, 6, 1, 7, 9]]
    board = Board(problem_data)
    sudoku = Sudoku(board)
    boards = dfs(sudoku)
    for i, board in enumerate(boards):
        print('\nSTEP %d' % i)
        print(board)
    assert boards[-1].data == solution_data

###<dfs.py>
def dfs(problem):
    found = {problem.get_start_state()}
    stack = [[problem.get_start_state()]]
    while stack:
        path = stack.pop()
        u = path[-1]  # path の最後のノード
        for v in problem.next_states(u):
            if problem.is_goal(v):
                return path + [v]
            elif v not in found:
                found.add(v)
                stack.append(path + [v])

###<board.py>
class Board:
    num_objects = 0  # Boardオブジェクトがいくつ作られたかトラッキングするクラス変数

    def __init__(self, data, allowed_digits=None):
        '''インスタンス変数self.dataは各マスに置かれた数字を要素とする9x9のリスト、
        self.allowed_digitsは各マスに置ける数字の集合を要素とする9x9のリスト'''
        Board.num_objects += 1
        self.data = data
        if allowed_digits is None:
            self.precompute_allowed_digits()
        else:
            self.allowed_digits = allowed_digits

    @classmethod
    def get_row(cls, obj, x):
        '''9x9の2次元リストobjからx行目を取り出す。objとしてはself.dataまたは
        self.allowed_digitsに準ずる2次元リストが渡されることを想定。'''
        return obj[x]

    @classmethod
    def get_column(cls, obj, y):
        '''9x9の2次元リストobjからy列目を取り出す'''
        return [obj[x][y] for x in range(9)]

    @classmethod
    def get_block(cls, obj, x, y):
        '''9x9の2次元リストobjから(x, y)が属する3x3ブロックを取り出す'''
        base_x = x // 3 * 3
        base_y = y // 3 * 3
        return [obj[x][y] for x in range(base_x, base_x + 3)
                          for y in range(base_y, base_y + 3)]

    def filled(self):
        return all(0 not in self.data[x] for x in range(9))

    def verify(self):
        def check(xs):
            '''リストxsが0~9の数からなり、1~9については重複がないことを
            チェックするヘルパー関数'''
            xs = [x for x in xs if x != 0]
            return (len(set(xs)) == len(xs) and all(1 <= x <= 9 for x in xs))

        return (all(check(Board.get_row(self.data, x)) for x in range(9))
            and all(check(Board.get_column(self.data, y)) for y in range(9))
            and all(check(Board.get_block(self.data, x, y)) for x in (0, 3, 6)
                                                            for y in (0, 3, 6)))

    def get_allowed_digits(self, x, y):
        return list(self.allowed_digits[x][y])

    def update_allowed_digits(self, allowed_digits, x, y, d):
        if d > 0:
            allowed_digits[x][y] = set()
            for obj in Board.get_row(allowed_digits, x):
                # 同じ行のマスの候補リストからdを除外
                obj.discard(d)
            for obj in Board.get_column(allowed_digits, y):
                # 同じ列のマスの候補リストからdを除外
                obj.discard(d)
            for obj in Board.get_block(allowed_digits, x, y):
                # 同じ3x3ブロックのマスの候補リストからdを除外
                obj.discard(d)

    def precompute_allowed_digits(self):
        self.allowed_digits = [
            [{1, 2, 3, 4, 5, 6, 7, 8, 9} for y in range(9)] for x in range(9)
        ]
        for x in range(9):
            for y in range(9):
                d = self.data[x][y]
                self.update_allowed_digits(self.allowed_digits, x, y, d)

    def move(self, x, y, d):
        assert self.data[x][y] == 0
        data = []
        for i, row in enumerate(self.data):
            if i != x:
                data.append(row)
            else:
                new_row = list(row)
                new_row[y] = d
                data.append(new_row)
        allowed_digits = [
            [set(self.allowed_digits[x][y]) for y in range(9)] for x in range(9)
        ]  # set()をつけることによりdeep copyを行う
        self.update_allowed_digits(allowed_digits, x, y, d)
        return Board(data, allowed_digits)

    def __str__(self):
        separator = '+---+---+---+'
        lines = [separator]
        for i in range(0, 9, 3):
            for j in range(i, i + 3):
                lines.append('|%d%d%d|%d%d%d|%d%d%d|' % tuple(self.data[j]))
            lines.append(separator)
        return '\n'.join(lines).replace('0', ' ')


if __name__ == '__main__':
    board = Board([[5, 3, 0, 0, 7, 0, 0, 0, 0],
                   [6, 0, 0, 1, 9, 5, 0, 0, 0],
                   [0, 9, 8, 0, 0, 0, 0, 6, 0],
                   [8, 0, 0, 0, 6, 0, 0, 0, 3],
                   [4, 0, 0, 8, 0, 3, 0, 0, 1],
                   [7, 0, 0, 0, 2, 0, 0, 0, 6],
                   [0, 6, 0, 0, 0, 0, 2, 8, 0],
                   [0, 0, 0, 4, 1, 9, 0, 0, 5],
                   [0, 0, 0, 0, 8, 0, 0, 7, 9]])
    print(board)

よろしければis_goalメソッド、next_statesメソッドのコードを埋めた状態で解説してくださるとありがたいです。

補足情報(FW/ツールのバージョンなど)

採点にあたってはプログラムの正確性のみならず効率も評価されるため、余計な探索を減らすようnext_statesの中身を工夫する必要があります。実行時間が異常に長いプログラムでは答えがあっていても正解とは認められません。

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

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

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

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

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

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

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

    詳細な説明はこちら

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

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

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

質問への追記・修正、ベストアンサー選択の依頼

  • mather

    2019/01/23 14:39

    タイトルに聞きたい内容を書きましょう。

    > 先生方はテスト作成で忙しいため先生に質問することはできません
    では、周囲の生徒に聞きましょう。

    キャンセル

  • mather

    2019/01/23 14:41

    > よろしければis_goalメソッド、next_statesメソッドのコードを埋めた状態で解説してくださるとありがたいです。
    これは「丸投げの質問」になります。ご自身で考えてください。

    キャンセル

  • azuapricot

    2019/01/23 14:59

    課題は自分でやるから課題なのであって
    わからなければわからないと正直にいうのもいいのではないでしょうか。

    こんなに長々書かれても恐らく誰も読んではくれないでしょうし、
    自分でやれというしかないです。
    ここがエラーになってしまって回避できない、どうしたら。
    ここの処理やってみたけど想定通りではない、どうしたら。
    ↑みたいな感じで質問しましょう。
    何から手を付けていいのか全くわからないと言われても、こちらも何から教えればいいのか全く分からないです。

    キャンセル

  • 退会済みユーザー

    2019/01/24 01:42

    複数のユーザーから「やってほしいことだけを記載した丸投げの質問」という意見がありました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

回答 1

+19

なにかの問題とか課題なら、自分で解きましょうよ

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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

関連した質問

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