Google Goggles Solves Sudoku

mikejuk writes "Ever been frustrated when you can't solve a Sudoku? Well, now there's an app for that. It is just one more capability in the latest version of Google Goggles. All you have to do is point your phone's camera at a Sudoku puzzle, take a snapshot, and pattern recognition and a bit of game logic sorts out the answer. Have you ever had the feeling that AI is getting to be just a little too commonplace?"

Comments

Sudoku porn

[Quiet_Desperation]

Ever been frustrated when you can't solve a Sudoku

No. Never been unable to solve one. :)

Re:Sudoku porn

[Yold]

after 6 hours of calculation

Holy moley, my unoptimized naive (backtracking) solution written in C would solve the hardest puzzles in under 30 seconds, on my 900mhz netbook no less. What language did you write it in (not trolling here)?

Re:Sudoku porn

[slim]

Holy moley, my unoptimized naive (backtracking) solution written in C would solve the hardest puzzles in under 30 seconds, on my 900mhz netbook no less. What language did you write it in (not trolling here)?

We had a little office competition to see who could write the fastest solver, back when the Sudoku craze kicked off.

I think all our solutions came up with a solution in a fraction of a second; but I don't think any of them would have found all the solutions to a grid which had more than one. Indeed I bet some of the algorithms would have stalled on such a grid -- since one of us limited himself to applying the kind of rules that a human might apply.

(He was able to programmatically classify grids into difficulty levels, by counting how many of the rules were necessary to solve it)

Re:Sudoku porn

[digitig]

No. Never wanted to solve one. Now, if they can do an app that solves cryptic crosswords...

Just like "Sudoku Grab" on the iPhone has done for

[Anonymous Coward]

The developer of Sudoku Grab for the iPhone - which solves Sudokus via the camera - has a blog post explaining how he did this (in June 2009.)

http://sudokugrab.blogspot.com/2009/07/how-does-it-all-work.html

Need more AI

[krou]

Have you ever had the feeling that AI is getting just a little be too commonplace?

Could do with some more English AI apps, if you ask me.

Re:Need more AI

[somersault]

Something makes me think that you don't really believe the quote in your signature.

we hath defeated the purpose

[tverbeek]

OK, it's cool technology, but this is almost as pointless as Homer Simpson's book of already-solved crossword puzzles.

Re:we hath defeated the purpose

[Ginger Unicorn]

now that's a contemporary reference...

Sudoku

[TheSpoom]

I think I remember hearing during my CS university days that solving Sudoku was relatively easy compared to actually coming up with puzzles that satisfied the rules of Sudoku.

Re:Sudoku

[Monkeedude1212]

They probably didn't do the image processing from scratch, they probably used a pre-existing image comparison tool to check for something like

###
###
###

Then chopped each square into its own, verified the symbol, and filled their arrays and got Cracking.

Re:Sudoku

[drosboro]

I think I remember hearing during my CS university days that solving Sudoku was relatively easy compared to actually coming up with puzzles that satisfied the rules of Sudoku.

True enough... although it's not really that hard to generate puzzles that satisfy the rules of Sudoku, either. What is a bit more challenging is coming up with interesting puzzles that solve the rules of sudoku, as is assigning a difficulty rating to them. I still haven't found a Sudoku app (including my own, unfortunately!) that generates puzzles as interesting as a skillfully hand-created puzzle. Some are better than others (one hopes mine is on the upper end, of course), but it's still hard to write an algorithm for making really good Sudoku puzzles.

Re:Sudoku

[slim]

They probably didn't do the image processing from scratch, they probably used a pre-existing image comparison tool to check for something like

Google Goggles is build around a pretty sophisticated image processing/classification engine. It takes an arbitrary snapshot, and recognises barcodes, QR codes, book/CD/DVD covers, product logos etc., and directs you to the appropriate Google search results.

With this, they've just added a class of image, and a service to handle it. It's a fun way to raise awareness of Goggles for them, I guess.

solving Soduku

[56ker]

I thought the fun was in trying to solve it yourself, not through having a machine give you the correct answer.

Re:solving Soduku

[ILMTitan]

I always thought the fun failed because it was easier to tell a computer how give you the correct answer than to solve it yourself.

