# Toy Robot to Solve Sudoku (w/ Video)

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

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: Two Robot Chefs Make Omelets

## Related Stories

#### Two Robot Chefs Make Omelets

December 4, 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, researchers are ...

#### Video: Swine flu health tips

April 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)

September 2, 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)

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

#### Google helps advertisers predict hot search topics

August 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)

June 9, 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

#### Israel firm wants super-efficient engine to power car revolution

October 28, 2016

An Israeli firm says a super-efficient engine it has created could drastically reduce fuel consumption and help power an auto industry revolution as manufacturers search for environmentally sound alternatives.

#### Learning Morse code without trying

October 27, 2016

It's not exactly beating something into someone's head. More like tapping it into the side.

#### Apple adds keyboard touch functions to Mac in major refresh

October 27, 2016

Apple's high-end Mac laptops are getting a touch-sensitive strip above the keyboard, as the company aims to spark consumer interest in a product line that's often overshadowed by newer gadgets like the iPad and iPhone.

#### You are less anonymous on the web than you think—much less

October 26, 2016

If you still think you can be anonymous on the internet, a team of Stanford and Princeton researchers has news for you: You can't. Over the summer, the team launched what they called the Footprints Project, which invited ...

#### Microsoft aims at Apple with high-end PCs, 3D software

October 26, 2016

Microsoft launched a new consumer offensive Wednesday, unveiling a high-end computer that challenges the Apple iMac along with an updated Windows operating system that showcases three-dimensional content and "mixed reality."

#### For the first time, brain surface stimulation provides 'touch' feedback to direct movement

October 26, 2016

In the quest to restore movement to people with spinal cord injuries, researchers have focused on getting brain signals to disconnected nerves and muscles that no longer receive messages that would spur them to move.

## 1 comment

Adjust slider to filter visible comments by rank