How To Measure Sudoku Difficulty

Glen Brunke, November 15, 2023

Sudoku puzzles, with their grid of numbers and logical challenges, have become a beloved pastime for millions worldwide. The history of Sudoku is rich, stretching back centuries, and its evolution into the digital age has transformed the way these puzzles are created and enjoyed today.

A Quick History Of Sudoku

The roots of Sudoku can be traced back to ancient number puzzles. In the 18th century, Swiss mathematician Leonhard Euler created a puzzle known as the Latin Square, a precursor to modern Sudoku. However, it wasn't until the late 20th century that Sudoku as we know it emerged.

Sudoku gained international popularity in the early 2000s, thanks in large part to a campaign by a retired judge from New Zealand, Wayne Gould. After encountering Sudoku in a Tokyo bookstore, Gould worked to popularize the puzzle globally, leading to its inclusion in many newspapers and puzzle books.

The Structure of Sudoku

A standard Sudoku grid consists of a 9x9 matrix, divided into 3x3 subgrids. The objective is to fill in the grid with digits from 1 to 9, ensuring that each row, column, and subgrid contains each digit only once. The initial grid contains some given numbers, serving as the starting point for the player.

Digital Transformation

As technology advanced, Sudoku made the leap to the digital realm. Online platforms, mobile apps, and computer software now offer Sudoku enthusiasts a plethora of options for playing and solving puzzles. The shift to digital has not only increased accessibility but also allowed for more complex and varied puzzle designs.

Modern Sudoku puzzles are often created using sophisticated algorithms that ensure a unique solution and a satisfying level of difficulty. These algorithms take into account various solving techniques, ranging from simple eliminations to complex strategies, providing a diverse and engaging experience for players of all skill levels.

How Difficulty Is Measured

There is not a standard, agreed upon method for measuring puzzle difficulty. Most puzzle players will tell you that it probably has something to do with the number of "givens", or the number of numbers already on the board before you start. Some say that you can use a point system based on the number of times you had to use an advanced technique like The Swordfish. Two physicists published a paper in 2012 titled The Chaos Within Sudoku as an attempt to develop a "Richter-type scale" to measure puzzle difficulty depending on the range of techniques needed to solve the puzzle. Others use a subjective scale by trying the puzzle out to see how hard it feels.

The problem with the above methods is that it can vary from publisher to publisher and we lack a universal standard way to "score" a puzzle's difficulty. The Chaos theory is useful, but overly complex in my opinion. There is a more simple way...

A Simple Way To Measure Difficulty

I propose the puzzle player's intuition is nearly correct: the givens make the difference. However, the point that I would build on is that it's not just the number of givens that matter, but the amount of information that they reveal.

Two puzzles can have exactly the same number of givens, but vary in difficulty. When a number is revealed on the playing board, it brings with it additional information about the surrounding cells as well. The total amount of information that has not yet been revealed can be represented as the range of possible moves for each cell. All of the possible numbers that can be played in a cell, in scientific terms, is that cell's entropy. The more possibilities there are, the more entropy.

It turns out, it's relatively simple to measure entropy in Sudoku. A cell can only contain the numbers 1 through 9, so a cell's maximum entropy is 9. As numbers are revealed on the board, the entropy of the cells in the same row, column, and 3x3 box fall, until they all reach zero and the puzzle is solved.

A Tool For Measuring Difficulty (Entropy)

I created a simple tool to measure the amount of entropy in a Sudoku puzzle. It works by measuring all of the possible moves for each cell and color coding that cell based on its total entropy. Darker green equals more entropy, and lighter green less. Blue-green means there's only one remaining possibility. If a cell is in conflict with the rules, it will color that cell red. To input the numbers, just click or press on the desired cell and select the number that should go there. Try out your next puzzle and see how well it matches.

Click On (Or Touch) The Grid To Start

If you're interested in the source code, you can find it on my github repository.

What Number Equates To A Hard Puzzle?

According to AISudoku.com, the world's most difficult puzzle with only one solution scored a 234. Most of the "evil" or "difficult" puzzles that I tried scored around 200. An easy puzzle was around 100-120 and medium was in between those two.

Check out the Top 10 Most Difficult Sudoku Puzzles if you'd like to see some examples of very challenging puzzles. The NY Times Sudoku is also held up by Sudoku enthusiasts as being of very high quality as well.

Regardless of the metrics used to gauge difficulty, Sudoku proves to be a delightful way to pass the time, fostering mental agility and providing a satisfying challenge for enthusiasts of all skill levels. So, dive into the grid, enjoy the journey of solving, and relish the mental workout that Sudoku brings to keep your mind sharp and entertained.

Image credit Microsoft Bing Image Creator, powered by DALL-E from OpenAI. Prompt: A toad completing a Sudoku puzzle on a stump. He is wearing glasses. Digital art style, photorealistic, surreal.