Grading the difficulty of a Sudoku puzzle

I’ve made a couple of previous attempts at developing Sudoku solvers, one naive approach which didn’t work too well, and a second, more informed attempt implementing Donald Knuth’s Algorithm X, which works incredibly well.

I thought I would turn this around and instead of building a solver, attempt to build a puzzle generator. As I already have a working solver (I’ve also build a React frontend for the Algorithm X solver that runs as an AWS Lambda), checking if I have a valid puzzle (one with only a single solution) is easy as I can reuse my existing solver. The hard part it turns out to be how you grade the difficulty of a puzzle, i.e. is a puzzle easy, medium or hard? This turns out to be a subjective point of view, based more personal opinion rather than any established levels of measuring difficulty. It’s interesting to note that apparently unlike a solver, there are no established mathematical approaches for grading a Sudoku puzzle.

Ok, so if it’s subjective, how to we write an app to automate the grading? First, the degree of how easy or complex a puzzle is determined using the same approaches to solve the puzzle as a human attempting to solve a puzzle does. The range and number of different approaches needed to solve a puzzle can be used to determine the relative difficulty. This is where the subjective nature comes in.

It seems to be commonly agreed that a puzzle rated as ‘simple’ can be solved solely by identifying ‘naked singles’ and/or ‘hidden singles.’ I’m not going to define all of the solving techniques as they’re described in many places online already, but for reference for the first couple see here:

Next for ‘medium’ difficulty, if you need to use naked pairs and hidden pairs, this puzzle is commonly considered medium difficulty.

Similarly for hard, if you need to used naked triples and/or hidden triples.

At this point more complex techniques such as x-wing and swordfish seem to be used to determine very hard or expert level, but there seems to be some variation on what level of difficulty require these techniques. There’s also many other techniques, some are listed here.

Grading Puzzle Examples

Given that there’s no standard approach to grade a puzzle, it’s probably going to be common that if you take an example puzzle from any source, the approaches used to grade that puzzle might be different from the rules you would apply, and therefore there’s likely to be some variation in difficulty of puzzles.

Let’s take a couple of example puzzles from sources online and run them through my grader so far so see if we’re on the right track.

Here’s an ‘easy’ puzzle example from https://www.websudoku.com :

Running my grader against this puzzle, I get:

Puzzle solved: Yes
Initial givens: 35
Passes through grid: 7
Naked singles found: 42
Hidden singles found: 0

This puzzle can be solved only by finding naked singles, therefore by my grading system, this is rated as ‘easy’ difficulty.

This next example needs additional approaches to solve, although it needs two approaches that would still be considered at the easy level, naked singles and also hidden singles:

This is a hard example from SukokuWiki:

Output from solver:

Puzzle solved: Yes
Initial givens: 44
Passes through grid: 35
Naked singles found: 6
Hidden singles found: 30
Naked pairs found: 17

Here’s an example where the source of this puzzle rates this one as difficult, but applying my ranking criteria my approach would classify this one as a medium (since it requires more than finding just singles, it requires finding pairs, but not any other techniques other than pairs).

Summary

Writing a solver following recognized algorithms like Dancing Links and Algorithm X turned out to be much simpler than developing a human ranker. For the ranker it took significant time to get the approaches implemented so they were working correctly and to the point where they could actually solve a puzzle. As this was a personal time project and I was only working on this a couple of hours a week, it took the majority of 2020 to get this complete and working. By comparison the Algorithm X solver I was able to complete in a couple of hours a week over about 2 weeks.

Completing this grader was one step towards implementing a puzzle generator. This is now also complete and running a couple of times a day, generating new puzzles which you can load via my React frontend here.

Updating my React Sudoku Solver app: Replacing Flux with Redux (part 2)

In the first part of converting my Sudoku solver React app from using Flux to Redux I looked at creating the Redux Store, Action Creators, reducers, and connecting Components to the Store. In this part 2 I’m taking a look at using redux-thunk for making my api calls.

Async API calls are integrated into a Redux app by using a ‘thunk’, support is provided by adding react-thunk to your app:

npm install --save redux-thunk

react-thunk is a middleware for your Redux Store. It looks at each Action dispatched to your Store and if it’s a function instead of an Action object it executes it.

Where you create your store with createStore(), add an import for applyMiddleware and thunk:

import { applyMiddleware, createStore } from 'redux';
import thunk from 'redux-thunk';
const middlewares = [thunk];

Pass a call to applyMiddleware as a param to createStore() passing this middlewares array. In my app I’ve already passed the devToolsEnhancer() to createStore():

let store = createStore(puzzleDataReducer, devToolsEnhancer());

