Gotta Comprehend ’Em All! Sudoku verifier done easy in Python

Sep 11, 2020 · 5 min read

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:

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:.....51639...6.48.....7.........39.6.43...52.1.92.........8.....92.1...55764.....`

While the solution for this puzzle would be:

`print(f"Solution:\n{solution}")Solution:487925163925361487631874259258743916743196528169258734314589672892617345576432891`

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.

Digital Frontiers — Das Blog

Dies ist das Blog der Digital Frontiers GmbH & Co.

Digital Frontiers — Das Blog

Dies ist das Blog der Digital Frontiers GmbH & Co. KG (http://www.digitalfrontiers.de). Hier veröffentlichen wir zu Themen, die uns interessieren und bewegen.

Written by

Digital Frontiers — Das Blog

Dies ist das Blog der Digital Frontiers GmbH & Co. KG (http://www.digitalfrontiers.de). Hier veröffentlichen wir zu Themen, die uns interessieren und bewegen.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app