Sudoku Board Generator

Question

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)

• AJNeufeld: 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.)
• RootTwo: 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.
• AJNeufeld: @RootTwo You would also need to add relabelling (permutations of the numbers). However, I don’t believe this generates all possible solutions.
• Snoop2001: @AJNeufeld yes, it is Python3.x . Thank you for editing the question and tags

Answer 1

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):
 col.add(grid[k][j]) # Set needs add instead of append
 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.