In my last article on the Long Refactoring series, I elided the process I went through to solve the bug. While preparing to turn the articles into a presentation, I went through the steps myself again, and came across the bug. When I was writing the articles, I was pressed for time, and didn’t go through the process of solving it step by step, which in turn means there is a gap between the pre-and-post states of the code: you can’t get there from here.
Let me take it from where I mentioned that I found a bug, and added the unit test that shows it.
Lets start with running the unit test code. Running it gets me the following error message
________test_advance ________
def test_advance():
test_board = tree_sudoku.build_board(puzzle0)
node = tree_sudoku.Tree_Node(None, 0)
node.write(test_board)
assert (test_board[0][0] == '9')
node = node.advance(test_board)
node = node.advance(test_board)
node.write(test_board)
assert (test_board[0][3] == '0')
node = node.advance(test_board)
node.write(test_board)
assert (test_board[0][3] == '9')
back_node = node.retreat()
> assert (test_board[0][3] == '0')
E AssertionError: assert '9' == '0'
E
E - 0
E + 9 |
From a quick look, the retreat function either is going forward, or creating a new node. Lets use the debugger to get more information there.
diff --git a/test_tree_sudoku.py b/test_tree_sudoku.py index 1dfcdec..25a5ab9 100755 --- a/test_tree_sudoku.py +++ b/test_tree_sudoku.py @@ -59,6 +59,7 @@ def test_advance(): node = node.advance(test_board) node.write(test_board) assert (test_board[0][3] == '9') + import pdb; pdb.set_trace() back_node = node.retreat() assert (test_board[0][3] == '0') assert (node.value == "9") |
Since the other unit test runs the code and calls retreat far too many times, we want to focus in on just the test_advance method. To call this code, I activate the virtual environment and call the pytest executable directly. Note that I have updated my tox.ini to use the more modern python 3.12
pytest test_tree_sudoku.py::test_advance
What becomes clear is that the retreat function does not write to the board. The “9” is not the value returned from the Node. The previous node has the value of “3”. What it looks like is that retreat was supposed to erase the board value, and return it to the state it was before retreat. However, if the was the case, we should have written a specific unit test for it. Looking at the original code, that was not the case. And the functional test still runs.
Looking at my comments in the original article, I think I decided to store the old value in the node when writing a new value. Then, when retreating, I restored the old value prior to returning the previous node. Lets see if that change fixes the unit test.
diff --git a/tree_sudoku.py b/tree_sudoku.py index 4c20d34..042cd69 100755 --- a/tree_sudoku.py +++ b/tree_sudoku.py @@ -196,6 +196,8 @@ class Tree_Node: self.next_node = None self.value = '9' self.index = index + self.old_value = '0' + self.board = None |
Yes this works. Note the ugliness of capturing the board in the write function. That is a sign that there is a dependency missing: the board should be passed in to the constructor of the Node.
This seems to be the point at which I decided I no longer wanted to start from a blank board every time. I would argue that this steps beyond refactoring, as it actively changes the logic of the original program. How far can we go before we make that functional change?
Once thing that seems clear is that the use of an array (really a string) for row/column is making the code much more cluttered. Lets tackle that now.
Start by making row and col a member variables of the node that gets initialized in the constructor.
commit a4d4fa4856275ba9b5be903129b4de712ae1297b Author: Adam Young <adam@younglogic.com> Date: Tue Nov 12 13:47:39 2024 -0500 intro row and col diff --git a/tree_sudoku.py b/tree_sudoku.py index 4c20d34..ca6b936 100755 --- a/tree_sudoku.py +++ b/tree_sudoku.py @@ -192,6 +192,8 @@ class Tree_Node: def __init__(self, last_node, index): self.possible_values = ['1', '2', '3', '4', '5', '6', '7', '8'] self.board_spot = board_index.table[index] + self.row = int(self.board_spot[0]) + self.col = int(self.board_spot[1]) self.last_node = last_node self.next_node = None self.value = '9' |
Now replace the access to the array wi
With these members. Include the test case.
diff --git a/test_tree_sudoku.py b/test_tree_sudoku.py index 2710ca4..462b75b 100755 --- a/test_tree_sudoku.py +++ b/test_tree_sudoku.py @@ -64,4 +64,5 @@ def test_advance(): assert (node.value == "9") back_node.write(test_board) assert (test_board[0][2] == '3') - assert (back_node.board_spot == '02') + assert (back_node.row == 0) + assert (back_node.col == 2) diff --git a/tree_sudoku.py b/tree_sudoku.py index ca6b936..3be293a 100755 --- a/tree_sudoku.py +++ b/tree_sudoku.py @@ -46,8 +46,8 @@ class SudokuSolver: while curr_board_filling_node.next_node: curr_board_filling_node = curr_board_filling_node.next_node curr_board_filling_node.write(test_board) - curr_row = int(curr_board_filling_node.board_spot[0]) - curr_col = int(curr_board_filling_node.board_spot[1]) + curr_row = curr_board_filling_node.row + curr_col = curr_board_filling_node.col test_board[curr_row][curr_col] = curr_board_filling_node.value if self.box_index.is_value_valid(test_board, curr_node): if curr_node.index + 1 >= MAX: @@ -106,9 +106,7 @@ class BoxIndex: self.table = self.fill_box_index_table() def is_value_valid(self, board, node): - row = int(node.board_spot[0]) - col = int(node.board_spot[1]) - return self.value_valid(board, row, col) + return self.value_valid(board, node.row, node.col) def value_valid(self, board, row_index, column_index): row = ['1', '2', '3', '4', '5', '6', '7', '8', '9'] @@ -191,9 +189,9 @@ board_index = BoardIndexTable() class Tree_Node: def __init__(self, last_node, index): self.possible_values = ['1', '2', '3', '4', '5', '6', '7', '8'] - self.board_spot = board_index.table[index] - self.row = int(self.board_spot[0]) - self.col = int(self.board_spot[1]) + board_spot = board_index.table[index] + self.row = int(board_spot[0]) + self.col = int(board_spot[1]) self.last_node = last_node self.next_node = None self.value = '9' @@ -217,15 +215,11 @@ class Tree_Node: return self.value def write(self, board): - curr_row = int(self.board_spot[0]) - curr_col = int(self.board_spot[1]) - board[curr_row][curr_col] = self.value + board[self.row][self.col] = self.value def check_solved(self, board): - row = int(self.board_spot[0]) - col = int(self.board_spot[1]) - if board[row][col] != '0': - self.value = board[row][col] + if board[self.row][self.col] != '0': + self.value = board[self.row][self.col] self.possible_values = [] |
With the code clearer, I can see I missed an opportunity to call write.
index d9df07f..de5c7fe 100755 --- a/tree_sudoku.py +++ b/tree_sudoku.py @@ -46,7 +46,7 @@ class SudokuSolver: while filler.next_node: filler = filler.next_node filler.write(test_board) - test_board[filler.row][filler.col] = filler.value + filler.write(test_board) if self.box_index.is_value_valid(test_board, curr_node): if curr_node.index + 1 >= MAX: break |
Now the main body of the loop looks like this:
def tree_to_solution_string(self, original_board): index = 0 head_node = Tree_Node(None, index) curr_node = head_node while True: filler = head_node test_board = copy.deepcopy(original_board) filler.write(test_board) while filler.next_node: filler = filler.next_node filler.write(test_board) filler.write(test_board) if self.box_index.is_value_valid(test_board, curr_node): if curr_node.index + 1 >= MAX: break curr_node = curr_node.advance(test_board) curr_node.check_solved(test_board) else: if len(curr_node.possible_values) == 0: # backtrack while len(curr_node.possible_values) == 0: curr_node = curr_node.retreat() curr_node.next() return self.build_solution_string(head_node) |
It is still obtuse, but a lot easier to work with. This is the point where I would consider the refactoring done, and would actually improve the implementation.