Sudoku solver

Techniques

single position 0

single candidate 0

candidate line 0

double-pairs 0

hidden-pairs 0

triple-pairs 0

guessing 0

Exection Order

Incremental

Solving algorithm:

How it works:

The custom solving algorithm solves a sudoku much like a human would solve one, using various methods to solve the puzzle (as shown above). The fist thing it does is filling a array of possible values for every field. these possibilities can be printed with the pencil mark button.

Other methods are then used to slim down the array of possibilities, if only one possibility is left in a single field, the value is saved and can be used to solve the rest of the puzzle.

If all methods are attempted and the algorithm can not make progress a guess is made, if this guess results in a unsolvable puzzle it is rolled back and attempted again.

The techniques that will be used can be chosen by checking/unchecking the checkboxes.

using backtracking algorithm: more info

How it works:

The backtracking algorithm solves the sudoku by checking if numbers can be placed on empty spots, if a number does not conflict with the sudoku rules it is saved and the algorithm moves to the next empty field, if the algorithm reaches an unsolvable state the puzzle is rolled back to the last time a choice was made.

Backtracking will however be able to solve faulty puzzles as the starting board is not checked for mistakes.

using backtracking algorithm: more info

How it works:

Uses the backtracking algorithm but in C. Executed on a raspberry pi via a PHP api.

using backtracking algorithm: more info

How it works:

The smart backtracking algorithm works similar to the backtracking algorithm but it creates a list first that contains possible candidates for a square using basic row, column and grid checks. Then the regular backtracking continues but this time instead of checking from numbers 1 to 9 it checks only the possible numbers we defined earlier. With complicated puzzles this can save over 10ms

Smart backtracking will just like the regular backtracking still continue with wrong user inputs, so faulty puzzles can still be made.

What it does:

the helper helps you solve a sudoku via various visual cues, the system does the following:
- a number turns red if its above the value of 9.
- a number turns orange if it clashes with current numbers on the board.
- a number turns blue if it does not clash with the current numbers on the board.
- a number turns green if it is the correct number for the solution.

the solving and pencil mark button are disabled and cannot be used. be aware, the helper will continue to work with your mistakes. if a mistake is made that makes the puzzle unsolvable you will no longer get green numbers.

It uses the custom solving algorithm to check for clashing numbers and the backtracking algorithm to check for the solution.

Camera info

In version 2 the sudoku solver got a new feature, the ability find a sudoku from a video feed. Here follows some information about how this was implemented:

First a video stream is started which is displayed on the page. then a frame of the video feed will be saved and cropped to the size of the red boundaries.

Next the images gets various filters applied to make the number detection step easier:

The contrast in this image is boosted to bring out more detail, which helps the program in low light scenarios but adds noise.
Color is not needed to read a sudoku so the image is converted to grayscale.
An adaptive threshold is applied to the image, which converts all pixels of the image to either fully black or fully white based on the value.

OpenCV is used to find the contours of the image. The contours are used to find all rectangles in the image, the largest of which is returned as an array of coordinates. these coordinates are used to warp the perspective, flattening the image. A simple white raster of lines is projected on the image to get rid of the sudoku's gridlines.

Now we only have the numbers and empty spaces left we can start identifying the numbers. This is done using TensorFlow . The image is split up into 81 individual images, these images are fed into TensorFlow, which has been trained with over 5000 images of sudoku numbers, taken from different sudoku books and digital sudoku's. TensorFlow's result is than compiled into a string & confidence matrix and verified based on puzzle validity and a minimum & maximum amount of numbers.

if the sudoku is deemed valid the final step is performed. A new image is created, this image consist of squares where numbers were detected, this image is projected using the previous array of coordinates to match the angle and orientation of the original image.

And that's it! this cycle is repeated 10 to 20 times to ensure no mistakes have been made. The numbers with the highest occurrence from all attempts are then send back to the solver, ready for you to solve :)