Sudoku Solver

This little robot solves a sudoku puzzle all by itself.
It scans the sudoku puzzle using a light sensor. It calculates the solution to the puzzle and then writes the digits.

Scanning
It first performs a quick scan to determine which cells are empty. It sweeps the light sensor over the sudoku puzzle while continuously reading the sensor values.
Each non-empty cell is then handled. An image of the digit is created by scanning the cell line by line moving the robot forward a tiny bit for every line.

Thresholding
The scanned image is very noisy and blurred.
To make it more sharp the image is transformed to a binary image (black and white).
Each pixel with a value below a threshold value is set to black. And the rest of the pixels are set to white.
The values from the light sensor are very close to each other and the overall values are affected by surrounding light, distance between surface and sensor and so on.
The threshold value is calculated by applying an automatic threshold algorithm (The Otsu Method).

Segmentation
The binary image may have more than one segment. It may have pixels not belonging to the digit. The center segment is found and other segments are deleted.

Thinning
The image is converted to 1-pixel wide lines with a thinning algorithm.

Feature extraction
Now the digits are classified by extracting some features from them:
- Width of the digit
- Number of tips
- Position and direction of tips

Solving the Sudoku
Solving a sudoku puzzle is a quite simple task for a computer. It is usually implemented using a recursive backtracking algorithm. But since the Mindstorms processor is rather slow, and since it doesn't allow for recursive functions, it took some care to optimize it.

Raw image

Thresholding

Segmentation

Thinning

Building Instructions