180 lines of code is not horrible, but it is a lot to wrap your mind around all at once. In order to get oriented to the code, we’re going to take on one of the simpler refactorings. We are going to replace a bunch of the magic numbers with symbolic constants.
Sudoku puzzles are 9 squares by 9 squares. Thus, we should expect to see a lot of 9s in the code.
grep 9 tree_sudoku.py rows = re.findall(r"\d{9}", board) row = ['1', '2', '3', '4', '5', '6', '7', '8', '9'] column = ['1', '2', '3', '4', '5', '6', '7', '8', '9'] square = ['1', '2', '3', '4', '5', '6', '7', '8', '9'] for a_row in range(9): box_center[1] -= 9 for row in range(9): for column in range(9): self.value = '9' |
We’re going to skip the places where it is in the character arrays for now, but those ranges and centers look like good targets. To Start, lets run our test to make sure everything still runs. OK. Now lets start by adding our symbolic constant at the top of the file. I am going to use DIM, short for dimension. It is long enough that people should be able to figure it out, but short enough that it won’t make the code less readable.
diff --git a/tree_sudoku.py b/tree_sudoku.py index 21a6a34..f5abef7 100644 --- a/tree_sudoku.py +++ b/tree_sudoku.py @@ -9,6 +9,10 @@ import re import copy import time + +DIM = 9 + + class SudokuSolver: def __init__(self): self.board_strings = self.import_csv() |
It might be tempting to search and replace automatically. Don’t do that. Part of the reason we are doing this one first is to get familiar with the code. You can use the search function, but make the changes by hand.
diff --git a/tree_sudoku.py b/tree_sudoku.py index 21a6a34..f456817 100644 --- a/tree_sudoku.py +++ b/tree_sudoku.py @@ -9,6 +9,10 @@ import re import copy import time + +DIM = 9 + + class SudokuSolver: def __init__(self): self.board_strings = self.import_csv() @@ -104,7 +108,7 @@ class SudokuSolver: else: return False - for a_row in range(9): + for a_row in range(DIM): number = board[a_row][column_index] if number == '0': continue @@ -150,13 +154,13 @@ class SudokuSolver: box_number += 1 box_center[1] += 3 box_center[0] += 3 - box_center[1] -= 9 + box_center[1] -= DIM return boxes def fill_board_index_table(self): return_list = [] - for row in range(9): - for column in range(9): + for row in range(DIM): + for column in range(DIM): return_list.append(str(row) + str(column)) return return_list |
Make that change and run the tests. Everything should still run.
Notice those 3s on the lines above box_center[1] -= DIM? Those are also magic numbers, and we know that there is a relationship between them and the one we just created. Sudoku puzzles have blocks of 3X3 cells. If you scale the puzzle down to 4 numbers in stead of 9, they have two blocks that are 2 X2 ins size. If you scale the puzzle up to 16 X 16, you get 4 blocks that are 4X4.
Lets call the smaller number BASIS. While we could caluculate the BASIS as the square-root of DIM, that would be a floating point operation, and we’d have float to int conversions. It is much easier, and clearer, to calculate DIM from BASIS.
Before we make this change, however, we check in our code to git. We have working code, and we don’t want to have to redo that work if we break something.
$ git status On branch master Changes not staged for commit: (use "git add <file>..." to update what will be committed) (use "git restore <file>..." to discard changes in working directory) modified: tree_sudoku.py no changes added to commit (use "git add" and/or "git commit -a") [ayoung@ayoungP40 tree_sudoku]$ git add tree_sudoku.py [ayoung@ayoungP40 tree_sudoku]$ git commit -m "introduced DIM symbolic constant" [master 653dac8] introduced DIM symbolic constant 1 file changed, 9 insertions(+), 5 deletions(-) |
The “print_board” function has a bunch of 3s in it, as well as numbers based on 3 for drawing the board. Since we don’t check that in our tests, we are not going to change this function. We only want to change things that we can test. The output will be a separate concern that we will get to once we have a better approach toward testing.
This is also the case with the “fill_box_index_table” code. This is too bad, as it is very tempting to change, but we can leave it for now. That leaves us with the trivial code change:
diff --git a/tree_sudoku.py b/tree_sudoku.py index f456817..130e935 100644 --- a/tree_sudoku.py +++ b/tree_sudoku.py @@ -10,7 +10,8 @@ import copy import time -DIM = 9 +BASIS = 3 +DIM = BASIS * BASIS class SudokuSolver: @@ -143,8 +144,8 @@ class SudokuSolver: boxes = {} box_center = [1, 1] box_number = 0 - for _row_of_boxes in range(3): - for _each_box in range(3): + for _row_of_boxes in range(BASIS): + for _each_box in range(BASIS): box_list = [] for i in range(-1, 2): box_list.append(str(box_center[0] + i) + str(box_center[1] - 1)) @@ -152,8 +153,8 @@ class SudokuSolver: box_list.append(str(box_center[0] + i) + str(box_center[1] + 1)) boxes[box_number] = box_list box_number += 1 - box_center[1] += 3 - box_center[0] += 3 + box_center[1] += BASIS + box_center[0] += BASIS box_center[1] -= DIM return boxes |
Note that the logic in this function makes use of the range from -1 to 2. This seems to be related ot the BASIS: We could change the 2 to BASIS – 1, but there seems to be more logic in this stretch that is hard coded to assume a square of size 3. We’ll leave those for now.
Run the tests and check in.
Last magic number we want to deal with is 81. This is the max number of squares in the puzzle, and we’ll modify the code to use this as MAX.
diff --git a/tree_sudoku.py b/tree_sudoku.py index 130e935..8db59ce 100644 --- a/tree_sudoku.py +++ b/tree_sudoku.py @@ -2,7 +2,7 @@ #find what values can go into what spot #create a tree trying to put in each value #if value can not be possible, end stem, go back up the tree -#retrun the branch when tree is 81 layers deep, the board is filled +#retrun the branch when tree is MAX=81 layers deep, the board is filled import csv import re @@ -12,7 +12,7 @@ import time BASIS = 3 DIM = BASIS * BASIS - +MAX = DIM * DIM class SudokuSolver: def __init__(self): @@ -29,7 +29,7 @@ class SudokuSolver: index = 0 head_node = Tree_Node(index, self.board_index_table[index]) current_node = head_node - while index < 81: + while index < MAX: current_board_filling_node = head_node test_board = copy.deepcopy(original_board) test_board[int(current_board_filling_node.board_spot[0])][int(current_board_filling_node.board_spot[1])] = current_board_filling_node.value @@ -38,7 +38,7 @@ class SudokuSolver: test_board[int(current_board_filling_node.board_spot[0])][int(current_board_filling_node.board_spot[1])] = current_board_filling_node.value if self.value_valid(test_board, int(current_node.board_spot[0]), int(current_node.board_spot[1])): index += 1 - if index >= 81: + if index >= MAX: continue new_node = Tree_Node(index, self.board_index_table[index], current_node) if test_board[int(new_node.board_spot[0])][int(new_node.board_spot[1])] != '0': |
Now that we have some simple work done, we should feel confident in our approach. Next we’ll make it a little less painful to work with out unit tests.