Toy Robot to Solve Sudoku (w/ Video)

Sep 03, 2009 by Lin Edwards weblog

(PhysOrg.com) -- A Swedish programmer, Hans Andersson, has used a Lego Mindstorms NXT kit to develop a robot to solve Sudoku puzzles.

Andersson first purchased the Lego Mindstorms kit for his daughters, but couldn't resist playing with it himself.

The first scans the puzzle and uses an to map out the puzzle's pre-set numbers and blank squares. The robot scans one line at a time, inching forward a little after each line is scanned.

The blurry scanned image is then converted to a black and white binary image to improve the sharpness of the picture. A threshold value calculated by Otsu's Method is used to determine whether each pixel in the image is white or black.

This video is not supported by your browser at this time.

The Otsu Method classes pixels as either foreground or background, and then determines the optimal threshold that minimizes the intra-class variance. Pixels below the threshold are set to black, and those above are set to white.

A thinning algorithm is then used to convert the resulting image of each digit to 1-pixel wide lines. The digits are then examined for features such as their width, and the number and direction of tips on the digit. The digit six, for example, has one tip, which points to the right. Following this procedure for each digit, the robot identifies all the pre-set numbers in the puzzle.

Once the puzzle is mapped, the robot solves it and fills in the blank squares. A recursive backtracking algorithm would normally be used to solve puzzles such as Sudoku, crosswords, or other puzzles in which the solution has several candidates. The method carries out a systematic examination of all possible solutions, and abandons and does not re-visit any that are eliminated.

The Lego Mindstorms processor is too slow to use a backtracking algorithm and it does not allow for recursive functions, so Andersson had to make sure the calculations were optimized. The result is a little robot that can solve Sudoku puzzles and get them right every time, and in only a few minutes.

More information: tiltedtwister.com/sudokusolver.html

© 2009 PhysOrg.com

Explore further: Posture affects infants' capacity to identify objects, study finds

Related Stories

Two Robot Chefs Make Omelets

Dec 04, 2008

(PhysOrg.com) -- No "house of the future" is complete without a household robot to do the cooking and cleaning. Although today´s robots still have a ways to go before substituting for a real live-in maid, ...

Recommended for you

A robot prepared for self-awareness

4 hours ago

A year ago, researchers at Bielefeld University showed that their software endowed the walking robot Hector with a simple form of consciousness. Their new research goes one step forward: they have now developed ...

Future US Navy: Robotic sub-hunters, deepsea pods

Mar 28, 2015

The robotic revolution that transformed warfare in the skies will soon extend to the deep sea, with underwater spy "satellites," drone-launching pods on the ocean floor and unmanned ships hunting submarines.

Festo has BionicANTs communicating by the rules for tasks

Mar 27, 2015

Germany-based automation company Festo, focused on technologies for tasks, turns to nature for inspiration, trying to take the cues from how nature performs tasks so efficiently. "Whether it's energy efficiency, ...

Virtual robotization for human limbs

Mar 26, 2015

Recent advances in computer gaming technology allow for an increasingly immersive gaming experience. Gesture input devices, for example, synchronise a player's actions with the character on the screen. Entertainment ...

Robots on reins could be the 'eyes' of firefighters

Mar 25, 2015

Researchers at King's College London have developed revolutionary reins that enable robots to act like guide dogs, which could enable that firefighters moving through smoke-filled buildings could save vital ...

User comments : 1

Adjust slider to filter visible comments by rank

Display comments: newest first

Going
5 / 5 (1) Sep 03, 2009
The Lego Rubik cube solving robot is even more awesome. http://www.youtub...n5A0HbhU

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.