5
\$\begingroup\$

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)
\$\endgroup\$
4
  • 3
    \$\begingroup\$ 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.) \$\endgroup\$
    – AJNeufeld
    Commented Dec 20, 2019 at 22:52
  • \$\begingroup\$ 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. \$\endgroup\$
    – RootTwo
    Commented Dec 21, 2019 at 0:37
  • \$\begingroup\$ @RootTwo You would also need to add relabelling (permutations of the numbers). However, I don’t believe this generates all possible solutions. \$\endgroup\$
    – AJNeufeld
    Commented Dec 21, 2019 at 4:54
  • \$\begingroup\$ @AJNeufeld yes, it is Python3.x . Thank you for editing the question and tags \$\endgroup\$
    – Snoop2001
    Commented Dec 22, 2019 at 3:18

1 Answer 1

5
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.