Re:solving Soduku

[MancunianMaskMan]

go get your coat and hand in your geek card at the door. The fun is in writing the program that solves the puzzle

Re:solving Soduku

[Stooshie]

Given your sig, are you being sarcastic?

it really works, its quite amazing

[circletimessquare]

i had a meeting with my boss today and he gave me a list of new requirements for extending the inhouse app. i pointed my cell phone at my notes from the meeting, it snapped a picture of my poor handwriting and the list of new requirements, i sent the picture to google goggles, i went to lunch, and when i came back google goggles was busy writing jquery code and extending the xslt transforms we use. i may even get a raise. thanks google goggles

Re:it really works, its quite amazing

[ziggyzaggy]

I tried that, but instead of a solution the google goggles sent a Terminator that killed my boss. Now my company is outsourcing our whole department, to google. thanks a lot, google goggles.

Re:it really works, its quite amazing

[Monkeedude1212]

You think that's impressive?

I've been having trouble satisfying my girlfriend in the bedroom. Tried everything, hours of foreplay, tools, toys, you name it! Then Google came along and changed everything. I simply took a picture of her lying naked on my bed with my cell phone, uploaded the picture to Google, and went to go grab some chinese food. By the time I got halfway through the Schezwan Chicken, she was having multiple orgasms! Thanks to Google, my relationship has never been better!

Re:it really works, its quite amazing

[Abstrackt]

Dude, that's because you left the phone on vibrate.

Re:Stunning

[peragrin]

What AI though? Sudoku is pattern recongintion. It doesn't take an AI to solve one. There is more processing spent on image analysis than actual problem solving.

When I think AI I think of some that can create on it's own. Not learn, not solve but create.

Re:Sudokus

[Monkeedude1212]

It's not even to do with numbers, it's just unique identifiers.

You could do it with animals. 1 = cow, 2 = sheep, so one so forth. I like to do it with colours, red, blue, yellow, etc. You could do it with Letters, ABCD...

There is no addition, subtraction, no real computation done with any of the numbers. The only rules are that there has to be 1 of every 9 symbol in each box and each row, and that rule will enforce the subsets that most other people apply (no two identical symbols in the same row or box).

Re:Sudokus

[slim]

Most people think that Sudoku is a math puzzle because its often associated with numbers, but thats not really the case as you can do it with any 9 unique identifiers.

Well, set theory isn't to (necessarily) do with numbers, and it's still maths.

Sudoku's a lot easier for a human to solve when the nine symbols happen to be numbers (or anything else with a well defined order), because you frequently count through the symbols to see which ones are missing.

Kakuro FTW, by the way.

Fully-automated Sudoku solution

[Tetsujin]

1: Set up a cron job on the home machine to periodically check Amazon for new Sudoku books and buy them
2: Build a package receiving conveyor to bring the packages in once delivered.
3: On the conveyor, set up imaging sensors to analyze the package, and robot arms to remove the packaging.
4: Once the book is freed from its packaging, remove its binding.
5: Move the individual pages through a paper-feed system. Along the paper-feed system there will be an examination station in which lights will illuminate the page as the phone takes a picture of the puzzle and solves it. The page is then inverted and any puzzles on the opposite side are also solved.
6: Once each page is solved, it is no longer needed: the pages are deposited in paper recycling.

From there, the operator just needs to take the bin out to the curb every week... I love Sudoku!

Re:Sudokus

[maxwell demon]

Most people think that Sudoku is a math puzzle because its often associated with numbers, but thats not really the case as you can do it with any 9 unique identifiers.

Most people think math means it has to be associated with numbers, but that's not really the case. Numbers just turn out to be a great tool which can be applied to a wide range of mathematical problems. But the problems themselves are often not defined in terms of numbers.

I'd consider Sudoku a math puzzle, even without numbers. You have a set of symbols (and yes, from a mathematical standpoint, your colors are symbols as well) and a set of places (being arranged in a square grid), and the task is to find a mapping from the places to the symbols so that for certain subsets of the set of places (rows, columns, subsquares) each symbol appears exactly once (or to say it more mathematically, for each of those subsets the restriction of the searched-for function to that subset is bijective). It's a well-defined mathematical problem.