HTTPS SSH

Sudoku Solver

CircleCI

History

Most online Sudoku solvers even today (2017) relied on server-side code or browser plugins do the actual solving. Around 2007 when I was building my portfolio to start my software engineer career, I decided to create a Sudoku solver entirely in client-side JavaScript. At the time, JavaScript was still considered a limited-use scripting language for the browser, but I saw the potential in this language as it was ubiquitous.

With this project I had the explicit goal of being able to performantly solve all valid single-solution Sudoku puzzles on the client side. At the time, the primary browsers were IE7 and Firefox. Chrome was not released until 2008. This had led me down a path of creating an application heavily relied upon bitwise operations for performance. Even today, the hundreds of unit tests, covering most of the core code, complete in under 1 second.

Implementation

I have implemented a number of human solving techniques. You can take any hard puzzles from the NYT or any other newspaper, and apply it to this puzzle. I am confident that this solver would solve those with no problem. When all human techniques are exhausted, the solver would then remodel the Sudoku as an Exact Cover problem. This allows the solver to solve in milliseconds puzzles that were designed to be impossible.

I did not use any third-party plugins for this when I developed it, so the older version of this solver actually worked on IE5. I even made part of the application work in IE4.
Around 2011, I have updated this to use RequireJS as module system, so that it is portable enough to work on node.js. Around 2017, I have updated to use TypeScript.

Run

To run as a Docker container:

docker build . -t sudoku-solver
docker run sudoku-solver '200105003054000710010203080602807304000000000105309806020701060081000240700402001'

To run as using Node.js/Yarn:

yarn install && yarn build
node dist/src/cli '200105003054000710010203080602807304000000000105309806020701060081000240700402001'