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.

Serverless Framework API Gateway CORS config

If you deploy a Serverless Framework Java Lambda to AWS and attempt to call it locally while developing your frontend, you’ll run into a CORS error like this:

Access to XMLHttpRequest at 'https://abc.execute-api.us-west-1.amazonaws.com/some/api' from origin 'http://localhost:3000' has been blocked by CORS policy: Response to preflight request doesn't pass access control check: No 'Access-Control-Allow-Origin' header is present on the requested resource.

Posts suggest to set a cors option under the event in your serverless.yaml like this:

events:
  - http:
    path: handlerPath
    method: post
    cors:
      origin: '*'

… but in current versions of Serverless this results in an error like this:

Serverless:   at 'functions['example'].events[0].httpApi': unrecognized property 'cors'

From this post, it mentions the cors options has moved up into the provider section:

provider:
  name: aws
  runtime: java8
  lambdaHashingVersion: 20201221
  httpApi:
    cors: true

This is in the docs here.

This works great!

What does this option do? It looks like it sets these options in API Gateway:

‘serverless invoke local’ with Java Lambdas

If you create a Java Lambda with the provided template, you’re probably returning a response using the provided ApiGatewayResponseClass. If you run your Lambda locally with ‘serverless invoke local –function functioname’, you’ll see a response like this:

Serverless: Invoke invoke:local
Serverless: In order to get human-readable output, please implement "toString()" method of your "ApiGatewayResponse" object.

com.serverless.ApiGatewayResponse@3bd3d05e

Any other logger output will appear in your console, but in order to see the actual content of your ApiGatewayResponse, add a toString() method as the message suggests.

You include any of the properties in ApiGatewayResponse, but if you’re just interested in the JSON payload in the body of the response, then just adding this will return the body:

public String toString(){
    return this.body;
}

Serverless framework deploy for Java AWS Lambdas

The Serverless framework ‘serverless deploy’ deploys whatever .jar you have packaged and ready to go within your source project.

If you make local code changes but don’t re-build your .jar, serverless thinks you don’t have any changes to deploy:

$ serverless deploy
...
Serverless: Packaging service...
Serverless: Service files not changed. Skipping deployment...

If you’re building a maven-based project, ‘mvn clean package’ first, then run your ‘serverless deploy’.