 realpython.com Go back Open original

Python Practice Problems: Get Ready for Your Next Interview – Real Python

By Real Python

This is a larger and more complex problem than you’ve looked at so far in this tutorial. You’ll walk through the problem step by step, ending with a recursive function that solves the puzzle. Here’s a rough outline of the steps you’ll take:

• Read the puzzle into a grid form.
• For each cell:
• For each possible number in that cell:
• Place the number in the cell.
• Remove that number from the row, column, and small square.
• Move to the next position.
• If no possible numbers remain, then declare the puzzle unsolvable.
• If all cells are filled, then return the solution.

The tricky part of this algorithm is keeping track of the grid at each step of the process. You’ll use recursion, making a new copy of the grid at each level of the recursion, to maintain this information.

With that outline in mind, let’s start with the first step, creating the grid.

Generating a Grid From a Line#

To start, it’s helpful to convert the puzzle data into a more usable format. Even if you eventually want to solve the puzzle in the given SDM format, you’ll likely make faster progress working through the details of your algorithm with the data in a grid form. Once you have a solution that works, then you can convert it to work on a different data structure.

1 # sudokusolve.py
2 def line_to_grid(values):
3  grid = []
4  line = []
5  for index, char in enumerate(values):
6  if index and index % 9 == 0:
7  grid.append(line)
8  line = []
9  line.append(int(char))
10  # Add the final line
11  grid.append(line)
12  return grid
13
14 def grid_to_line(grid):
15  line = ""
16  for row in grid:
17  r = "".join(str(x) for x in row)
18  line += r
19  return line

Your first function, line_to_grid(), converts the data from a single string of eighty-one digits to a list of lists. For example, it converts the string line to a grid like start:

line = "0040060790000006020560923000780...90007410920105000000840600100"
start = [ [ 0, 0, 4, 0, 0, 6, 0, 7, 9], [ 0, 0, 0, 0, 0, 0, 6, 0, 2], [ 0, 5, 6, 0, 9, 2, 3, 0, 0], [ 0, 7, 8, 0, 6, 1, 0, 3, 0], [ 5, 0, 9, 0, 0, 0, 4, 0, 6], [ 0, 2, 0, 5, 4, 0, 8, 9, 0], [ 0, 0, 7, 4, 1, 0, 9, 2, 0], [ 1, 0, 5, 0, 0, 0, 0, 0, 0], [ 8, 4, 0, 6, 0, 0, 1, 0, 0],
]

Each inner list here represents a horizontal row in your sudoku puzzle.

You start with an empty grid and an empty line. You then build each line by converting nine characters from the values string to single-digit integers and then appending them to the current line. Once you have nine values in a line, as indicated by index % 9 == 0 on line 7, you insert that line into the grid and start a new one.

The function ends by appending the final line to the grid. You need this because the for loop will end with the last line still stored in the local variable and not yet appended to grid.

The inverse function, grid_to_line(), is slightly shorter. It uses a generator expression with .join() to create a nine-digit string for each row. It then appends that string to the overall line and returns it. Note that it’s possible to use nested generators to create this result in fewer lines of code, but the readability of the solution starts to fall off dramatically.

Now that you’ve got the data in the data structure you want, let’s start working with it.

Generating a Small Square Iterator#

Your next function is a generator that will help you search for the smaller three-by-three square a given position is in. Given the x- and y-coordinates of the cell in question, this generator will produce a list of coordinates that match the square that contains it:

In the image above, you’re examining cell (3, 1), so your generator will produce coordinate pairs corresponding to all the lightly shaded cells, skipping the coordinates that were passed in:

(3, 0), (4, 0), (5, 0), (4, 1), (5, 1), (3, 2), (4, 2), (5, 2)

Putting the logic for determining this small square in a separate utility function keeps the flow of your other functions more readable. Making this a generator allows you to use it in a for loop to iterate through each of the values.

The function to do this involves using the limitations of integer math:

