Toy Robot to Solve Sudoku (w/ Video)

September 3, 2009 by Lin Edwards weblog
Toy Robot to Solve Sudoku

Enlarge

(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: http://tiltedtwist … usolver.html

© 2009 PhysOrg.com

4.6 /5 (5 votes)  

Filter


Move the slider to adjust rank threshold, so that you can hide some of the comments.


Display comments: newest first

Going
Sep 03, 2009

Rank: 5 / 5 (1)
The Lego Rubik cube solving robot is even more awesome. http://www.youtub...n5A0HbhU
Rank 4.6 /5 (5 votes)
Related Stories
Relevant PhysicsForums posts
  • Flow around a reducing bend - effect on pumping work
    created7 hours ago
  • Formula for deflection of 6061 T6 hollow tube, please help.
    created12 hours ago
  • Help to make a Unit Hydrograph of Reservoir Level - Storage Curve for a Dam
    created21 hours ago
  • Heating frozen water pipes by induction?
    createdFeb 05, 2012
  • Bending around sheave or pulley
    createdFeb 05, 2012
  • Electric company meter reading
    createdFeb 05, 2012
  • More from Physics Forums - General Engineering

More news stories

Airborne robot swarms are making complex moves (w/ video)

(PhysOrg.com) -- The GRASP Lab at the University of Pennsylvania this week released a video that shows their new look in GRASP Lab robotic flying devices. They are now showing flying devices with more complex ...

Electronics / Robotics

created Feb 02, 2012 | popularity 4.9 / 5 (28) | comments 10 | with audio podcast report

New Nokia phone no standout, but worth a look

The first of Nokia's new generation of smartphones isn't flashy and certainly isn't an iPhone killer. But it's a nice device, and at $40 with a two-year contract, a bargain.

Electronics / Consumer & Gadgets

created Feb 03, 2012 | popularity 1 / 5 (2) | comments 3

Some HTC Android phones found vulnerable to WiFi password leak

(PhysOrg.com) -- The United States Computer Emergency Readiness Team (U-CERT) has issued a warning to users of some HTC Android phones regarding a security vulnerability that has been found. The warning pert ...

Electronics / Consumer & Gadgets

created Feb 02, 2012 | popularity 5 / 5 (1) | comments 2 | with audio podcast report

New Vizio HD-TV breaks wide-screen barrier for movies, apps

The shape of TVs to come might be even wider than wide-screen. Today's high-definition sets evolved to a rectangular 16-by-9 shape from the more square analog TVs. But a wider 21-by-9 display standard is in ...

Electronics / Consumer & Gadgets

created Jan 30, 2012 | popularity 3.8 / 5 (4) | comments 1

Studying butterfly flight to help build bug-size flying robots

To improve the next generation of insect-size flying machines, Johns Hopkins engineers have been aiming high-speed video cameras at some of the prettiest bugs on the planet. By figuring out how butterflies ...

Electronics / Robotics

created Feb 02, 2012 | popularity 5 / 5 (2) | comments 1 | with audio podcast


Nicira promises virtual networks will transform networking

(PhysOrg.com) -- For the past four years, founders of the start-up company Nicira have been developing cutting-edge software that they predict will transform the networking technology underlying the Internet. ...

Navy to begin tests on electromagnetic railgun prototype launcher

The Office of Naval Research (ONR)'s Electromagnetic (EM) Railgun program will take an important step forward in the coming weeks when the first industry railgun prototype launcher is tested at a facility ...

Study of diving beetles suggest sperm evolution may be driven by changes in female reproductive organs

Studying female reproductive tracts and sperm in diving beetles (Dytiscidae), researchers from the University of Arizona and Syracuse University have obtained a glimpse into a bizarre and amazing world of spe ...

Fossil cricket: Jurassic love song reconstructed

Some 165 million years ago, the world was host to a diversity of sounds. Primitive bushcrickets and croaking amphibians were among the first animals to produce loud sounds by stridulation (rubbing certain body parts together). ...

New insight from whole-genome sequencing of Europe's 2011 E. coli outbreaks

Using whole-genome sequencing, a team led by researchers from Harvard School of Public Health (HSPH) and the Broad Institute has traced the path of the E. coli outbreak that sickened thousands and killed over 50 people in Ger ...

Redder ladybirds more deadly, say scientists

A ladybird's colour indicates how well-fed and how toxic it is, according to an international team of scientists. Research led by the Universities of Exeter and Liverpool directly shows that differences between ...