SudokuJS

SudokuJS is a step-by-step Sudoku solver that I wrote in JavaScript. It's my first open source contribution. You can play with the solver here. This post covers my thought process through building this. If you're more interested in the actual code, you can check it out here.

Goals

I wanted to create Sudoku solver that could solve non evil newspaper Sudoku puzzles. In addition, I had three overarching goals:

• Make the solver helpful for humans
• The sudoku board should be interactive — the user should be able to enter numbers and play
• Produce good code that can be reused by others

I decided early to spend minimal time on the UX and the visuals in this project. That's what I usually spend a lot of time on, and I wanted this to be more of a programming exercise. I might revisit these parts later, if I find time.

Making it helpful for humans

How do you make the solver useful for humans? I thought of two major user scenarios that the solver should handle:

1. I'm stuck in my puzzle and want help
2. I want some info about this puzzle – can I solve it? How hard is it?

I'm stuck – give me some help

Before the solver can give any advice it first needs to be able to solve puzzles. I looked at the basic strategies listed here, and eventually implemented them one by one. Just having the strategies available is not enough to make the solver useful however, for a couple of reasons:

• If you're stuck in the middle, and the solver just solves your whole puzzle, well, that's not what you wanted. You still want to be able to solve the puzzle yourself – you just want some help in your current position!
• If you're solving an easy puzzle, and the solver pulls a very advanced strategy only really needed for evil puzzles and says “hey, just use this and you'll be fine”, then well, that's kind of useless (in most circumstances). The solver needs to identify what the easiest possible strategy to move the puzzle forward is – and then use this one.

This adds up to two requirements for the solver: step-by-step solving, and always using the easiest strategies first. Easiest here means easiest for humans – not for the computer. The way my solver solves puzzles is I think quite similar to how humans solve them – but definitely not the ‘optimal' way.

How difficult is this puzzle?

Ranking Sudoku puzzles seems to be a big topic on its own, and not something I wanted to get stuck in. I still wanted to be able to provide some useful analysis for puzzles though.

I decided early on that I was going to base my difficulty ranking on the steps my solver took in order to solve a puzzle. Since I was already attempting to solve the puzzles in the ‘easiest' possible way, I thought this would be a good measure. I tried a few different score formulas, but in the end I went back to the basics. My main ranking is now solely based on what strategies were (ever) used in order to solve a puzzle. Did the solver ever use any hard strategy to solve it? Then it's a hard puzzle. Only easy strategies? Then it's easy. While this method can't tell you which one is the harder of two hard puzzles, it should really never put the wrong label on a puzzle.

Finally, I decided that it could also be useful to tell a user what strategies are needed in order to solve a puzzle. To be really useful this would require either that the user already knows what for example “pointingElimination” is, or that there's some information available to tell them so, but I haven't added such info yet.

Playable puzzle

Creating an interactive UI is the kind of task I had decided not to spend too much time on in this project. Realistically however, the solver needs some kind of visual sudoku board, and the user needs to be able to use it to enter the puzzle they want help with. The alternative would be to use this kind of input for the puzzle:

, but clearly that's not very user friendly. Since the solver is going to present the next step visually on a board, users might as well be allowed to enter their puzzle directly on the board. Then if they started on the board, and the solver continued on the board... It would be madness to force them to go somewhere else to continue (if the solver helps them get unstuck). So the solver had to have a interactive board UI, however minimal. It's currently only useful for easy-medium puzzles, as you can't edit the candidates in the cells. Candidates are the possible numbers that can go into a cell, and are used to solve harder sudoku puzzles. I might add candidate editing functionality later.

Open source – sharing the code

While I have been using GitHub for a while, taking advantage of open source code for color pickers, lazy loading scripts, removing mobile click delays and much more, I had yet to actually get on and share anything myself. Sometimes I feel that what I create is not useful enough to be shared, but I realize now that that's not really my judgement to make. Just put your work out there, and let other's decide if they want to use it or not. If you're following best practice and write modular JS, then your code should already be more or less ready to be used by others, so it's not too much of a commitment.

So now it was time. Aside from writing good code in general, there were three main things I focused on when making this project open source, things that I appreciate when using other people's code:

• Good documentation (including comments)
• Easy setup
• Necessary and useful methods & callback

You can find the SudokuJS code on the GitHub repository — judge for yourself whether I succeeded or not. If you have any feedback I am super keen to hear it! Also, if you decide to use the solver anywhere, don't hesitate to tell me so, or to contact me if you need any help.

So that's it, that's my first open source project. I don't expect it to find too many people, even the current project name is overly redundant — but hey my goal with this project was never for it to go viral. I'm now on GitHub, and you can expect me to share some more project over time. I'm currently writing a tool for DRYing up CSS, I'll post here or on Twitter when I have more info.