# Toy Robot to Solve Sudoku (w/ Video)

##### Sep 03, 2009 by Lin Edwards

(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.

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.

Explore further: SRI microrobots show fast-building factory approach (w/ video)

## 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, ...

#### Video: Swine flu health tips

Apr 30, 2009

Lucile Packard Children’s Hospital has issued some swine flu health tips.

#### N97 mini, X6 and X3: Nokia unveils new smartphones to rival iPhone (w/ Video)

Sep 02, 2009

Nokia, the world's leading mobile phone maker, unveiled Wednesday three new smartphones as the Finnish firm tries to claw back market share from Apple's popular iPhone and RiM's Blackberry.

#### 'Curtain twitching' skylarks keep track of strangers through their songs (w/ Video)

Aug 26, 2009

(PhysOrg.com) -- Skylarks can hear the difference between friendly neighbours and dangerous strangers, and deal with any threatening intruders, says new research by scientists at Queen Mary, University of London.

Aug 19, 2009

Google has developed a formula to predict hot online search topics in what promises to be a boon for businesses eager to target ads that accompany Internet search results.

#### Fish robot as an alternative marine propulsion system of the future (w/Video)

Jun 09, 2009

The team of Darmstadt researchers analyzed videos of fish’s motions and then developed a prototype fish robot that duplicated them, and are now testing it using the locomotional patterns of various species of fish in order ...

## Recommended for you

#### SRI microrobots show fast-building factory approach (w/ video)

18 hours ago

(Phys.org) —SRI International, a research center that conducts client-sponsored research and development for government and other organizations, is attracting attention for work on what micro-factories ...

#### Honda's new ASIMO robot, more human-like than ever

20 hours ago

It walks and runs, even up and down stairs. It can open a bottle and serve a drink, and politely tries to shake hands with a stranger. Meet the latest ASIMO, Honda's humanoid robot.

#### Simplicity is key to co-operative robots

Apr 16, 2014

A way of making hundreds—or even thousands—of tiny robots cluster to carry out tasks without using any memory or processing power has been developed by engineers at the University of Sheffield, UK.

#### Students turn \$250 wheelchair into geo-positioning robot

Apr 16, 2014

Talk about your Craigslist finds! A team of student employees at The University of Alabama in Huntsville's Systems Management and Production Center (SMAP) combined inspiration with innovation to make a \$250 ...

#### Using robots to study evolution

Apr 14, 2014

A new paper by OIST's Neural Computation Unit has demonstrated the usefulness of robots in studying evolution. Published in PLOS ONE, Stefan Elfwing, a researcher in Professor Kenji Doya's Unit, has succes ...

#### Eye of the beholder: Improving the human-robot connection (w/ video)

Apr 11, 2014

Researchers are programming robots to communicate with people using human-like body language and cues, an important step toward bringing robots into homes.

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

## More news stories

#### Hackathon team's GoogolPlex gives Siri extra powers

(Phys.org) —Four freshmen at the University of Pennsylvania have taken Apple's personal assistant Siri to behave as a graduate-level executive assistant which, when asked, is capable of adjusting the temperature ...

(Phys.org) —Google engineers working on software to automatically read home and business addresses off photographs taken by Street View vehicles, have created a product so good that not only can it be used ...

#### Tiny power plants hold promise for nuclear energy (Update)

Small underground nuclear power plants that could be cheaper to build than their behemoth counterparts may herald the future for an energy industry under intense scrutiny since the Fukushima disaster, the ...

#### Neuromorphic computing 'roadmap' envisions analog path to simulating human brain

(Phys.org) —In the field of neuromorphic engineering, researchers study computing techniques that could someday mimic human cognition. Electrical engineers at the Georgia Institute of Technology recently ...

#### SRI microrobots show fast-building factory approach (w/ video)

(Phys.org) —SRI International, a research center that conducts client-sponsored research and development for government and other organizations, is attracting attention for work on what micro-factories ...

#### First potentially habitable Earth-sized planet confirmed: It may have liquid water

The first Earth-sized exoplanet orbiting within the habitable zone of another star has been confirmed by observations with both the W. M. Keck Observatory and the Gemini Observatory. The initial discovery, ...

#### Vitamin B3 might have been made in space, delivered to Earth by meteorites

Ancient Earth might have had an extraterrestrial supply of vitamin B3 delivered by carbon-rich meteorites, according to a new analysis by NASA-funded researchers. The result supports a theory that the origin ...

#### Better thermal-imaging lens from waste sulfur

Sulfur left over from refining fossil fuels can be transformed into cheap, lightweight, plastic lenses for infrared devices, including night-vision goggles, a University of Arizona-led international team ...

#### Bright points in Sun's atmosphere mark patterns deep in its interior

Like a balloon bobbing along in the air while tied to a child's hand, a tracer has been found in the sun's atmosphere to help track the flow of material coursing underneath the sun's surface.

#### Researchers find tin selenide shows promise for efficiently converting waste heat into electrical energy

(Phys.org) —A team of researchers working at Northwestern University has found that tin selenide (SnSe) has the highest Carnot efficiency for a thermoelectric cycle ever found, making it potentially a possible ...