Sudoku with Python and Sets — Part Four
This will be the final article in the Sudoku with Python and Sets series. Awwww!
It’s alright though. It will be a good one.
Review
To get us started, I want to look back to the previous article and make an improvement to it. This helps remember where we left off, along with practicing our development mindset.
In Part 3, we created a function called check_cells(possible_area, n_in_pair) to find n_in_pair numbers that could only fit in n_in_pair cells within a row, column, or subgrid. This technique significantly reduced the possible values for these cells. However, our initial implementation had a limitation: it only removed the identified pair from other cells, but did not refine the possibilities within the paired cells themselves.
Let’s come up with an even better way to write our old function to meet our new needs.
def check_cells(possible_area,n_in_pair):
#Get the shape to adjust it if it is a grid later
possible_shape = possible_area.shape
possible_area = possible_area.flatten()
#Create a list of lists, with the combinations of possible numbers for each cell index
pairs_list = [[tuple(sorted(t)) for t in create_pairs(s, n_in_pair)] for s in possible_area]
#Find cells that only have one possible pair in their pairs_list
one_possible_pair = [p for p in pairs_list if len(p) == 1]
#If the possible pair of size n_in_pair only shows up n_in_pair times, then
#remove that pair from all other cells
how_many = Counter(sum(one_possible_pair,[]))
for k,v in how_many.items():
if v == n_in_pair:
for n,p in enumerate(pairs_list):
if [k] != p:
possible_area[n] = possible_area[n].difference(set(k))
else:
possible_area[n] = set(k)
return possible_area.reshape(possible_shape)First, we need to flatten the shape of our input, so this can work on rows and columns, along with subgrids. Then, we create a list of the possible pairs for each cell.
#Get the shape to adjust it if it is a grid later
possible_shape = possible_area.shape
possible_area = possible_area.flatten()
#Create a list of lists, with the combinations of possible numbers for each cell index
pairs_list = [[tuple(sorted(t)) for t in create_pairs(s, n_in_pair)] for s in possible_area]Next, we find possible pairs from cells that only have one pair. If we count how many times each pair appears, and it matches the number of items that are within each pair, then we found the n_in_pair cells that can contain n_in_pair possible values.
#Find cells that only have one possible pair in their pairs_list
one_possible_pair = [p for p in pairs_list if len(p) == 1]
#If the possible pair of size n_in_pair only shows up n_in_pair times, then
#remove that pair from all other cells
how_many = Counter(sum(one_possible_pair,[]))After finding them, let’s loop through each cell and difference the pair from all cells except the ones we identified.
for k,v in how_many.items():
if v == n_in_pair:
for n,p in enumerate(pairs_list):
if [k] != p:
possible_area[n] = possible_area[n].difference(set(k))
else:
possible_area[n] = set(k)Boom. Simpler function created.
Now, let’s move onto a new strategy, which I will explain through sets.
Where Rows and Subgrids Meet
Suppose we are looking at a row and a subgrid combined (Fig. 1):
We know that every row must contain 1 through 9, and every subgrid the same. So:
A ∪ B ∪ C = {1,2,3,4,5,6,7,8,9}
We also know that the rows in the subgrid are equal to:
Set 1 ∪ Set 2 ∪ Set 3 = {1,2,3,4,5,6,7,8,9}
Let’s set (haha, get it!) these equal to each other since they contain the same values:
A ∪ B ∪ C = Set 1 ∪ Set 2 ∪ Set 3
One of the things that we notice is that Set 1 and A are equal to each other, so since no repeating values can repeat, and these two sets are equal, then we can difference them from both sides:
(A ∪ B ∪ C) \ A = (Set 1 ∪ Set 2 ∪ Set 3) \ A
B ∪ C = Set 2 ∪ Set 3
Lets look at that in pictorial form to make sense of it (Fig. 2):
We know that these boxes are going to contain the same values. For example, if there is a 6 in B or C, then there will be a 6 in subgrid Set 2 or Set 3.
We can take this a step further. Let’s say that we know a possible pair in a column can only fit inside a single subgrid (Fig. 3). For example:
If we knew that 5 and 6 could only fit in two cells in the row, and both of those cells happened to be in the same subgrid, then we could remove 5 and 6 from all other cells in the subgrid, that are not in the same row. So {6,8} would change to {8}, {5,7} to {7}, and {4,5} to {4}. We can see how useful this would be for solving, especially when coupled with our previous strategy for pairs.
Let’s implement it!
Implementation
First, let’s get a row, and find out all the unique possible numbers. We can make a dictionary, where the keys are these numbers.
temp = possible_board[row_num,:]
#Get all the unique possible numbers and make them keys in a dictionary.
# Make the values empty lists.
unique_possible = sum([[i for i in v] for v in temp],[])
which_subgrids = {num:[] for num in unique_possible}For the values, let’s find which subgrid each value is contained in, and if we can only find the values in a single subgrid, then we know it has to be in there.
for num in unique_possible:
#Go through which subgrid the values from the column are in
for subgrid in range(3):
#Combine all the values at the intersection of the column and a subgrid into one list
eval_temp = temp[subgrid*3:subgrid*3+3]
eval_temp = sum([[i for i in v] for v in eval_temp],[])
#Add the index of the subgrid to the dictionary list value
# if the number is in the subgrid
if num in eval_temp:
which_subgrids[num].append(subgrid)If there is only one subgrid for the number, then let’s index that subgrid on our possible values board. Similar to before, where we broke the subgrid into Set 1, Set 2, and Set 3, we can get the sets that are not part of our row, and discard the paired possible numbers from these.
#Only get unique subgrid indexes so they do not repeat
which_subgrids = {num: np.unique(v) for num,v in which_subgrids.items()}
#If there is only one subgrid that the number can go in
for k,v in {num: v[0] for num,v in which_subgrids.items() if len(v) == 1}.items():
#get the full subgrid that the column intersects
grid_look = possible_board[(row_num // 3)*3:(row_num // 3)*3+3,v*3:v*3+3].copy()
#Remove the column from the subgrid
removed_row = grid_look[(row_num % 3),:]
fixed = np.delete(grid_look, (row_num % 3), axis=0)
#For the other columns in the subgrid, discard the value that appears
# in the segment of the column we are looking at
for row in fixed:
for item in row:
if isinstance(item, set):
item.discard(k)
#recombine the columns to create the full subgrid. Set this as the subgrid for possible values
result = np.insert(fixed, (row_num % 3), removed_row, axis=0)
if (result != possible_board[(row_num // 3)*3:(row_num // 3)*3+3,v*3:v*3+3]).any():
possible_board[(row_num // 3)*3:(row_num // 3)*3+3,v*3:v*3+3] = resultGreat! We can repeat this same logic for columns. Here are the row and column functions:
def check_row_in_subgrid(board,possible_board):
can_update = False
for row_num in range(9):
temp = possible_board[row_num,:]
#Get all the unique possible numbers and make them keys in a dictionary. Make the values empty lists.
unique_possible = sum([[i for i in v] for v in temp],[])
which_subgrids = {num:[] for num in unique_possible}
#For each number
for num in unique_possible:
#Go through which subgrid the values from the column are in
for subgrid in range(3):
#Combine all the values at the intersection of the column and a subgrid into one list
eval_temp = temp[subgrid*3:subgrid*3+3]
eval_temp = sum([[i for i in v] for v in eval_temp],[])
#Add the index of the subgrid to the dictionary list value if the number is in the subgrid
if num in eval_temp:
which_subgrids[num].append(subgrid)
#Only get unique subgrid indexes so they do not repeat
which_subgrids = {num: np.unique(v) for num,v in which_subgrids.items()}
#If there is only one subgrid that the number can go in
for k,v in {num: v[0] for num,v in which_subgrids.items() if len(v) == 1}.items():
#get the full subgrid that the column intersects
grid_look = possible_board[(row_num // 3)*3:(row_num // 3)*3+3,v*3:v*3+3].copy()
#Remove the column from the subgrid
removed_row = grid_look[(row_num % 3),:]
fixed = np.delete(grid_look, (row_num % 3), axis=0)
#For the other columns in the subgrid, discard the value that appears in the segment of the column we are looking at
for row in fixed:
for item in row:
if isinstance(item, set):
item.discard(k)
#recombine the columns to create the full subgrid. Set this as the subgrid for possible values
result = np.insert(fixed, (row_num % 3), removed_row, axis=0)
if (result != possible_board[(row_num // 3)*3:(row_num // 3)*3+3,v*3:v*3+3]).any():
possible_board[(row_num // 3)*3:(row_num // 3)*3+3,v*3:v*3+3] = result
can_update = True
def check_col_in_subgrid(board,possible_board):
can_update = False
for col_num in range(9):
temp = possible_board[:,col_num].copy()
#Get all the unique possible numbers and make them keys in a dictionary. Make the values empty lists.
unique_possible = sum([[i for i in v] for v in temp],[])
which_subgrids = {num:[] for num in unique_possible}
#For each number
for num in unique_possible:
#Go through which subgrid the values from the column are in
for subgrid in range(3):
#Combine all the values at the intersection of the column and a subgrid into one list
eval_temp = temp[subgrid*3:subgrid*3+3]
eval_temp = sum([[i for i in v] for v in eval_temp],[])
#Add the index of the subgrid to the dictionary list value if the number is in the subgrid
if num in eval_temp:
which_subgrids[num].append(subgrid)
#Only get unique subgrid indexes so they do not repeat
which_subgrids = {num: np.unique(v) for num,v in which_subgrids.items()}
#If there is only one subgrid that the number can go in
for k,v in {num: v[0] for num,v in which_subgrids.items() if len(v) == 1}.items():
#get the full subgrid that the column intersects
grid_look = possible_board[v*3:v*3+3,(col_num // 3)*3:(col_num // 3)*3+3].copy()
#Remove the column from the subgrid
removed_col = grid_look[:, (col_num % 3)]
fixed = np.delete(grid_look, (col_num % 3), axis=1)
#For the other columns in the subgrid, discard the value that appears in the segment of the column we are looking at
for row in fixed:
for item in row:
if isinstance(item, set):
item.discard(k)
#recombine the columns to create the full subgrid. Set this as the subgrid for possible values
result = np.insert(fixed, (col_num % 3), removed_col, axis=1)
if (possible_board[v*3:v*3+3,(col_num // 3)*3:(col_num // 3)*3+3] != result).any():
# print(result)
# print(possible_board[v*3:v*3+3,(col_num // 3)*3:(col_num // 3)*3+3])
possible_board[v*3:v*3+3,(col_num // 3)*3:(col_num // 3)*3+3] = result
can_update = True When we put this all back into our original solver function, we can run it:
def solve_sudoku(board,possible_board):
can_update = True
#While we can update our grid
while can_update:
#Update the possible values in the grid
can_update = update_possible_values(board, possible_board)
#If nothing was updated in the previous step
if not can_update:
can_update = place_unique_row(board, possible_board)
#If nothing was updated in the previous step
if not can_update:
can_update = place_unique_col(board, possible_board)
#If nothing was updated in the previous step
if not can_update:
can_update = place_unique_subgrid(board, possible_board)
#########################
# UPDATED NEW BELOW HERE#
#########################
#Iterate through columns
if not can_update:
#Let's check pairings of 2, 3 to start
for n_in_pair in range(2,4):
for i in range(9):
#Get the area we are looking at
check = possible_board[:,i]
#If any values on the possible_board changed with our function, then update possible_board
if (check_cells(check,n_in_pair) != check).any():
possible_board[:,i] = check_cells(check,n_in_pair)
can_update = True
#Iterate through rows
if not can_update:
for n_in_pair in range(2,4):
for i in range(9):
check = possible_board[i,:]
if (check_cells(check,n_in_pair) != check).any():
possible_board[i,:] = check_cells(check,n_in_pair)
can_update = True
#Iterate through subgrids
if not can_update:
for n_in_pair in range(2,4):
for grid_row in range(3):
for grid_col in range(3):
gx, gy = grid_row * 3, grid_col * 3
check = possible_board[gx:gx + 3,gy:gy + 3]
if (check_cells(check,n_in_pair) != check).any():
possible_board[gx:gx + 3,gy:gy + 3] = check_cells(check,n_in_pair)
can_update = True
############################
# COMPLETELY NEW BELOW HERE#
############################
if not can_update:
check_col_in_subgrid(board,possible_board)
if not can_update:
check_row_in_subgrid(board,possible_board)
return boardAnd see our results:
board = np.array([
[0, 0, 0, 0, 1, 0, 0, 3, 0],
[0, 0, 9, 0, 0, 5, 0, 0, 8],
[8, 0, 4, 0, 0, 6, 0, 2, 5],
[0, 0, 0, 0, 0, 0, 6, 0, 0],
[0, 0, 8, 0, 0, 4, 0, 0, 0],
[1, 2, 0, 0, 8, 7, 0, 0, 0],
[3, 0, 0, 9, 0, 0, 2, 0, 0],
[0, 6, 5, 0, 0, 8, 0, 0, 0],
[9, 0, 0, 0, 0, 0, 0, 0, 0]])
solve_sudoku(board,possible_board) #You may have to run this a few timesarray([[7, 5, 2, 8, 1, 9, 4, 3, 6],
[6, 3, 9, 2, 4, 5, 7, 1, 8],
[8, 1, 4, 7, 3, 6, 9, 2, 5],
[4, 7, 3, 5, 9, 2, 6, 8, 1],
[5, 9, 8, 1, 6, 4, 3, 7, 2],
[1, 2, 6, 3, 8, 7, 5, 4, 9],
[3, 8, 7, 9, 5, 1, 2, 6, 4],
[2, 6, 5, 4, 7, 8, 1, 9, 3],
[9, 4, 1, 6, 2, 3, 8, 5, 7]])It looks like we completed another grid!
Series Closing Remarks
I want to end the article series here. I understand there are many advanced sudoku techniques that can assist you even further, but I think it is fun to leave those to you all to continue your learning.
I hope you enjoyed playing the game in Python, along with thinking about the strategies in a new and thoughtful way. If you did, and you liked my writing, check out some of my other articles!
Link to Github.
If you like my articles, keep reading. For me to continue writing though, I need fuel…and my tank runs on hot lattes!
