Interrelated personal side projects can be a goldmine of learning opportunities

Some people struggle to find ideas for working on side/personal software development projects for learning (and fun!). I’ve kept a running list of ideas in an online notebook and if I’m struggling for an idea for a new project I refer back to this list.

Over the past couple of years I stumbled across a series of inter-related projects that’s been a goldmine of learning opportunities, from frontend to backend to serverless.

This series of projects started with a question “Can you solve a problem without understanding the problem?”. tl;dr? No. The problem for this activity was solving Sudoku puzzles, and you can read more about this here:

This lead to the next step, researching more about exact cover problems, and how they can be solved with well established algorithms:

After building an implementation of Donald Knuth’s Algorithm X, I packaged it up as an AWS Lambda, and then built a React frontend for it:

I have one other project in progress for the frontend, replacing Flux with Redux. I’m still working on that one.

After building my solver and the frontend, I starting thinking about how to generate new puzzles. This is in progress here: https://github.com/kevinhooke/sudoku-generator

If you’re generating new puzzles you also need a way to grade the difficulty of puzzles. The unusual thing about this is there’s no established algorithm for grading the complexity of Sudoku puzzles, they’re typically graded by applying human solving techniques, so this led to this: https://github.com/kevinhooke/sudoku-human-grader

This string of related projects has kept me busy of the past couple of years. Not every idea will lead to a series of related projects like this, but if you can find an idea that does, it will keep you busy with plenty of problems to solve and many learning opportunities.

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.