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.

Sudoku and Exact Cover problems

Sudoku is an example of an Exact Cover problem and can be solved by picking a subset of candidate rows from the exact cover matrix that satisfy all of the constraints for the complete grid.

I explored building an implementation of Donald Knuth’s Algorithm X using Dancing Links as a Sudoku solver, which you can read more about here.

For a 9×9 Sudoku puzzle, a candidate grid has x possible candidates, by y constraints.

For a 9×9 grid using numbers 1 through 9, there are:

9 rows x 9 columns x 9 (values 1 through 9) = 729

… possible candidate values for the cells.

For 4 constraints applied to every cell in the 9×9 grid, there are

9 rows x 9 columns x 4 constraints = 324

… constraints to be met.

If you fill a grid where a 1 represents a met constraint by that candidate and 0 is unmet, if you zoom out far enough the table looks like this:

To see how a matrix like this is used together with Donald Knuth’s Algorithm X and Dancing Links, see my previous post here.

Updating my AWS Lambda Sudoku Solver to generate new puzzles (part 1)

Having spent some time in the past building an implementation of Donald Knuth’s Algorithm X in Java to solve Sudoku Puzzles, I recently wondered what it would take to modify it to generate new puzzles.

If you missed my previous posts on this investigation, see:

It turns out having a working solver is part of the way there to implementing a puzzle generator, because you need to be able to check if a puzzle has a single solution, since valid puzzles only have 1 solution.

When I last wrapped my Solver as an AWS Lambda, I had taken the naive approach to call System.exit() in my Solver code if I detected there was more than 1 solution as a quick way to exit and not get stuck in a loop iterating over finding possible thousands of solutions for a grid that’s not a valid puzzle.

I went back and took another look at this and reworked it so I could pass an upper limit for number of puzzles, and changed the return type to return a List of solutions, and a flag indicating if there was a single solution or not. Latest commits on my repo have these changes, and I’m now ready to move on to building the puzzle generator. More updates coming soon.

Building a React frontend for my AWS Lambda Sudoku solver

Over the past few months I built an implementation of Donald Knuth’s Algorithm X using Dancing Links in Java to solve Sudoku puzzles.

This was a fascinating exercise in itself (you can read more my experience here), but the next logical step would be to package it up in a way to share it online.

Since I’m pursuing my AWS certifications right now, one interesting and low cost approach to host the the Solver implementation is to package it as an AWS Lambda. Sudoku Solver as a Service? Done. I exposed it through AWS API Gateway. It accepts an request payload that looks like this:

{"rows":["...81.67.","..749.2.8",".6..5.1.4","1....39..","4...8...7","..69....3","9.2.3..6.","6.1.743..",".34.69..."]}

and returns a response with a solution to the submitted puzzle request like this:

{"rows":["349812675","517496238","268357194","185723946","493681527","726945813","972538461","651274389","834169752"]}

The request and response payloads are an array of Strings, where each item represents a String of values concatenated together for one row in the grid, with ‘.’s for unknowns.

I’m still learning React as I go, and while building this front end for my Lambda Sudoku Solver I learnt some interesting things about React and Javascript. The source for the app is shared here.

I used Flux to structure the app, so there main parts of the app are:

  • a main, highlevel Container component,
  • a CellComponent that renders each cell in the Sudoku grid,
  • an Action that handles the interaction with the AWS Lambda
  • a Store that holds the results from calling the Lambda

I don’t want to focus on the pros and cons of using React or Flux (and this is not intended to be a how-to on building an app using React) as there were some other specific issues I ran into that were interesting learning opportunities. A couple of these I already captured in separate posts, so I’ll include these links below.

Iteration 1: onChange handler per row

My first approach to maintaining the state for the display of the grid and the handler for changes to each cell was to keep it simple and have a seperate array of values per row, and a separate onChange handler for each row. This is not a particularly effective way to structure this as there’s duplication in each of the 9 handlers.

The State looked like this:

this.state =
{
row1 : [],
row2 : [],
row3 : [],
row4 : [],
row5 : [],
row6 : [],
row7 : [],
row8 : [],
row9 : []
};

And each of the handlers looked like this, one handler per row, so handleChangeRow1() through handleChangeRow9():

handleChangeRow1(index, event){
console.log("row 1 update: " + event.target.value);
var updatedRow = [...this.state.row1];
updatedRow[index] = event.target.value
this.setState( { row1 : updatedRow } );
}

This approach needed 9 versions of the function above, each one specifically handling updates to the state for a single row. We’ll come back to improving this later.

The interesting thing to notice at this point that to update an array in React state, you need to clone a copy of the array, and then update the copy. I used the spread operator ‘…’ to clone the array.

Each row in the grid I rendered separately like this (so this approach needed 9 of these blocks):

<div>
{
this.state.row1.map( (cell, index) => (
<CellComponent key={index} value={this.state.row1[index]}
onChange={this.handleChangeRow1.bind(this, index)}/>
)
)}
</div>

This was my first working version of the app, at least at the point where I could track the State of the grid as a user entered or changed values in the 9×9 grid. Next steps was to improve the approach.

Iteration 2: Using an array of arrays for the State

The first improvement was to improve the State arrays, moving to an array of arrays. This is easily setup like this:

this.state =
{
grid: []
};

for (var row = 0; row < 9; row++) {
this.state.grid[row] = [];
}

Iteration 3: One onChange handler for all rows

Instead of a handler per row, I parameterized the onChange handler to reused for all rows. This is what I ended up with:

handleGridChange(row, colIndex, event) {
console.log("row [" + row + "] col [" + colIndex + "] : " + event.target.value);
var updatedGrid = [...this.state.grid];
updatedGrid[row][colIndex] = event.target.value;

//call Action to send updated data to Store
SudokuSolverAction.updatePuzzleData(updatedGrid);
}

Using .map() on each of the rows in State, I then rendered each row of the grid like this, passing the current row index and column index as params into handleGridChange():

<tr>
{
this.state.grid[0].map((cell, colIndex) => (
<td key={"row0" + colIndex}>
<CellComponent value={this.state.grid[0][colIndex]}
onChange={this.handleGridChange.bind(this, 0, colIndex)}/>
</td>
)
)}
</tr>

I’m sure there’s a way to use a nested .map() of the results of a .map() or some other clever approach to render the whole grid in a single go, but rendering each of rows individual is an ok approach with me since there’s only 9 rows. If the number of rows were much more than 9 then I’d spend some time working on a better approach, but I’m ok with this for now.

Flux Action and Store

The Action to call the Lambda, and maintaining the state of the responses in the Store was pretty simple. You can check out the source here if you’re interested.

CSS styling for the grid

One last thing to do was to style the grid so it looks like a usual Sudoku grid, with vertical and horizontal lines at 3 and 6, to divide the grid in 3×3 of the 3×3 squares. This took some reading to find out how to easily do this, but turns out CSS nth-child() psuedoclass handles this perfectly. I covered this in this post here.

Take a look at the app

I might move this to a more permanent home later, but if you want to check out the app, you can take a look here.