Gotta Comprehend ’Em All! Sudoku verifier done easy in Python
At Digital Frontiers we all have our favourite languages. The other day we were arguing about advantages and shortcomings of some specific ones and decided to have a closer look at them, using a Sudoku verifier as common example. If you are also interested in other programming languages, here is a collection of links to the other blog posts in our series:
- Featuring C: The slightly bumpy road to Sudoku verifier in C
- Featuring Java: (yet to be published)
- Featuring Kotlin: (yet to be published)
- Featuring Rust: (yet to be published)
- Featuring Haskell: (yet to be published)
Today, let’s talk about: Python!
With a background of only statically-typed programming languages, learning and using Python definitively required some time to familiarise with the language back then. But the beauty of Python catches you faster than you might realise. And you will rapidly fall in love with the simple and concise syntax, the user-friendly data structures and the extensive library support.
With a small example I would like to show you some of the concepts I like so much about Python.
The problem: Verifying sudokus
This blog post is part of a series that illustrates the advantages and disadvantages of the respective programming language. A Sudoku verifier serves as our reference project.
Python is well prepared for this task and there are plenty of ways to implement that in Python. The intriguing question is just: What is the unique selling point of Python? There must be some elegant and concise solution that would barely be possible in other languages, if at all.
If I had to enumerate my favourite features Python, they would be list comprehensions, generators and the overall iterable/iterator construct. These are extremely powerful tools that set Python apart from other languages. For this reason my implementation concentrates upon using them.
If you’d already like to take a quick peek inside, you can find the code on our GitHub: https://github.com/dxfrontiers/sudoku_verifier_python
Getting solvable Sudokus
However, before digging into the details of my solution, there is some question to solve: Where do I get correct Sudoku puzzles for my verifier?
Well, how about generating the puzzles ourselves and feeding them to our verifier? This way we’re not dependent on some external representation we would have to parse first.
I then stumbled over this implementation that translates Sudoku puzzles into the exact cover problem, which is then solved instead.
Sudoku using ‘exact cover’ solver: https://codereview.stackexchange.com/q/37415
Working with the generated Sudoku puzzles is simple and straightforward. A puzzle is randomly generated and solved if a solution exists. Afterwards we’re converting the solution into a format we can easily work with, a list of lists of ints.
from sudoku import make_puzzle, solve, puzzle_to_grid_altpuzzle = make_puzzle()
solution = solve(puzzle)
sudoku_grid = puzzle_to_grid_alt(solution)print(f"Is solvable: {check_sudoku(sudoku_grid)}")
The check_sudoku function is our contribution to the whole, accepting the list of lists of ints and verifying, whether the Sudoku solution is correct.
An exemplary puzzle could look like this:
print(f"Puzzle:\n{puzzle}")Puzzle:
.....5163
9...6.48.
....7....
.....39.6
.43...52.
1.92.....
....8....
.92.1...5
5764.....
While the solution for this puzzle would be:
print(f"Solution:\n{solution}")Solution:
487925163
925361487
631874259
258743916
743196528
169258734
314589672
892617345
576432891
Enough talk… now get to the code!
So, we have everything set up. We are bootstrapping the Sudoku puzzles to verify in our code. What’s missing is the implementation of the verifier. I chose a naive approach of checking, whether
- each row,
- each column,
- and each of the nine 3x3 subgrids
contain all of the digits from 1 to 9. By rearranging columns and subgrids as rows, we can reuse the verify_line function for those three checks:
def verify_line(line):
return len(line) == 9 and sum(line) == sum(set(line))Pretty straightforward and self-explanatory, I would say.
Let’s move on to the logic for rearranging the grid, which is the more exciting part of the implementation:
We’re extensively using list comprehensions here, which makes the code very concise. List comprehensions provide a succinct way to create lists, typically by making new lists where each element is the result of some operations applied to each item of another list.
First, the rows are passed to our verifier function and we collect all rows that violate the predicate verify_line(row). In order to verify the columns, we’re transposing the Sudoku grid, so that rows become columns and vice versa. The transposed grid shares the same structure as its origin.
The zip(*grid) unpacks the grid as iterators. The zip function iterates over the given iterators in parallel one-by-one, taking every first index of the rows, every second index, and so forth. After these series of steps we’re working with a list of tuples of ints, but that’s not a big issue. In case, you really want to work with a list of lists again, use this transformation instead:
grid = [list(row) for row in zip(*grid)]Lastly, we want to verify the respective Sudoku subgrid of 3x3 numbers.
This part of line 9 extracts each subgrid for us:
[row[j:j + 3] for row in grid[i:i + 3]]The slicing operator : extracts sublists of both the grid and the iterated rows. However, this operation leaves us with a list of lists of tuples of ints, which is a bit too nested for further processing:
[[(4, 5, 1), (6, 3, 9), (7, 8, 2)], ...]Therefore, we flatten the list by one dimension. As there is no explicit flatten function in Python, we implement one by ourselves… using list comprehensions, of course. We could also use itertools.chain instead, which treats consecutive sequences as a single sequence. But I like the idea of only using list comprehensions for this solution.
The basic structure of flatten using only list comprehension looks like the following:
[item for items in list for item in items]Replace list with the aforementioned operation to extract subgrids and you’re done:
[item for items in [row[j:j + 3] for row in grid[i:i + 3]] for item in items]The innermost nested structure (the 3-tuples) is eliminated, so that we are left with a list of lists of ints again:
Before: [[(4, 5, 1), (6, 3, 9), (7, 8, 2)], ...]
After: [[4, 5, 1, 6, 3, 9, 7, 8, 2], ...]And lastly, if there are no invalid rows, columns or subgrids, the Sudoku puzzle should be valid.
return not (bad_rows or bad_cols or bad_squares)Wrapping it up
And this concludes the end of our journey of comprehending back and forth. Python of course has a much richer set of features, most of which we could not elaborate in this blog post. But when I think about how some of these operations would have looked in, for example, Java, I’m quite satisfied.
Thanks for reading! Feel free to comment or message me, when you have questions or suggestions. You might be interested in the other posts published in the Digital Frontiers blog, announced on our Twitter account.
