Lego MindStorm Sudoku Solver Robot


sudoku3

Swedish hacker [Hans Andersson] is no stranger to puzzle-solving robots. 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.

It was built around the LEGO Mindstorms NXT system, “reads” a printed sudoku page, solves the puzzle, then fills out the solution right on the same page, confidently and in ink. It’s a well-rounded project that brings together an unexpected image scanner, image processing algorithms, and precise motor control, all using standard NXT elements.

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

The building instructions have not yet been posted, but if the video above and the directions for his prior ’bot are any indication, then we’re in for a treat; he simply has a knack for explaining things concisely and with visual clarity.

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.

The source code and the detailed PDF diagrams for Tilted Twister are as gorgeous as his new robot’s penmanship

 

Share Button

Leave a Reply