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.

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.