Note

I have rewritten this project using React and TypeScript - see sudoku-buster-react.

Description

The idea of this repo is to create a web application to scan a Sudoku puzzle from a newspaper or similar, solve the puzzle and display the solution.

I used a separate project to develop code to scan a Sudoku puzzle. It uses:

• OpenCV.js to find the bounding box of the puzzle
• TensorFlow.js to train a model to recognise blank squares / digits 1 through 9

I use dlxlib to solve the Sudoku puzzle (my implementation of Knuth's Algorithm X).

Large Download

It should be noted that this web app takes quite a while to load because some of the resources are very large:

Resource	Size
opencv_4.1.1.js	8.7M
opencv.js	4.1MB
index.bundle.js	997KB
models/digits/model.weights.bin	626KB
models/blanks/model.weights.bin	304KB
models/cells/model.weights.bin	627KB

I clearly still have some work to do to reduce the size of these resources.

Update 1

I have managed to halve the size of opencv.js by making my own custom build.

Update 2

opencv.js

I have moved the foundBoundingBox step from JavaScript to a C++ WebAssembly (see this separate repo) so that I no longer need to include opencv.js. The C++ WebAssembly is about 1MB in size.

index.bundle.js

I have updated @tensorflow/tfjs to the latest version (currently 3.6.0). I hope to reduce the size of the main bundle by doing some of the stuff described here.

Instructions

• Browse to https://sudoku-buster.herokuapp.com/
• Wait for the web app to load
• Tap the big square to start the webcam
• Point the webcam at a Sudoku puzzle
• When the web app recognises the puzzle, it stops the webcam and shows the solution
• Given digits are shown in magenta and calculated digits are shown in black
• For best results:
  • Try to position the puzzle roughly within the guides
  • Try to ensure puzzle is reasonably straight (not too wonky or warped)
  • Try to avoid shadows
• Use the Cancel button to stop scanning and return to the start
• Tap the solution to return to the start

Query Params

The following query params can be added:

Query Param	Description
c	Draw the largest contour (red)
cs	Draw the four corners of the largest contour (magenta)
bb	Draw the bounding box of the largest contour (blue)
gs	Draw all the grid squares (green)
fps	Display the number of webcam captures being processed per second

The following link enables all options (the "Everything Bagel"):

• https://sudoku-buster.herokuapp.com/index.html?c&cs&bb&gs&fps

TODO

• Try to further reduce the size of opencv.js
  • UPDATE: I have now moved the findBoundingBox step to a C++ WebAssembly to avoid having to use opencv.js
• Use a service worker to cache large files
• Improve scanning speed/accuracy/robustness
  • Autocorrect warped images
  • Tune the training of the cells model
  • Re-train the cells model on binary images
    • In an attempt to better handle different lighting conditions
• Upload performance metrics and store them in a document database
• Add a new web page for analysis of uploaded performance metrics

Tests

A few basic in-browser tests can be found here:

• Tests

Links

• For the OpenCV approach to finding the bounding box, I borrowed heavily from:
  • Emaraic - Real-time Sudoku Solver
  • tahaemara/real-time-sudoku-solver: Real-time Sudoku Solver using Opencv and Deeplearning4j
• sudoku-scanner
• Knuth's Algorithm X
• Dancing Links
• dlxlib
• MongoDB Node.JS Driver
  • MongoDB Node.js Driver Documentation
  • Node.js MongoDB Driver API