# sudokusolve.py
def small_square(x, y): upperX = ((x + 3) // 3) * 3 upperY = ((y + 3) // 3) * 3 lowerX = upperX - 3 lowerY = upperY - 3 for subX in range(lowerX, upperX): for subY in range(lowerY, upperY): # If subX != x or subY != y: if not (subX == x and subY == y): yield subX, subY

There are a lot of threes in a couple of those lines, which makes lines like ((x + 3) // 3) * 3 look confusing. Here’s what happens when x is 1.

>>>
>>> x = 1
>>> x + 3
4
>>> (x + 3) // 3
1
>>> ((x + 3) // 3) * 3
3

Using the rounding of integer math allows you to get the next-highest multiple of three above a given value. Once you have this, subtracting three will give you the multiple of three below the given number.

There are a few more low-level utility functions to examine before you start building on top of them.

Moving to the Next Spot#

Your solution will need to walk through the grid structure one cell at a time. This means that at some point, you’ll need to figure out what the next position should be. compute_next_position() to the rescue!

compute_next_position() takes the current x- and y-coordinates as input and returns a tuple containing a finished flag along with the x- and y-coordinates of the next position:

# sudokusolve.py
def compute_next_position(x, y): nextY = y nextX = (x + 1) % 9 if nextX < x: nextY = (y + 1) % 9 if nextY < y: return (True, 0, 0) return (False, nextX, nextY)

The finished flag tells the caller that the algorithm has walked off the end of the puzzle and has completed all the squares. You’ll see how that’s used in a later section.

Removing Impossible Numbers#

Your final low-level utility is quite small. It takes an integer value and an iterable. If the value is nonzero and appears in the iterable, then the function removes it from the iterable:

# sudokusolve.py
def test_and_remove(value, possible): if value != 0 and value in possible: possible.remove(value)

Typically, you wouldn’t make this small bit of functionality into a function. You’ll use this function several times, though, so it’s best to follow the DRY principle and pull it up to a function.

Now you’ve seen the bottom level of the functionality pyramid. It’s time to step up and use those tools to build a more complex function. You’re almost ready to solve the puzzle!

Finding What’s Possible#

Your next function makes use of some of the low-level functions you’ve just walked through. Given a grid and a position on that grid, it determines what values that position could still have:

For the grid above, at the position (3, 1), the possible values are [1, 5, 8] because the other values are all present, either in that row or column or in the small square you looked at earlier.

This is the responsibility of detect_possible():

# sudokusolve.py
def detect_possible(grid, x, y): if grid[x][y]: return [grid[x][y]] possible = set(range(1, 10)) # Test horizontal and vertical for index in range(9): if index != y: test_and_remove(grid[x][index], possible) if index != x: test_and_remove(grid[index][y], possible) # Test in small square for subX, subY in small_square(x, y): test_and_remove(grid[subX][subY], possible) return list(possible)

The function starts by checking if the given position at x and y already has a nonzero value. If so, then that’s the only possible value and it returns.

If not, then the function creates a set of the numbers one through nine. The function proceeds to check different blocking numbers and removes those from this set.

It starts by checking the column and row of the given position. This can be done with a single loop by just alternating which subscript changes. grid[x][index] checks values in the same column, while grid[index][y] checks those values in the same row. You can see that you’re using test_and_remove() here to simplify the code.

Once those values have been removed from your possible set, the function moves on to the small square. This is where the small_square() generator you created before comes in handy. You can use it to iterate over each position in the small square, again using test_and_remove() to eliminate any known values from your possible list.

Once all the known blocking values have been removed from your set, you have the list of all possible values for that position on that grid.

You might wonder why the code and its description make a point about the position being “on that grid.” In your next function, you’ll see that the program makes many copies of the grid as it tries to solve it.

Solving It#

You’ve reached the heart of this solution: solve()! This function is recursive, so a little up-front explanation might help.

The general design of solve() is based on testing a single position at a time. For the position of interest, the algorithm gets the list of possible values and then selects those values, one at a time, to be in this position.

For each of these values, it creates a grid with the guessed value in this position. It then calls a function to test for a solution, passing in the new grid and the next position.

It just so happens that the function it calls is itself.

For any recursion, you need a termination condition. This algorithm has four of them:

1. There are no possible values for this position. That indicates the solution it’s testing can’t work.
2. It’s walked to the end of the grid and found a possible value for each position. The puzzle is solved!
3. One of the guesses at this position, when passed back to the solver, returns a solution.
4. It’s tried all possible values at this position and none of them will work.

Let’s look at the code for this and see how it all plays out:

# sudokusolve.py
import copy def solve(start, x, y): temp = copy.deepcopy(start) while True: possible = detect_possible(temp, x, y) if not possible: return False finished, nextX, nextY = compute_next_position(x, y) if finished: temp[x][y] = possible return temp if len(possible) > 1: break temp[x][y] = possible x = nextX y = nextY for guess in possible: temp[x][y] = guess result = solve(temp, nextX, nextY) if result: return result return False

The first thing to note in this function is that it makes a .deepcopy() of the grid. It does a deep copy because the algorithm needs to keep track of exactly where it was at any point in the recursion. If the function made only a shallow copy, then every recursive version of this function would use the same grid.

Once the grid is copied, solve() can work with the new copy, temp. A position on the grid was passed in, so that’s the number that this version of the function will solve. The first step is to see what values are possible in this position. As you saw earlier, detect_possible() returns a list of possible values that may be empty.

If there are no possible values, then you’ve hit the first termination condition for the recursion. The function returns False, and the calling routine moves on.

If there are possible values, then you need to move on and see if any of them is a solution. Before you do that, you can add a little optimization to the code. If there’s only a single possible value, then you can insert that value and move on to the next position. The solution shown does this in a loop, so you can place multiple numbers into the grid without having to recur.

This may seem like a small improvement, and I’ll admit my first implementation did not include this. But some testing showed that this solution was dramatically faster than simply recurring here at the price of more complex code.

Note: This is an excellent point to bring up during an interview even if you don’t add the code to do this. Showing them that you’re thinking about trading off speed against complexity is a strong positive signal to interviewers.

Sometimes, of course, there will be multiple possible values for the current position, and you’ll need to decide if any of them will lead to a solution. Fortunately, you’ve already determined the next position in the grid, so you can forgo placing the possible values.

If the next position is off the end of the grid, then the current position is the final one to fill. If you know that there’s at least one possible value for this position, then you’ve found a solution! The current position is filled in and the completed grid is returned up to the calling function.

If the next position is still on the grid, then you loop through each possible value for the current spot, filling in the guess at the current position and then calling solve() with the temp grid and the new position to test.

solve() can return only a completed grid or False, so if any of the possible guesses returns a result that isn’t False, then a result has been found, and that grid can be returned up the stack.

If all possible guesses have been made and none of them is a solution, then the grid that was passed in is unsolvable. If this is the top-level call, then that means the puzzle is unsolvable. If the call is lower in the recursion tree, then it just means that this branch of the recursion tree isn’t viable.

Putting It All Together#

At this point, you’re almost through the solution. There’s only one final function left, sudoku_solve():

# sudokusolve.py
def sudoku_solve(input_string): grid = line_to_grid(input_string) answer = solve(grid, 0, 0) if answer: return grid_to_line(answer) else: return "Unsolvable"

This function does three things:

1. Converts the input string into a grid
2. Calls solve() with that grid to get a solution
3. Returns the solution as a string or "Unsolvable" if there’s no solution

That’s it! You’ve walked through a solution for the sudoku solver problem.

Interview Discussion Topics

The sudoku solver solution you just walked through is a good deal of code for an interview situation. Part of an interview process would likely be to discuss some of the code and, more importantly, some of the design trade-offs you made. Let’s look at a few of those trade-offs.

Recursion

The biggest design decision revolves around using recursion. It’s possible to write a non-recursive solution to any problem that has a recursive solution. Why choose recursion over another option?

This is a discussion that depends not only on the problem but also on the developers involved in writing and maintaining the solution. Some problems lend themselves to rather clean recursive solutions, and some don’t.

In general, recursive solutions will take more time to run and use more memory than non-recursive solutions. But that’s not always true and, more importantly, it’s not always important.

Similarly, some teams of developers are comfortable with recursive solutions, while others find them exotic or unnecessarily complex. Maintainability should play into your design decisions as well.

One good discussion to have about a decision like this is around performance. How fast does this solution need to execute? Will it be used to solve billions of puzzles or just a handful? Will it run on a small embedded system with memory constraints, or will it be on a large server?

These external factors can help you decide which is a better design decision. These are great topics to bring up in an interview as you’re working through a problem or discussing code. A single product might have places where performance is critical (doing ray tracing on a graphics algorithm, for example) and places where it doesn’t matter at all (such as parsing the version number during installation).

Bringing up topics like this during an interview shows that you’re not only thinking about solving an abstract problem, but you’re also willing and able to take it to the next level and solve a specific problem facing the team.

Sometimes it’s worth picking a solution that’s slower in order to make a solution that’s easier to work with, debug, and extend. The decision in the sudoku solver challenge to convert the data structure to a grid is one of those decisions.

That design decision likely slows down the program, but unless you’ve measured, you don’t know. Even if it does, putting the data structure into a form that’s natural for the problem can make the code easier to comprehend.

It’s entirely possible to write a solver that operates on the linear strings you’re given as input. It’s likely faster and probably takes less memory, but small_square(), among others, will be a lot harder to write, read, and maintain in this version.

Missteps

Another thing to discuss with an interviewer, whether you’re live coding or discussing code you wrote offline, is the mistakes and false turns you took along the way.

This is a little less obvious and can be slightly detrimental, but particularly if you’re live coding, taking a step to refactor code that isn’t right or could be better can show how you work. Few developers can write perfect code the first time. Heck, few developers can write good code the first time.

Good developers write the code, then go back and refactor it and fix it. For example, my first implementation of detect_possible() looked like this:

# sudokusolve.py
def first_detect_possible(x, y, grid): print(f"position [{x}][{y}] = {grid[x][y]}") possible = set(range(1, 10)) # Test horizontal for index, value in enumerate(grid[x]): if index != y: if grid[x][index] != 0: possible.remove(grid[x][index]) # Test vertical for index, row in enumerate(grid): if index != x: if grid[index][y] != 0: possible.remove(grid[index][y]) print(possible)

Ignoring that it doesn’t consider the small_square() information, this code can be improved. If you compare this to the final version of detect_possible() above, you’ll see that the final version uses a single loop to test both the horizontal and the vertical dimensions.

Wrapping Up

That’s your tour through a sudoku solver solution. There’s more information available on formats for storing puzzles and a huge list of sudoku puzzles you can test your algorithm on.