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

該当のソースコード

python言語
1###<sudoku.py>(呼び出すboard.pyとdfs.pyは下に記してあります。)
2from board import Board
3from dfs import dfs
4
5class SearchProblem:
6    '''探索問題を定義する抽象クラス'''
7    def get_start_state(self):
8        '''初期状態を返す関数'''
9        raise NotImplementedError
10    
11    def next_states(self, state):
12        '''与えられた状態 state から遷移できる状態のリストを返す関数'''
13        raise NotImplementedError
14
15    def is_goal(self, state):
16        '''与えられた状態 state がゴールかどうかを True/False で返す関数'''
17        raise NotImplementedError
18
19
20class Sudoku(SearchProblem):
21    def __init__(self, board):
22        self.board = board
23    
24    def get_start_state(self):
25        return self.board
26    
27    def is_goal(self, board):
28         for x in range(9):
29            for y in range(9):
30                if self.board[x][y] != 0:
31                    pass
32                else:
33                    return False
34            return True
35 
36    def next_states(self, board):
37        pass
38
39
40if __name__ == '__main__':
41    problem_data = \
42        [[5, 3, 0, 0, 7, 0, 0, 0, 0],
43         [6, 0, 0, 1, 9, 5, 0, 0, 0],
44         [0, 9, 8, 0, 0, 0, 0, 6, 0],
45         [8, 0, 0, 0, 6, 0, 0, 0, 3],
46         [4, 0, 0, 8, 0, 3, 0, 0, 1],
47         [7, 0, 0, 0, 2, 0, 0, 0, 6],
48         [0, 6, 0, 0, 0, 0, 2, 8, 0],
49         [0, 0, 0, 4, 1, 9, 0, 0, 5],
50         [0, 0, 0, 0, 8, 0, 0, 7, 9]]
51    solution_data = \
52        [[5, 3, 4, 6, 7, 8, 9, 1, 2],
53         [6, 7, 2, 1, 9, 5, 3, 4, 8],
54         [1, 9, 8, 3, 4, 2, 5, 6, 7],
55         [8, 5, 9, 7, 6, 1, 4, 2, 3],
56         [4, 2, 6, 8, 5, 3, 7, 9, 1],
57         [7, 1, 3, 9, 2, 4, 8, 5, 6],
58         [9, 6, 1, 5, 3, 7, 2, 8, 4],
59         [2, 8, 7, 4, 1, 9, 6, 3, 5],
60         [3, 4, 5, 2, 8, 6, 1, 7, 9]]
61    board = Board(problem_data)
62    sudoku = Sudoku(board)
63    boards = dfs(sudoku)
64    for i, board in enumerate(boards):
65        print('\nSTEP %d' % i)
66        print(board)
67    assert boards[-1].data == solution_data
68
69###<dfs.py>
70def dfs(problem):
71    found = {problem.get_start_state()}
72    stack = [[problem.get_start_state()]]
73    while stack:
74        path = stack.pop()
75        u = path[-1]  # path の最後のノード
76        for v in problem.next_states(u):
77            if problem.is_goal(v):
78                return path + [v]
79            elif v not in found:
80                found.add(v)
81                stack.append(path + [v])
82
83###<board.py>
84class Board:
85    num_objects = 0  # Boardオブジェクトがいくつ作られたかトラッキングするクラス変数
86
87    def __init__(self, data, allowed_digits=None):
88        '''インスタンス変数self.dataは各マスに置かれた数字を要素とする9x9のリスト、
89        self.allowed_digitsは各マスに置ける数字の集合を要素とする9x9のリスト'''
90        Board.num_objects += 1
91        self.data = data
92        if allowed_digits is None:
93            self.precompute_allowed_digits()
94        else:
95            self.allowed_digits = allowed_digits
96
97    @classmethod
98    def get_row(cls, obj, x):
99        '''9x9の2次元リストobjからx行目を取り出す。objとしてはself.dataまたは
100        self.allowed_digitsに準ずる2次元リストが渡されることを想定。'''
101        return obj[x]
102
103    @classmethod
104    def get_column(cls, obj, y):
105        '''9x9の2次元リストobjからy列目を取り出す'''
106        return [obj[x][y] for x in range(9)]
107
108    @classmethod
109    def get_block(cls, obj, x, y):
110        '''9x9の2次元リストobjから(x, y)が属する3x3ブロックを取り出す'''
111        base_x = x // 3 * 3
112        base_y = y // 3 * 3
113        return [obj[x][y] for x in range(base_x, base_x + 3)
114                          for y in range(base_y, base_y + 3)]
115
116    def filled(self):
117        return all(0 not in self.data[x] for x in range(9))
118
119    def verify(self):
120        def check(xs):
121            '''リストxsが0~9の数からなり、1~9については重複がないことを
122            チェックするヘルパー関数'''
123            xs = [x for x in xs if x != 0]
124            return (len(set(xs)) == len(xs) and all(1 <= x <= 9 for x in xs))
125
126        return (all(check(Board.get_row(self.data, x)) for x in range(9))
127            and all(check(Board.get_column(self.data, y)) for y in range(9))
128            and all(check(Board.get_block(self.data, x, y)) for x in (0, 3, 6)
129                                                            for y in (0, 3, 6)))
130
131    def get_allowed_digits(self, x, y):
132        return list(self.allowed_digits[x][y])
133
134    def update_allowed_digits(self, allowed_digits, x, y, d):
135        if d > 0:
136            allowed_digits[x][y] = set()
137            for obj in Board.get_row(allowed_digits, x):
138                # 同じ行のマスの候補リストからdを除外
139                obj.discard(d)
140            for obj in Board.get_column(allowed_digits, y):
141                # 同じ列のマスの候補リストからdを除外
142                obj.discard(d)
143            for obj in Board.get_block(allowed_digits, x, y):
144                # 同じ3x3ブロックのマスの候補リストからdを除外
145                obj.discard(d)
146
147    def precompute_allowed_digits(self):
148        self.allowed_digits = [
149            [{1, 2, 3, 4, 5, 6, 7, 8, 9} for y in range(9)] for x in range(9)
150        ]
151        for x in range(9):
152            for y in range(9):
153                d = self.data[x][y]
154                self.update_allowed_digits(self.allowed_digits, x, y, d)
155
156    def move(self, x, y, d):
157        assert self.data[x][y] == 0
158        data = []
159        for i, row in enumerate(self.data):
160            if i != x:
161                data.append(row)
162            else:
163                new_row = list(row)
164                new_row[y] = d
165                data.append(new_row)
166        allowed_digits = [
167            [set(self.allowed_digits[x][y]) for y in range(9)] for x in range(9)
168        ]  # set()をつけることによりdeep copyを行う
169        self.update_allowed_digits(allowed_digits, x, y, d)
170        return Board(data, allowed_digits)
171
172    def __str__(self):
173        separator = '+---+---+---+'
174        lines = [separator]
175        for i in range(0, 9, 3):
176            for j in range(i, i + 3):
177                lines.append('|%d%d%d|%d%d%d|%d%d%d|' % tuple(self.data[j]))
178            lines.append(separator)
179        return '\n'.join(lines).replace('0', ' ')
180
181
182if __name__ == '__main__':
183    board = Board([[5, 3, 0, 0, 7, 0, 0, 0, 0],
184                   [6, 0, 0, 1, 9, 5, 0, 0, 0],
185                   [0, 9, 8, 0, 0, 0, 0, 6, 0],
186                   [8, 0, 0, 0, 6, 0, 0, 0, 3],
187                   [4, 0, 0, 8, 0, 3, 0, 0, 1],
188                   [7, 0, 0, 0, 2, 0, 0, 0, 6],
189                   [0, 6, 0, 0, 0, 0, 2, 8, 0],
190                   [0, 0, 0, 4, 1, 9, 0, 0, 5],
191                   [0, 0, 0, 0, 8, 0, 0, 7, 9]])
192    print(board)
193

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

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

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

mather

2019/01/23 05:39

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

mather

2019/01/23 05:41

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

azuapricot

2019/01/23 05:59

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