Sudoku Board Generator

I am working on a Sudoku board generator that generators a valid complete Sudoku board.

My algorithm generates a valid board, but the runtime is variable. Time varies from ~0.2 to 8 seconds. Ideally, I would like to get it to < 1 second consistently.

The logic part of the algorithm is what is taking the longest. It has to ensure each 3x3 square has unique numbers 1-9, and it has to ensure each column has unique numbers 1-9. If it does not, the algorithm randomly chooses another permutation to use and then tries again.

If someone could provide me with optimization tips, that would be very helpful. Thank you!

NUM_ROWS = 9
NUM_COLS = 9

def fill_grid(grid):
# get all permutations for 1-9
all_permutes = list(itertools.permutations([1,2,3,4,5,6,7,8,9], r=9))

# append one permutation to each row
for i in range(NUM_ROWS):

"""
get lists for all the columns and squares

to help check for a valid board
"""
# make each current column into list
curr_col_set = []
for j in range(NUM_COLS):
col = []
for k in range(NUM_ROWS):
col.append(grid[k][j])
curr_col_set.append(col)

# make each current square into list
curr_square_set = []
for j in range(0, NUM_ROWS, 3):
for k in range(0, NUM_COLS, 3):
square = []
for l in range(j, j+3):
for m in range(k, k+3):
square.append(grid[m][l])
curr_square_set.append(square)

"""
use logic to ensure each row results in valid board
"""
allowed = False
while not allowed:
allowed = True
choice = random.choice(all_permutes)
for j in range(len(choice)):
if choice[j] not in set(curr_col_set[j]): # ensure digit isn't in col
if i < 3: # ensure digit isn't in square
if j < 3:
if choice[j] in curr_square_set[0]:
allowed = False
break
elif j < 6:
if choice[j] in curr_square_set[3]:
allowed = False
break
elif j < 9:
if choice[j] in curr_square_set[6]:
allowed = False
break
elif i < 6:
if j < 3:
if choice[j] in curr_square_set[1]:
allowed = False
break
elif j < 6:
if choice[j] in curr_square_set[4]:
allowed = False
break
elif j < 9:
if choice[j] in curr_square_set[7]:
allowed = False
break
elif i < 9:
if j < 3:
if choice[j] in curr_square_set[2]:
allowed = False
break
elif j < 6:
if choice[j] in curr_square_set[5]:
allowed = False
break
elif j < 9:
if choice[j] in curr_square_set[8]:
allowed = False
break

else:
allowed = False
break

all_permutes.remove(choice) # remove the row from all_permutes
grid[i] = choice # add row to board

return grid

grid = [[0 for i in range(NUM_COLS)] for i in range(NUM_ROWS)] # 9x9 grid of 0's
grid = fill_grid(grid)
• You code is not formatted properly: fill_grid() seems to be indented when it should not be. Also, you're missing imports. I've edited the tags to say you are using Python; can you confirm it is Python-3.x? Also, the title shouldn't say "Optimizing" because that is not what the code does; the title should describe the what the code does, not the goal of posting the question (everyone posting on Code Review wants code optimized, clarified, simplified etc; stating it is not helpful.) Dec 20, 2019 at 22:52
• I seem to recall that one valid board can be turned into other valid boards by swapping rows/cols within a set of 3, or by swapping a set of 3 rows/cols with another set of 3 rows/cols. That might make a faster routine, or one that runs in a fixed time. Dec 21, 2019 at 0:37
• @RootTwo You would also need to add relabelling (permutations of the numbers). However, I don’t believe this generates all possible solutions. Dec 21, 2019 at 4:54
• @AJNeufeld yes, it is Python3.x . Thank you for editing the question and tags Dec 22, 2019 at 3:18

Repeated set() construction

allowed = False
while not allowed:
allowed = True
choice = random.choice(all_permutes)
for j in range(len(choice)):
if choice[j] not in set(curr_col_set[j]): # ensure digit isn't in col

Consider the 7th, 8th or 9th row. You are grabbing a random permutation, and checking to see if choice[j] is in set(curr_col_set[j]) for each column j. How many times is set(curr_col_set[j]) being constructed? Once for each random row permutation?

Maybe you could construct it exactly once:

curr_col_set = []
for j in range(NUM_COLS):
col = set()                        # Set, instead of list
for k in range(NUM_ROWS):
curr_col_set.append(col)

And then you can remove the set construction out of this line:

if choice[j] not in curr_col_set[j]: # ensure digit isn't in col

The code now runs a little faster.

Note that with list comprehension, we can reduce the code for the set generation, and speed it up slightly in the process:

curr_col_set = []
for j in range(NUM_COLS):
col = set(grid[k][j] for k in range(NUM_ROWS))
curr_col_set.append(col)

Or even further:

curr_col_set = [set(grid[k][j] for k in range(NUM_ROWS)) for j in range(NUM_COLS)]

Do the equivalent to the curr_square_set to speed up the choice[j] in curr_square_set[ ] calls.

Reducing the Search Space

When your algorithm starts, all_permutes has 362880 entries. After you pick the first row, you remove that row, so the search space reduces by one, to 362879. Not a huge reduction.

However, when you pick a row, that locks in digits which cannot appear again in those respective columns. If you removed all rows where any digit matches a digit in the current choice selection, you'd significantly reduce the search space, and remove the possibility of randomly selecting those rows which can't possibly work. Moreover, you wouldn't need to keep track of the curr_col_set, because you'd be guaranteed not to select a row where a duplicate digit appears in the column because those possibilities no longer exist.

So, remove the curr_col_set construction code, and the if ...: else: statement involving it, and replace:

all_permutes.remove(choice) # remove the row from all_permutes

with:

# Remove all row permutations where any column digit matches the current one.
all_permutes = [ row for row in all_permutes if all(x != y for x, y in zip(row, choice))]

With this change, all_permutes drops from 362880 to 133496, then to 43412, then to 12040, 2742, 488, 52, 2, and finally to 1 as the 9 rows are generated.