The code in tree_to_solution_string mixes the logic of solving the puzzle with the management of a linked list. Splitting your attention between these two levels can make it hard to track down errors. To continue teasing these two aspects apart, we need to make heavier use of the iterator. We’re in the middle of it now, and the code might actually feel like it is more of a mess than when we started. That is common, natural, and nothing to be afraid of.
Well, unless we get directed on to a different task tomorrow. Lets finish this up tonight.
Remember to run the tests after every change.
The allocation of new nodes is done in this code:
new_node = Tree_Node( self.board_index.table[index], curr_node) new_node.check_solved(test_board) curr_node.next_node = new_node curr_node = new_node |
Lets pull that out into its own function.
And…as we do it, we trip over that board_index table again. I am going to pull that out into a global variable for the moment. I have a feeling that I am going to end up encapsulating it inside our Node class eventually, but we are not there yet.
--- a/treesudoku/tree_sudoku.py +++ b/treesudoku/tree_sudoku.py @@ -29,15 +29,20 @@ class SudokuSolver: self.board_strings = board_strings self.boards_dict = self.strings_to_board_dict(self.board_strings) self.box_index = BoxIndex() - self.board_index = BoardIndexTable() self.solved_board_strings = dict() for key, value in self.boards_dict.items(): return_string = self.tree_to_solution_string(value) self.solved_board_strings[key] = return_string def tree_to_solution_string(self, original_board): + def advance(node, test_board): + new_node = Tree_Node( + board_index.table[index], node) + new_node.check_solved(test_board) + node.next_node = new_node + return new_node index = 0 - head_node = Tree_Node(self.board_index.table[index]) + head_node = Tree_Node(board_index.table[index]) curr_node = head_node while index < MAX: curr_board_filling_node = head_node @@ -51,11 +56,8 @@ class SudokuSolver: index += 1 if index >= MAX: continue - new_node = Tree_Node( - self.board_index.table[index], curr_node) - new_node.check_solved(test_board) - curr_node.next_node = new_node - curr_node = new_node + curr_node = advance(curr_node, test_board) + curr_node.check_solved(test_board) else: if len(curr_node.possible_values) == 0: # backtrack @@ -194,6 +196,9 @@ class BoardIndexTable: return return_list +board_index = BoardIndexTable() + + class Tree_Node: def __init__(self, board_spot, last_node=None, next_node=None): self.possible_values = ['1', '2', '3', '4', '5', '6', '7', '8'] |
The advance function belongs in the Node class. I don’t think there is any benefit to keeping it in this interim form, even in git, so I am going to move it straight away. I do have to add an index to it. Still messy.
--- a/treesudoku/tree_sudoku.py +++ b/treesudoku/tree_sudoku.py @@ -29,7 +29,6 @@ class SudokuSolver: self.board_strings = board_strings self.boards_dict = self.strings_to_board_dict(self.board_strings) self.box_index = BoxIndex() - self.board_index = BoardIndexTable() self.solved_board_strings = dict() for key, value in self.boards_dict.items(): return_string = self.tree_to_solution_string(value) @@ -37,7 +36,7 @@ class SudokuSolver: def tree_to_solution_string(self, original_board): index = 0 - head_node = Tree_Node(self.board_index.table[index]) + head_node = Tree_Node(board_index.table[index]) curr_node = head_node while index < MAX: curr_board_filling_node = head_node @@ -51,11 +50,8 @@ class SudokuSolver: index += 1 if index >= MAX: continue - new_node = Tree_Node( - self.board_index.table[index], curr_node) - new_node.check_solved(test_board) - curr_node.next_node = new_node - curr_node = new_node + curr_node = curr_node.advance(test_board, index) + curr_node.check_solved(test_board) else: if len(curr_node.possible_values) == 0: # backtrack @@ -194,6 +190,9 @@ class BoardIndexTable: return return_list +board_index = BoardIndexTable() + + class Tree_Node: def __init__(self, board_spot, last_node=None, next_node=None): self.possible_values = ['1', '2', '3', '4', '5', '6', '7', '8'] @@ -222,6 +221,14 @@ class Tree_Node: self.possible_values = [] self.solved = True + def advance(self, test_board, index): + node = self + new_node = Tree_Node( + board_index.table[index], node) + new_node.check_solved(test_board) + node.next_node = new_node + return new_node + start = time.time() solver = SudokuSolver(import_csv()) |
Lets do the same with the code that deletes the node.
if len(curr_node.possible_values) == 0: # backtrack while len(curr_node.possible_values) == 0: curr_node = curr_node.last_node curr_node.next_node = None index -= 1 |
Move that to a helper function….
index 165948e..8d58d6f 100644 --- a/treesudoku/tree_sudoku.py +++ b/treesudoku/tree_sudoku.py @@ -35,6 +35,11 @@ class SudokuSolver: self.solved_board_strings[key] = return_string def tree_to_solution_string(self, original_board): + def retreat(node): + node = curr_node.last_node + node.next_node = None + return node + index = 0 head_node = Tree_Node(board_index.table[index]) curr_node = head_node @@ -56,8 +61,7 @@ class SudokuSolver: if len(curr_node.possible_values) == 0: # backtrack while len(curr_node.possible_values) == 0: - curr_node = curr_node.last_node - curr_node.next_node = None + curr_node = retreat(curr_node) index -= 1 curr_node.next() return self.build_solution_string(head_node) |
And then move it to the Node class
--- a/treesudoku/tree_sudoku.py +++ b/treesudoku/tree_sudoku.py @@ -56,8 +56,7 @@ class SudokuSolver: if len(curr_node.possible_values) == 0: # backtrack while len(curr_node.possible_values) == 0: - curr_node = curr_node.last_node - curr_node.next_node = None + curr_node = curr_node.retreat() index -= 1 curr_node.next() return self.build_solution_string(head_node) @@ -229,6 +228,11 @@ class Tree_Node: node.next_node = new_node return new_node + def retreat(self): + node = self.last_node + node.next_node = None + return node + start = time.time() solver = SudokuSolver(import_csv()) |
Lets do something about that index. What is clear is that there should only ever be 81 nodes, max, and each node knows its index. Having both the index and the board location is overkill, but you can never have too much overkill. First, lets clear up the parameter list for the Node initialization.
--- a/treesudoku/tree_sudoku.py +++ b/treesudoku/tree_sudoku.py @@ -36,7 +36,7 @@ class SudokuSolver: def tree_to_solution_string(self, original_board): index = 0 - head_node = Tree_Node(board_index.table[index]) + head_node = Tree_Node(board_index.table[index], None) curr_node = head_node while index < MAX: curr_board_filling_node = head_node @@ -193,10 +193,9 @@ board_index = BoardIndexTable() class Tree_Node: - def __init__(self, board_spot, last_node=None, next_node=None): + def __init__(self, board_spot, last_node): self.possible_values = ['1', '2', '3', '4', '5', '6', '7', '8'] self.board_spot = board_spot - self.next_node = next_node self.last_node = last_node self.value = '9' self.solved = False |
Now we can add an index parameter to the end,. Yes, I know I removed it before, I was wrongish.
With the index parameter back, we can encapsulate the BlockIndexTable inside the node object constructor.
self.board_spot = board_index.table[index] |
And then remove it from the parameter list.
--- a/treesudoku/tree_sudoku.py +++ b/treesudoku/tree_sudoku.py @@ -36,7 +36,7 @@ class SudokuSolver: def tree_to_solution_string(self, original_board): index = 0 - head_node = Tree_Node(board_index.table[index]) + head_node = Tree_Node(None, index) curr_node = head_node while index < MAX: curr_board_filling_node = head_node @@ -193,13 +193,14 @@ board_index = BoardIndexTable() class Tree_Node: - def __init__(self, board_spot, last_node=None, next_node=None): + def __init__(self, last_node, index): self.possible_values = ['1', '2', '3', '4', '5', '6', '7', '8'] - self.board_spot = board_spot - self.next_node = next_node + self.board_spot = board_index.table[index] self.last_node = last_node + self.next_node = None self.value = '9' self.solved = False + self.index = index def next(self): self.value = self.possible_values.pop() @@ -222,8 +223,7 @@ class Tree_Node: def advance(self, test_board, index): node = self - new_node = Tree_Node( - board_index.table[index], node) + new_node = Tree_Node(node, self.index + 1) new_node.check_solved(test_board) node.next_node = new_node return new_node |
Including in the advance function.
--- a/treesudoku/tree_sudoku.py +++ b/treesudoku/tree_sudoku.py @@ -50,7 +50,7 @@ class SudokuSolver: index += 1 if index >= MAX: continue - curr_node = curr_node.advance(test_board, index) + curr_node = curr_node.advance(test_board) curr_node.check_solved(test_board) else: if len(curr_node.possible_values) == 0: @@ -221,7 +221,7 @@ class Tree_Node: self.possible_values = [] self.solved = True - def advance(self, test_board, index): + def advance(self, test_board): node = self new_node = Tree_Node(node, self.index + 1) new_node.check_solved(test_board) |
Get rid of the index variable in the code, and use the value from the current node pointer instead. Yeah, I called it a pointer. The one place we have to watch is where it is used for early exit from the loop, but there we can use curr_node.index + 1.
What is trickier is that check at the top.
while index < MAX: |
This controls the whole loop. But curr_node is not always equal to the maximum node when we reach this point. We can’t just check for curr_node.index < MAX because the continue statement kicks us up here when we pass beyond the last node, we’ll never break. If we use a break statement instead of the the continue, it works.
--- a/treesudoku/tree_sudoku.py +++ b/treesudoku/tree_sudoku.py @@ -35,10 +35,9 @@ class SudokuSolver: self.solved_board_strings[key] = return_string def tree_to_solution_string(self, original_board): - index = 0 - head_node = Tree_Node(None, index) + head_node = Tree_Node(None, 0) curr_node = head_node - while index < MAX: + while curr_node.index < MAX: curr_board_filling_node = head_node test_board = copy.deepcopy(original_board) curr_board_filling_node.write(test_board) @@ -47,9 +46,8 @@ class SudokuSolver: curr_board_filling_node.write(test_board) if self.box_index.is_value_valid(test_board, curr_node): - index += 1 - if index >= MAX: - continue + if curr_node.index + 1 >= MAX: + break curr_node = curr_node.advance(test_board) curr_node.check_solved(test_board) else: @@ -57,7 +55,6 @@ class SudokuSolver: # backtrack while len(curr_node.possible_values) == 0: curr_node = curr_node.retreat() - index -= 1 curr_node.next() return self.build_solution_string(head_node) |
At this point, the statement at the top of the loop will never evaluate to False. We could replace it with while True.
It should be clear by now that the code writes the partial solution on a clean board, and then rolls forward with the next thing it is trying. Now that we have a backtrack function, we could reset the nodes to their default state and try again.
And that would mean we don’t even need the early steps of the algorithm that roll forward. This is a pretty big jump. But the break in the middle of the code is the trigger to show that this is where we can change things
Seems I had a bug in advance. I did not find it until I wrote a unit test.
Here is the unit test change:
--- a/treesudoku/test_tree_soduku.py +++ b/treesudoku/test_tree_soduku.py @@ -31,7 +31,38 @@ puzzles = { } +puzzle0 = ("003020600" + + "900305001" + + "001806400" + + "008102900" + + "700000008" + + "006708200" + + "002609500" + + "800203009" + + "005010300") + + def test_sudoku_solver(): solver = tree_sudoku.SudokuSolver(tree_sudoku.import_csv()) for key, solution in solver.solved_board_strings.items(): assert solver.solved_board_strings[key] == puzzles[key] + + +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(test_board) + assert(test_board[0][3] == '0') + assert(node.value == "9") + back_node.write(test_board) + assert(test_board[0][2] == '3') + assert(back_node.board_spot == '02') |
And here is the change to the algorithm, including the fix for the advance method.
--- a/treesudoku/tree_sudoku.py +++ b/treesudoku/tree_sudoku.py @@ -38,24 +38,21 @@ class SudokuSolver: head_node = Tree_Node(None, 0) curr_node = head_node test_board = copy.deepcopy(original_board) + curr_node.check_solved(test_board) while True: - curr_board_filling_node = head_node - curr_board_filling_node.write(test_board) - while curr_board_filling_node.next_node: - curr_board_filling_node = curr_board_filling_node.next_node - curr_board_filling_node.write(test_board) - + if not curr_node.solved: + curr_node.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(test_board) + # backtrack + while len(curr_node.possible_values) == 0: + curr_node = curr_node.retreat(test_board) curr_node.next() + curr_node.write(test_board) return self.build_solution_string(head_node) def build_solution_string(self, head_node): @@ -227,9 +224,9 @@ class Tree_Node: node = self if node.next_node is None: new_node = Tree_Node(node, self.index + 1) - new_node.check_solved(test_board) - node.next_node = new_node - return new_node + new_node.check_solved(test_board) + node.next_node = new_node + return node.next_node def retreat(self, test_board): node = self |
It took a lot of trial and error to get this to run. Here is roughly what I learned:
The original code was rewriting the potential values on the board. This should not have been necessary if the backtracking was correct. IN general, the code was selecting a value on one trip through the loop, and writing, checking it and backtracking on the next time.
With backtracking erasing the old values, there was no need to re-write the potential answer every time. You also don’t need to free and reallocate the nodes on back track. Right now, the linked list is built on demand in a forward only manner.
We are not done here, not by a long shot, but this is the biggest change in behavior. There should not be a need to change the functioning of the algorithm itself.