Naively, I thought I’d be able to add thunk and devToolsEnhancer() in the array and pass like this:

const middlewares = [thunk, devToolsMiddleware()];
let store = createStore(puzzleDataReducer, applyMiddleware(...middlewares));

… but this leads to some rather cryptic errors and I’ve honestly no idea what this means or how to resolve it:

VM1047:1 Uncaught TypeError: t.apply is not a function
     at :1:47480
     at :1:33759
     at :1:26192
     at eval (redux.js:602)
     at eval (redux.js:646)
     at createStore (redux.js:79)

Luckily a quick search found this article, suggesting the way to combine these enhancers is to use redux’s compose() function. Import compose from redux:

import { createStore, applyMiddleware, compose } from 'redux';

Use compose() to combine thunk and the devToolsEnhancer() call like this:

compose(
   applyMiddleware(thunk, otherMiddleware()),
   window.devToolsExtension ? window.devToolsExtension() : f => f
 )

In my case I don’t have other middleware to include, so my createStore() was originally this:

let store = createStore(puzzleDataReducer, devToolsEnhancer());

and now including thunk and using compose() it looks like this:

let store = createStore(puzzleDataReducer, compose(
    applyMiddleware(thunk),
    window.devToolsExtension ? window.devToolsExtension() : f => f
    )
);

Next I need to move my Flux Action that makes my api call to a function that is returned by an Action Creator. Since react-thunk looks for functions returned by Action Creators instead of Action objects and executes them. this was a relatively minor change moving the function from my original Action to my Action Creator.

At this point I’ve got a working app, migrated from Flux to Redux. You can check the final result on GitHub here. I’ve still got some cleanup to do – in particular I don’t have a clean separation between my reducer code and my Action Creator code. I’ll code back and do some cleanup later, and also deploy a parallel copy of the same app to AWS. Right now the original Flux based app is deployed here. I’ll deploy the final Redux based app shortly.

Using my Sudoku Solver to generate new puzzles (part 2)

Following on from Part 1, I’ve been looking at some alternative approaches to generating new Sudoku puzzles. It turns out that having a working and effective solver is essential in generating new puzzles, because you need to know if you’ve generated a valid puzzle, meaning a puzzle with only a single solution.

The generally accepted approach to creating new puzzles is to generate a completed grid and then remove values from cells, checking at each step that you still have a valid puzzle and then stop at a point where you’ve generated a puzzle with the required difficulty. Grading a puzzle ‘easy’ through ‘difficult’ is another topic unto itself, so I’ll come back to this later.

Here’s a summary of possible (but not exhaustive) approaches to generate a completed grid:

Brute force approach with backtracking

  • fill each cell with a random number
  • check puzzle is valid
  • if puzzle is not valid, go back to previous cell and try another random number

Although this approach would work, it’s obviously not the most efficient approach. Brute force algorithms usually take advantage of the speed of today’s CPUs to offset the inefficiency of trying every combination until you get what you’re looking for.

Running a solver against an empty grid

  • run solver against empty grid
  • ensure solver is picking a random candidate column from it’s exact cover matrix (see previous posts for how this is used by the solver)

This approach is interesting as it reuses the Solver, and instead of solving a puzzle with a limited number of givens, the puzzle has zero givens. My Solver uses the same approach with Knuth’s Algorithm X to ‘solve’ an empty grid, it doesn’t make much difference whether there’s a minimum of 17 givens for a valid puzzle or zero puzzle, it will still fill the grid.

The downside of my current Solver approach though is that it will always fill the grid with the same combination of numbers due to the way it always picks the next value based on the next unmet constraint with the least number of remaining possible candidates. While this approach sames significant time solving a valid puzzle, it does mean the approach has a predictable result and doesn’t produce random filled grids. This could be updated to add some randomness, but I think there’s an easier approach.

Run solver against a partially populated grid

  • Populate row 1 in the grid with a random combination of 1 through 9
  • Run the solver against this ‘seeded’ grid

Like the previous approach, this reuses the solver. However, by ‘seeding’ the first row with a random combination of 1 through 9, this does result in different grids being generated. Without any closer investigation however, due to the predictable results from my Solver, I think at best this probably means this approach will only generate 9! combinations (362880). While this is enough puzzles to keep you busy for a least a few weeks (!), there still has to be a better approach.

Conclusions

Since I already have a working solver, I’m going to use the ‘seeded’ partially populated grid approach, run my seeder against it, then remove a number of candidates, then run a ‘difficulty grader’ against it. I’ve been working on the ‘grader’ for a while now, I’ll post an update on the approach I’m taking with that in another post.