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

better-it-than-me?

[intellitech]

No, better-at-it-than-you!

Re:better-it-than-me?

[vux984]

No it was fine the first time. "better-it-than-me".

You've never heard the expression "Better him than me." ?

In this case "him" is an "it" ("google goggles"), so its "Better it than me.", as in "better that it have to figure out sudoko, than for me to have to figure out sudoko".

Of course, its possible that the author just messed it up, and meant what you said, but it is hardly self evident that is so.

Re:better-it-than-me?

[Golddess]

In this case "him" is an "it" ("google goggles"), so its "Better it than me.", as in "better that it have to figure out sudoko, than for me to have to figure out sudoko".

If that's the case, then what's the point? Sudoku is a game. Having a computer tell you what to write in the spaces makes me wonder why you're bothering at all (unless you're using it as a learning tool).

No

[Anonymous Coward]

No, not really.

Re:No

[cayenne8]

I've been looking around.

How come there isn't a version of Goggles for iPhone yet?

Re:No

[dargon]

Grab the base google app for iPhone, it has goggles built into it

Re:No

[dissy]

Download "Google Mobile App"

When you are on the search screen, the top has a text box for search, as well as a mic icon and a camera icon, for voice and goggles search respectively.

Sudoku porn

[Quiet_Desperation]

Ever been frustrated when you can't solve a Sudoku

No. Never been unable to solve one. :)

Re:Sudoku porn

[Anonymous Coward]

Yes, I have. I then wrote a program to solve it (unoptimized, naive) and it told me, after 6 hours of calculation, that there were 8 possible solutions.

That was in a printed, paid-for magazine too.

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

[Anonymous Coward]

I'm going to assume that he brute-forced the entire grid to find all possible answers. There's no way why anything like that should take six hours.

Re:Sudoku porn

[JonySuede]

backtracking is not that naive
naive is usually a full deep first space search

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

Re:Sudoku porn

[Zebedeu]

That's because their generator used the naive way of generating a Sudoku puzzle: create a random complete puzzle from scratch and then start deleting random boxes.

I know that because back in the time I tried to do a generator myself. Turns out there's more to it than that.

Re:Sudoku porn

[Anonymous Coward]

I think Prolog is ideally suited for solving these problems. All you have to do is specify the game rule logic, the backtracking is already part of the interpreter.

(Not the GP AC.)

Re:Sudoku porn

[stealth_finger]

Ever been frustrated when you can't solve a Sudoku

No. Never been unable to solve one. :)

No, never tried to solve one. :p

Re:Sudoku porn

[maxwell demon]

Actually, the most naive implementation would just randomly fill the fields and then check whether it solves the puzzle, repeating until it found the solution. :-)

Re:Sudoku porn

[Anonymous Coward]

No. Never been unable to solve one. :)

http://www.kristanix.com/sudokuepic/worlds-hardest-sudoku.php

There you go.

Re:Sudoku porn

[FatdogHaiku]

What language did you write it in (not trolling here)?

klingon#

Re:Sudoku porn

[perryizgr8]

my highly unoptimized c code can do that in milliseconds. on a fucking ancient 800mhz core duo.

Re:Sudoku porn

[gknoy]

Somehow, I am both intrigued and frightened at the prospect of Klingon dialects of Perl.

Re:Sudoku porn

[Quiet_Desperation]

They're fun for a while, but once you figure out the techniques it gets old fast.

Re:Sudoku porn

[Quiet_Desperation]

D'oh. Blocked at my work!

Re:Sudoku porn

[Hognoxious]

Never been unable to, but then I've never solved one either.

Re:Sudoku porn

[adamdoyle]

Actually, the most naive implementation would just randomly fill the fields and then check whether it solves the puzzle, repeating until it found the solution. :-)

And that really could take six hours (or more) to compute.

Re:Sudoku porn

[UnknownSoldier]

Yeah, no kidding.  This is a Sudoku solver in less then 100 lines of C code that will solve any (solvable) board.

/. sucks ... breaking this posting up into multiple posts...

    #include <stdio.h> // gcc -DLOG=0 sudoku.c -O2 -o sudoku.exe
    #include <string.h> // memset

    typedef struct Board
    {
        char cell[9][9];
    } Board;

    void Print( Board* board )
    {
        int x, y;
        for( y = 0; y < 9; y++ ) {
            if (y && (y%3 == 0)) printf("---+---+---\n");
            for( x = 0; x < 9; x++ ) {
                if (x && (x%3 == 0)) printf("!");
                printf( "%c", board->cell[y][x] ? '0' + board->cell[y][x] : ' ' );
            }
            printf("\n");
        }
        printf( "\n" );
    }

    int GetInvalidMoves( Board* board, int x, int y ) // bitmask of invalid moves
    {
        int cx, cy, wx, wy, bMask = 0;
        cy = y; for( cx = 0; cx < 9; cx++ ) // horizontal
            bMask |= (1 << board->cell[cy][cx]);
        cx = x;    for( cy = 0; cy < 9; cy++ ) // vertical
            bMask |= (1 << board->cell[cy][cx]);
        wx = x - (x % 3); // 3x3 block
        wy = y - (y % 3);
        for( cy = 0; cy < 3; cy++ )
            for( cx = 0; cx < 3; cx++ )
                bMask |= (1 << board->cell[wy+cy][wx+cx]);
        return bMask;
    }

    int TotalEmptyCells( Board* board )
    {
        int x, y, nEmpty = 0;
            for( y = 0; y < 9; y++ )
                for( x = 0; x < 9; x++ )
                    if ( ! board->cell[y][x] ) // empty = !full
                        nEmpty++;
        return nEmpty;
    }

Re:Sudoku porn

[UnknownSoldier]

Part 2 of the solver since /. sucks for "junk characters"

    int Solve( Board* board ) // Recursive Brute-Force Solver
    {
        Board temp = *board;
        int nCells = TotalEmptyCells( &temp );
        int x, y, n;
        if( !nCells ) // trivial case - solved if no empty // if zero cells remaining
            return 1;
        for( y = 0; y < 9; y++ ) // while we have empty cells,
            for( x = 0; x < 9; x++ )
                if( ! temp.cell[y][x] ) // Find first empty // empty = !full
                {
                    int bInvalidMoves = GetInvalidMoves( &temp, x, y );
                    for( n = 1; n <= 9; n++ ) // iterate the empty cell with all possible candidates
                    {
                        if( ! (bInvalidMoves & (1 << n)) ) {
                            temp.cell[y][x] = n;
if( LOG ) printf("[%d,%d]=%c ", x+1,y+1,'0'+n);
                            if( Solve( &temp ) ) {
                                *board = temp; // propogate solution back to caller
                                return 1;
                            }
                        }
                    }
if( LOG ) printf("\n");
                    return 0; // No valid configurations for this board
                }
        return !printf( "No empty cells! Couldn't find solution for this board.\n" );
    }

    void Input( Board* board )
    {
        memset( (void*)board, 0, sizeof( Board ) ); // Clear()
        char *p = &board->cell[0][0];
        while (p <= &board->cell[8][8]) {
            int c = getchar();
            if ((c == '-') || (c == '_'))
                p++;
            else if ((c >= '0') && (c <= '9'))
                *p++ = c - '0';
        }
    }

int main( int nArg, char *aArg[] )
{
    Board board;
    Input( &board );
    Print( &board );
    Solve( &board );
    Print( &board );
}

Re:Sudoku porn

[oreaq]

The language doesn't really matter. Have a look at Peter Norvig's sudoku solver for a very elegant, small, and really fast implementation in python.

Re:Sudoku porn

[Jaxoreth]

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.

My solver takes less than half a second on 9x9 puzzles and finishes 16x16 ones in less than five seconds, running on an 800MHz PowerPC in Mac OS 9. It's written in Perl.

Then again, it's far from naive. Mostly it alternates between ruling out possible answers and deducing answers by elimination of other possibilities. When that runs out, it checks for saturation -- if cell A must be either 1 or 2 and cell B must also be either 1 or 2, then 1 and 2 are spoken for within any group containing A and B and can be ruled out for other cells in those groups. Then it checks every intersection of a box and a row or column -- any answers that can't be assigned outside the intersecting cells of one group can't be assigned to the other group outside the intersection either.

Finally, if that leads to a dead end, it looks for a cell with only two possible answers, and tries both hypothetically. If one leads to a contradiction, it's ruled out; otherwise, the new information obtained from each path is compared and anything deduced from each path independently is added to the original data set, using the logic that ((P -> Q) ^ (~P -> Q)) implies Q regardless of P. If necessary this could be generalized to cells with more than two possible answers, but I haven't encountered a puzzle where this was necessary.

This solver works on any NxN sudoku (where N is square), at least theoretically since after 25x25 you run out of letters. Goggles only recognizes 9x9, it seems.

who needs to think?

[starblazer]

Lazyness abounds....

Re:who needs to think?

[BrokenHalo]

Sometimes it seems as if the best and likeliest future for every member of the human race might be to shove a stick wand mixer through the top of everybody's skull to puree their brains, which can then be ingested though a straw, since that's all they're good for.

Let's face it: sudoku is purely a way to waste time. If you can't solve it, then put it down and find something else to do. I personally don't see why that should be so hard.

If we are so fucked that we have to have an app to waste time for us, then we might just as well never get out of bed.

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

So...?

[Anonymous Coward]

What's so exciting about this? Sudoku solvers have been around for ages. Personally I have even programmed one myself when I was 16...

Also, I'm sure Goggles isn't the first app to have this functionality.

Re:So...?

[Tetsujin]

What's so exciting about this? Sudoku solvers have been around for ages. Personally I have even programmed one myself when I was 16...

Also, I'm sure Goggles isn't the first app to have this functionality.

Yes. The Goggles, they do nothing that we haven't seen before.

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.

Re:Need more AI

[krou]

Funny thing is, if I don't believe it, that makes me imperfect, so ... ;)

Re:Need more AI

[PPH]

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

That's the final straw! If you slobs can't even watch your grammar, we can do without you.

-- SkyNet

Re:Need more AI

[Tetsujin]

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

That's the final straw! If you slobs can't even watch your grammar, we can do without you.

-- SkyNet

Hey, I'm not sure if I think what you're doing is right.

  -- John Henry

Re:Need more AI

[Anonymous Coward]

Died with a sudoku in his hand.

Re:Need more AI

[CapOblivious2010]

Seems to me that "SkyNet" would be the perfect name for an airline's on-board wifi system... yet oddly no one seems to use that name!

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

[Anonymous Coward]

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

You should have mentioned his book of already-solved sudoku (from the same episode) since it's more on topic.

Re:we hath defeated the purpose

[tverbeek]

Too on-the-nose.

Re:we hath defeated the purpose

[Ginger Unicorn]

now that's a contemporary reference...

Re:we hath defeated the purpose

[Anonymous Coward]

Solving Sudoku is trivial. The pattern recognition to read the puzzle is a bit more intriguing.

Re:we hath defeated the purpose

[Anonymous Coward]

I don't know... it's so day-before-yesterday.

Re:we hath defeated the purpose

[elashish14]

Why? Sometimes it's good to solve problems just for the sake of intellectual curiosity. Why do we even do Sudoku puzzles in the first place if there's nothing to be gained from solving them? And I mean, if you're, say, driving to work in the morning while solving the Sudoku (or maybe just taking the train), and then you arrive and have to go to work and just want to know what the solution is - well now you can have it and get on with your day (of course, having admitted bitter defeat and succumbing to puzzle-solving mortality).

And I think there's a lot that could potentially be gained from solving Sudoku via AI. What if more complex or heuristic problems could be modeled as solving a sudoku puzzle? And I can't imagine there's nothing to be gained in other fields - case studies and thought experiments in algorithms, threading, and so on. I can't imagine it was that hard to implement, just some signal processing to create the puzzle in memory and then applying some generic sudoku AI to solve it. And in the end, I guess the developers just wanted to have some fun and see what they could do. So no, I don't think it's totally useless

Re:we hath defeated the purpose

[Anonymous Coward]

Well the app could also check your answer or give you hints (instead of the full answer) when you get stuck.

Re:we hath defeated the purpose

[xtracto]

Weell... I remember back when I lived in the UK some newspapers gave free wine bottles to the first persons who solved Sudokus =o)...

Re:we hath defeated the purpose

[Zebedeu]

Pointless? It's all over the web.
Ok, maybe just the geek web, but still, at the very least it was a great marketing move.

Re:we hath defeated the purpose

[FrootLoops]

My aunt likes Sudokus but isn't terribly good at them. I could see her enjoying a hint every now and then without having to wait for the next day's paper or type it in to a computer. Then again, there's no way she'd use this setup without me or someone like me getting her into smart phones.

Re:we hath defeated the purpose

[wootcat]

True.

There's another app in the App Store that I think is far better than the Goggles version. It allows you to grab any printed Sudoku puzzle. The app then converts it and allows you to work on the puzzle on your iPhone. Great for those times you have a newspaper that isn't yours, or you are needing to leave for work and won't be taking the paper with you.

I really don't see the point of the Goggles version. I rarely (if ever) want to be given a complete finished grid. At most all I ever want are hints that lead me to solving it myself.

Re:we hath defeated the purpose

[antdude]

Was that the same crossword puzzle book that was in the last new episode? :)

Re:we hath defeated the purpose

[Anonymous Coward]

sounds like your aunt is a retard

Re:we hath defeated the purpose

[drinkypoo]

And I think there's a lot that could potentially be gained from solving Sudoku via AI.

Exactly what I was thinking. The value of logic puzzles is applying the structures you've built in your brain to other situations. Your brain says "hey this looks familiar" and BANGO you compute a near-optimal result and nip off to the pub to celebrate.

Re:we hath defeated the purpose

[jeremyp]

Sudoku is too easy to be a useful AI exercise. In fact, once you take into account all the symmetries including the fact that if you swap any two digits everywhere on the grid, you have the same puzzle (e.g. if you tur all the 2's into 5's and all the 5's into 2's), there are only about 45,000 different solved grids.

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

[timeOday]

Solving Sudoku is easy compared to the visual processing they're doing to recognize the puzzle from an image in the first place. I wonder how robust it is.

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

[timeOday]

Yeah, probably. But try implementing like that sometime, it isn't easy to make it really work well.

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

[Anonymous Coward]

I red a blog post from the guy who did this on the iPhone a while back. His algorithm was basically:
1. convert image to grey-scale
2. use flood fill to identify dark and light regions
3. detect edges to find the squares
4. use an neural net for OCR
5. run sudoku solver on extracted puzzle.

I'd expect this app does basicly the same thing (me even have been written by the same guy).

Re:Sudoku

[slim]

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.

You sound like you know what you're talking about. Sudokus which claim to be hand-created do generally seem more satisfying to solve. I assume, though, that creating them is machine-assisted in some way. Am I right? I'm imagining some sort of interactive grid editor which shows you the ramifications of your number placement, tells you when you've constrained the grid to a single solution, etc.

Re:Sudoku

[maxwell demon]

(me even have been written by the same guy).

You're an AI which has been written by the same guy who wrote the iPhone Sudoku solver?

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.

Re:Sudoku

[drosboro]

Hmm. I haven't heard of any software like that... but it sounds like that would be the way to go. When I was researching sudoku generation for my application, it looked to me like most of the "experts" were really just using pen and paper, working "backwards" from the solution to a puzzle. It would be really useful to have a program that would tell you things like "to solve this puzzle, you'll need to use 2 X-wings and a swordfish, and this squares can be solved right off the bat by simple elimination".

I haven't heard of such an app, but it would be an interesting challenge. Unfortunately, I suspect the market would be a bit on the small side.

Re:Sudoku

[DMUTPeregrine]

SudoCUE is/was (no longer developed it seems) about the best sudoku app around. It generates some excellent puzzles, can check for a unique solution, and has a nice way to rate difficulty. It also has an optimizer which can remove clues to make a puzzle harder, and can preserve symmetry. And SudoCUE does exactly what you wanted, it can list all techniques needed to solve the puzzle.

Re:Sudoku

[harl]

Solving sudoku is a trivial problem. High school level.

8 queens

Re:Sudoku

[KevinIsOwn]

Indeed, solving Sudoku is extremely simple. Break out your favorite constraint programming solver and a couple for loops and a bunch of all-different constraints later, you're done. This scales to any size sudoku puzzle and is rather fast.

Re:Sudoku

[TaoPhoenix]

The web is a wonderful place!

Try this site for solving by named strategies.

http://www.sudokuwiki.org/sudoku.htm

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

[courteaudotbiz]

I totally agree with you. But sometimes, when you're stuck and can't find another number, it would be cool that this app just gives you a hint, instead of solving the entire sudoku.

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?

Re:solving Soduku

[wondafucka]

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

No, the fun is developing an algorithm to process the image and then another one to solve it. Who cares if it robs the end user of enjoyment or purpose.

Re:solving Soduku

[sexconker]

I totally agree with you. But sometimes, when you're stuck and can't find another number, it would be cool that this app just gives you a hint, instead of solving the entire sudoku.

But if you make a mistake, you're fucked unless the OCR is smart enough to distinguish between the givens and your entries, and account for any scribbling, crossing out, etc. you've done).

Re:solving Soduku

[Anonymous Coward]

I wrote a simulating annealing program to solve this back in the day. Made sure it worked on my test suite of evil examples and never touched a Sudoku puzzle since.

CS

Re:solving Soduku

[agm]

As a software developer, it's more fun to look at Sudoku as a different sort of puzzle: how do I get a computer to solve it? Even if it's just using a brute force approach there is something satisfying about writing software in a low level language that solves these kinds of puzzles.

Re:solving Soduku

[IrquiM]

You obviously haven't been stuck in the middle of a puzzle!

Re:solving Soduku

[Intron]

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

Too easy. 12 lines of lisp. The true geek writes the program that generates the puzzles.

Stunning

[spywhere]

I just tried it with a Sudoku puzzle of "Evil" difficulty, and my iPhone 3gs solved it in about five seconds.
I grew up on Asimov, Clarke, and Heinlein, but this is truly science fiction.

Re:Stunning

[Anonymous Coward]

Yikes, that is evil.

Seriously, five seconds is a *long time* for a computer. Any computer.

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:Stunning

[geekoid]

most real intelligences can't create, I'm not sure why you have such lofty ideals for an artificial one.

Re:Stunning

[Tetsujin]

I just tried it with a Sudoku puzzle of "Evil" difficulty, and my iPhone 3gs solved it in about five seconds.

I grew up on Asimov, Clarke, and Heinlein, but this is truly science fiction.

Science Fiction? Really?

I mean, in terms of visual recognition the pattern of the puzzle is pretty rigidly structured - a grid of numbers, probably with lines. If the image recognition can deal with things like working around the user's attempts to solve the puzzle, that's pretty good - but there are much more impressive image recognition feats out there. (Maybe Kinect is a good example?)

In terms of problem solving... The problem is an easy one for a computer program to attack, and the problems aren't very large.

Re:Stunning

[Anonymous Coward]

So if I created a program to **create** (read: generate) sudoku puzzles, would that be considered "AI"? By your definition, of course ;)

Re:Stunning

[mr_gorkajuice]

False. It may not always be pretty, but I do not know a single person who can't create a doodle.

Re:Stunning

[Moryath]

"Real stupidity beats artificial intelligence every time.
        Terry Pratchett, Hogfather"

AI, in general, isn't what most people think it is. You can make a stupidly-hard-to-beat game where the opponent plays "perfectly" against you, with perfect timing and unencumbered by the physical constraints of a controller, and you get what happens in most of the Street Fighter series (or about any other fighting game), where the "hardest difficulty level" or end-boss is unbeatable, seems to always get off the perfect shot, block, tech hit, avoidance roll, etc, until you start abusing a game-breaking technique or bug yourself to beat the game. That's actually pretty easy.

What's harder is making a game AI that acts somewhat seemingly like real opponents, that makes real mistakes and leaves openings for the player to work with while not feeling like you're just handing them the game.

Of course, on most systems (Nintendo's underpowered consoles most of all), the designers don't even bother, they just code in whatever the AI they want and the altered difficulty levels give the enemy bigger guns, more health/armor, or just drop even more enemies in a level to chew through. Or else the difficulty levels leave the enemy alone, but screw with the player's health bar and damage output to much the same effect.

As we start dropping "AI" into other frontiers, it doesn't get much better. Translation AI is still relatively poor, able to handle some word-for-word translations passably but being lousy the moment you come across colloquialisms, figures of speech, neologisms, parallel synonyms, malapropisms, simply typos, failures of homonym (there/their/they're, our/hour, its/it's, principle/principal). There's a reason it's so easy to tell when you get a tech call response that's outsourced to somewhere in Asia - most of them know just enough Engrish to try to translate word-for-word what they want to say, and so they come up with constructions like "Tech support welcomes you, may I please know the problem you have today" that could just as easily come out of Babelfish or Google Translate.

For pure problem-solving and pattern-matching, AI's proceeding slowly. Maps and GPS routing have their benefits but are certainly not perfect yet. "Automatic response answers" chat stuff is best tossed in the garbage bin, usually right next to a company's crappily written FAQ page.

Re:Stunning

[ceoyoyo]

Image analysis counts as AI under the more generous definitions. Learning counts under most definitions.

Creating is easy. There are lots of programs that "create" music, or art, or whatever.

Re:Stunning

[circletimessquare]

"computers are useless. they can only answer questions"

-pablo picasso

Re:Stunning

[ClickOnThis]

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.

Precisely. The hardest part of the problem is processing the image into a Sudoku matrix in the computer memory. After that, solving the puzzle is trivial, for a computer anyway.

Just for fun, I once wrote a C program to solve Sudoku puzzles input via the keyboard. It was maybe one or two dozen lines long.

Re:Stunning

[peragrin]

Most of today's AI's are dumber than chimpanzees. A chimp can figure out if you want a termite then you need a stick. Today's AI couldn't come up with a stick unless it was programed into them and even only stumble on that answer randomly.

Computer AI either have to play with inhuman reflexes or by cheating(adjusting environment settings to suit them). That isn't an AI. It is a computer.

Re:Stunning

[ceiling9]

Creativity is often just finding a solution to an NP-hard problem, for example writing a song. Most people can tell if a song is enjoyable to listen to or not, but they can't necessarily write their own. They can listen to many songs and determine which are most pleasing. A songwriter has the special ability of assembling a song that meets the requirements of being pleasing by some method that is more efficient than simply testing each combination of random notes. Sudoko is similar, it is easy to verify that a given solution is correct. One solution method would be to keep testing different combinations of numbers until a solution is found, but there are more efficient methods using some heuristics based on the other numbers present, or experience from solving previous puzzles. The question might be whether there is something fundamentally more intelligent about things that humans create - songs, literature, etc, compared to a series a numbers in a Sudoko puzzle.

Re:Stunning

[Anonymous Coward]

Sudoku can be solved in a fraction of a second by standard constrained search. There is no problem solving needed at all.

Re:Stunning

[Trogre]

Detective Del Spooner: Human beings have dreams. Even dogs have dreams, but not you, you are just a machine. An imitation of life. Can a robot write a symphony? Can a robot turn a... canvas into a beautiful masterpiece?
Sonny: Can *you*?

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

[I8TheWorm]

goggles is pretty slick... but my $.02, I use Evernote for that and it does the same.

A not so strange coincidence, I'm working on jquery mobile at the moment... love those guys.

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

[Stooshie]

Make it so Number One!

Re:it really works, its quite amazing

[Abstrackt]

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

Re:it really works, its quite amazing

[Anonymous Coward]

I think I really messed up. I took a picture of Chuck Norris, sent it to Goggles and went to lunch. When I got back Google had crashed.

Re:it really works, its quite amazing

[takowl]

thanks google goggles

...thoggles.

Re:it really works, its quite amazing

[antdude]

More like stole your app ideas for them to use. Then, you get fired for leaking out work's confidential information!

There is no need for logic...

[Anonymous Coward]

I never understood the appeal of sudoku.

Sudoku puzzles are so simple that a simple brute-force approach is quick & easy. Sudoku was one of those programing 101 assignments from a while back.

Re:There is no need for logic...

[tukang]

Sudoku is an np-c problem (actually the hitting set problem or graph coloring problem), so it's "hard" by definition. It may be easy to brute force a small grid but the problem gets exponentially more difficult as you increase the grid size and brute-force quickly becomes extremely slow.

Re:There is no need for logic...

[slim]

Sudoku is an np-c problem (actually the hitting set problem or graph coloring problem), so it's "hard" by definition. It may be easy to brute force a small grid but the problem gets exponentially more difficult as you increase the grid size and brute-force quickly becomes extremely slow.

This is true, but it's just as NP complete whether you solve it by hand or by computer. Nobody's going to be publishing grids so large that a human can't solve it in reasonable time -- so it will always be easily solvable by a computer.

I'd say that the optimal algorithm is a bit more refined than "brute force" (which so me suggests "try every solution until it passes"). Prolog almost does it for you -- define the constraints in code, and off it goes into a depth-first search for the solution.

i like this trend

[mapkinase]

Next it will have my cake and simultaneously eat it. Sometimes I already feel that my computer does not need me, it can get busy or really busy by itself.

Re:i like this trend

[DrData99]

The cake is a lie!

Re:i like this trend

[Anonymous Coward]

The goggles, they do nothing!

Sudokus

[Monkeedude1212]

While I do enjoy a good Sudoku while on a long flight or perhaps while on the train, I've never understood everyone else's insatiable fascination with them. From a programming perspective, it's an easy puzzle to solve. All you need to know is the various techniques for solving a square. Though also from a computing standpoint, you could quite easily brute force your way through it in a few minutes, no doubt. And like the famous Rubiks Cube - you COULD essentially do it if you had enough memory to preform the pattern recognition, as there are truly only so many ways things can line up, once you look at them abstractly and not as individual numbers. Then you can have it rotated any of the 4 ways but basically, this is not that hard of an App to write, I'm wondering which approach it is they took.

I find it more fun to do with something less easy to work with. 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. I personally like a rainbow ROYGTBPVM of colours instead of numbers, it adds a bit of flavour to the challenge and lets me use up all those old school supplies. Not that I ever have them with me whenever I travel, but someone had the idea to throw one of those Sudoku puzzle books in a stocking one year and I pull it out on occaison when the power goes out and I need that mental interaction that video games provide.

Re:Sudokus

[kmdrtako]

...it's an easy puzzle to solve....

I presumed that the point was to activate the part of your brain that does things with numbers.

It's not so much that it needs to be an easy or hard puzzle to solve, just doing things with numbers---

Or has that been debunked now?

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

[Anonymous Coward]

http://www.youtube.com/watch?v=uTzjC4yTAqU that's how this works... without ocr

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.

Re:Sudokus

[tlhIngan]

I presumed that the point was to activate the part of your brain that does things with numbers.

It's not so much that it needs to be an easy or hard puzzle to solve, just doing things with numbers---

Or has that been debunked now?

It's not a number puzzle. It's a logic and reasoning puzzle.

People do crosswords too, and I'm sure there's also ways to have those solved by computers.

Last I heard a few months ago, Sudoku was being investigated as a possible way to transmit data or other thing as well - the math behind it is apparently quite interesting.

And people's facination isn't that computers make it trivially easy to solve, but just it's an interesting way to while away a few minutes of time that doesn't require staring at a screen. Computers can solve sudokus that are impossibly hard (by brute forcing, usually) for humans (the harest sudokus that are solvable are nowhere near how hard they can be).

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.

Re:Sudokus

[xtracto]

That's why I prefer Killer Sudoku, it introduces arithmetical complexity to the typical Sudoku game.

Re:Sudokus

[FrootLoops]

I'd like to think the GP meant "the part of your brain that does things with logic".

Re:Sudokus

[Monkeedude1212]

I suppose I see it as more of a logic problem , and while you could say that the foundations of logic are based on mathematics, I like to keep them seperate to help with parsing exactly whats going on.

One does not even need to understand addition to do a Sudoku, but you need to understand addition to do just about anything in Mathematics.

Re:Sudokus

[Anonymous Coward]

I think the GGP meant "part of your brain."

Re:Sudokus

[the_one(2)]

Sudoku is a variant of the graph-coloring problem which most certainly qualifies as CS and CS probably qualifies as math. Graph-coloring (and sudoku) is NP-complete btw.

Re:Sudokus

[harl]

Sudoku is just 8 queens.

Re:Sudokus

[azgard]

Wrong. It's graph coloring. Admittedly, 8 queens is also instance of graph coloring, but different one.

Re:Sudokus

[harl]

So it is 8 queens then.

Seriously?

[weltbrand]

Can't believe this... Pretty cool.

It's not AI

[Anonymous Coward]

It's just a parlor trick to impress your non-techie friends with. Even programming from scratch, it's not hard to write a program that can recognize printed numbers. Call me when it can actually learn!

wharrgarbl

[dsanfte]

Be common too place to the whatsit?

I am torn

[Conspiracy_Of_Doves]

Ok, its pretty amazing that this kind of thing is possible, but what is the point in using it? If you are going to just have your phone solve the puzzle for you, why bother picking up the sudoku in the first place?

Re:I am torn

[thesandtiger]

This application is nothing terribly exciting, but the idea of being able to take a picture on a cheap mobile device, that device being able to analyze the picture for content, decide it's a certain kind of thing, and then attempt to analyze and solve that kind of problem is pretty neat.

I could see applications of this that would examine, say, a pile of items and an empty space and then suggest an ideal packing strategy to fit them all most efficiently. Or, as someone who does a lot of "some assembly required" type projects, I could see IKEA wanting to use something like this where people could buy a thing, lay out the parts, take a picture of that part layout with their phone, and get video instructions showing them how to put it all together, in sequence, along with common mistakes. (Can you guess that I've broken or otherwise fucked up a number of IKEA assemblies?)

Lots of potential for ubiquitous real-time assessment and analysis of visual data, but yes, sudoku isn't terribly exciting.

Re:I am torn

[bickerdyke]

That's what I ask myself too...

Why pick up a sudoku in the first place?

I prefer the weekly crossword puzzle in "Die Zeit". That is still fun even if you use google/wikipedia to solve it.

Re:I am torn

[maxwell demon]

I prefer the weekly crossword puzzle in "Die Zeit". That is still fun even if you use google/wikipedia to solve it.

Actually a program to solve that would clearly qualify as AI.

Ken Ken - have you tried it?

[Anonymous Coward]

Now that's a math puzzle :)

"AI is getting just a little be too commonplace?"

[John Hasler]

It isn't AI. AI is whatever it is that machines can't do yet.

Re:"AI is getting just a little be too commonplace

[slim]

It isn't AI. AI is whatever it is that machines can't do yet.

It's a funny old term, AI. So much so that someone coined the term "machine intelligence" to mean what AI used to mean.

In pursuing machine intelligence, computer scientists developed a load of techniques which came to be generally useful for other purposes. LISP and Prolog came out of this. As it happens, Prolog is a very good choice of language if you ever want to write a Sudoku solver. And LISP is a good choice of language if you want to write an image recognition algorithm which processes photographs of Sudoku grids (which is the impressive part of this).

Accuracy?

[Cwix]

I just tried it on my phone and it had trouble recognizing some of the printed numbers. So It did the sudoku puzzle without all of the clues. It gave a correct answer for what it recognized, but it placed the wrong numbers in the places that it had left out a clue so the back of the book answer was wrong. It found the correct answer on the second try but it still dropped a clue on that one also.

Re:Accuracy?

[Metrathon]

i tried it on the puzzle in my newspaper - got a good shot of it but there were many numbers not filled in from the original puzzle and so the solution had nothing to do with the intended problem... The image recognition made the same mistakes on subsequent trials which surprises me.

Hey!

[LoudMusic]

Hey that's cheating!

Oh right, that's what Google is for.

Maybe You Could...

[GreenSeven]

Have your phone solve the puzzle before you start, don't look at it, solve it yourself and then use the phone to check your answer?? Just trying to think of how this is useful... But really, most of the time the puzzles come with the answer anyways...

Re:Maybe You Could...

[Tetsujin]

Have your phone solve the puzzle before you start, don't look at it, solve it yourself and then use the phone to check your answer?? Just trying to think of how this is useful... But really, most of the time the puzzles come with the answer anyways...

If it were a puzzle in a newspaper or something, the answer might not appear until the next issue.

Mostly I think the purpose of something like this is to impress onlookers with the power of one's (software-augmented) mighty Sudoken attack. It's also a testbed for future cybernetic implant versions.

Re:Maybe You Could...

[icebraining]

Checking if the rules are met isn't very difficult or time consuming; it probably takes less time than launching the app, taking the picture N times until it successfully recognizes it and wait for it to solve.
Besides, are all sudoku puzzles required to have only one solution? You might find a good solution that doesn't match the Goggles' one.

Re:Maybe You Could...

[slim]

Have your phone solve the puzzle before you start, don't look at it, solve it yourself and then use the phone to check your answer??

As with all NP-complete problems (by definition!) checking your answer is easy. It involves counting from 1 to 9, 27 times. In reality, if you've screwed it up, you'll find out in the course of solving it.

Re:Maybe You Could...

[maxwell demon]

With Sudoku, it's trivial to check if you have a solution, without being given the solution to compare with. Just check whether your alledged solution follows the rules. This is as easy as counting to 9 and checking the number is there, for each row, column and subsquare (actually you can even omit some).

Gentoo already did it

[korgitser]

Portage can solve sudokus in no time. Can't find the link now but just make ebuilds of the squares.

Re:Gentoo already did it

[Anonymous Coward]

Portage can solve sudokus in no time. Can't find the link now but just make ebuilds of the squares.

I think you mean Debian.

Though, it's completely missing the point: The fun part of this is the fact you just need to snap a quick picture without having to enter the values manually.

It is also fun

[RingDev]

Writing an application that can solve any Soduku you give it.

Both can be enjoyable.

-Rick

when I can snap a picture of my chess board...

[jbuck]

...and goggles gives me it's next move, I'll be impressed.

Re:when I can snap a picture of my chess board...

[slim]

When I can snap a picture of my chess board and goggles gives me it's next move, I'll be impressed.

Like with Sudoku, this can be divided into two problems: recognising the board, and solving the puzzle.

Choosing a reasonable chess move is something computers can already do well -- although it's much harder than Sudoku -- so that's fine.

It doesn't feel as if recognising a chess board is too far off, for a well chosen chess set in good lighting. I'd be surprised if someone hadn't already done it. Obviously it could already work well on the kind of board diagram you get in newspaper chess columns. One that would work on any old chess set in any lighting, from a dumb user's choice of angle -- that sounds hard.

Re:when I can snap a picture of my chess board...

[FrootLoops]

Harder than hard, sometimes it'd be impossible with a single picture. The user might cover up one piece (say, a pawn) with another (say, a king) from their bad angle choice. Depending on the other pieces you might not be able to infer the location of the covered pawn. Similarly a bishop could probably be blocked by a queen, which is even worse.

Sometimes *I* have trouble figuring out what piece is what on a chess set, like in this random crystal set. Because I know it's probably early-game I can figure out which piece is what after looking at it for a bit, but still, that one would be horrible to feed a chess board recognizer.

Machine Vision is the only 'AI' here...

[Vornzog]

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

I wrote a 'human' version of a sudoku solver on vacation a couple of years ago - on the flight between two Hawaiian islands. It would have been easier/shorter to write the recursive solver that will solve any sudoku board, but I wanted to write code that works the puzzle similar to how I do it by hand. There wasn't much there deserving of being called 'AI'.

The only thing vaguely AI about this is the 'Machine Vision' needed to recognize a sudoku board and ocr the numbers. I'm no AI expert, but since the board is a well-defined grid and the numbers are printed in a clean, bold, large computer font, it seems to me that most machine vision researchers could hack together to code to do this in an afternoon, made mostly from pre-existing code they had lying around anyway.

Don't get me wrong - I love my Android phone, I'm drooling at the prospect of upgrading to a faster one in the next year or so, Google Goggles is a sweet app (it impressed the hell out of my non-technical, non-gadget-loving sister, and that is hard to do), etc, etc.

But this isn't AI - this is sophomore algorithms homework, graduate-level (but not at all new) machine vision, and decent camera phone hardware. This isn't revolutionary, and it almost doesn't qualify for evolutionary. It comes closer to being inevitable. But think of how much more productive we can all be now that computers will solve all those pesky sudokus for us!

Re:"AI is getting just a little be too commonplace

[Chapter80]

It isn't AI. AI is whatever it is that machines can't do yet.

I'm glad you said that. So many people react immediately with "This isn't AI!", and you defined AI perfectly.

Is This Really AI & Developed By Eugene Varsha

[ClockEndGooner]

I think the question at the end of the post, "... AI is getting just a little bit too commonplace?" isn't relevant to using AI to solve a Sudoku puzzle. I thought part of the definition of AI was the ability for a system and/or application to dynamically adapt and learn and apply new rules based on previous input criteria and patterns where no known patterns exist? (http://en.wikipedia.org/wiki/Artificial_intelligence). Since each valid Sudoku puzzle should have one and only one solution, there are different well defined algorithms and or approaches to solve a Sudoku puzzle solely on the correct application of logical rules, does this really count as AI?

Nonetheless, I wonder if the Google Goggle Sudoku Solver was implemented by Eugene Varshavsky? ( Fraud Suspected At Sudoku Championship: http://www.npr.org/templates/story/story.php?storyId=114215648) {:-)

a future scenario

[thrillseeker]

A well dressed man infiltrates a Google data center after yet another night of single malt, high stakes card games, playing with gadgets, and a roll in the hay with an exotic lass. Needing to take down the center for not complying with his archaic sense of 'dishonor' in not forcing carriers to update their damn software, he quickly sketches out an unsolvable Sudoku puzzle, snaps a picture with his Galaxy S from Verizon still stuck on crappy Android 2.1, and sends it off to be (un)solved by the data center's machines. Alarms go off, geeks panic, and the magic smoke begins to leak out of everything. With a chuckle, he heads back to the hay wagon ...

NP-complete

[toxonix]

The AI part is image recognition of the grid and clues. That's interesting, but it's been done already. I'd like to know how they implemented the solver. The Soduku problem is considered NP-complete. Which is just about the only thing that is interesting about the puzzle. I've never bothered to solve one myself, since I don't think there is anything to learn from it. Actually implementing a solver might be an interesting waste of time though.

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:Fully-automated Sudoku solution

[Ksevio]

Should probably add a step where the pages are run through a printer where the answers are printed back on the page. Then you could just have the printer output directly to the recycling.

Re:Fully-automated Sudoku solution

[ustolemyname]

Wouldn't it be simpler to just copy the solutions pages at the back?

Re:Fully-automated Sudoku solution

[hellkyng]

Because step 7 wasn't "Profit!" I have to assume your solution is not commercially viable, please re-submit using appropriate meme for consideration. Also your solution reeks of completeness, a bit of uncertainty ( Step 6. ????) would further your cause.

Re:Fully-automated Sudoku solution

[Tetsujin]

Wouldn't it be simpler to just copy the solutions pages at the back?

But then I wouldn't have the fun of delegating the responsibility of the task of solving the problem.

Re:Fully-automated Sudoku solution

[Tetsujin]

Because step 7 wasn't "Profit!" I have to assume your solution is not commercially viable, please re-submit using appropriate meme for consideration. Also your solution reeks of completeness, a bit of uncertainty ( Step 6. ????) would further your cause.

That joke dates back to, what, 1998? I am not so in love with the Underpants Gnomes joke that I will do constant callbacks of it.

The Bus Pants Utilization

[Anonymous Coward]

Hey! Google stole this from last weeks episode of The Big Bang Theory. I'm tellin.

Re:"AI is getting just a little be too commonplace

[mr_gorkajuice]

Indeed. By that logic, I'd claim AI got too commonplace by the time I could carry an electronic device capable of multiplication.

Re:"AI is getting just a little be too commonplace

[Anonymous Coward]

by Google Goggles (2) on Tuesday January 11, @11:23AM

It isn't AI. AI is whatever it is that machines can't do yet.

I prefer the term "Artificial Person" myself.

Old technology, but very neat.

[impossiblefork]

This feels like the sort of logic oriented AI from the 1970s that involved expert systems, LISP, prolog and constraint satisfaction problems (a sudoku solver even used to be a mandatory assignment in a class on programming paradigms) and the OCR-part is, I think, not very novel either.

Taken all-together the thing does however look very polished and I suspect that we'll see much more like it in the future once the average programmer becomes more familiar with older research.

Seriously? That's the source?

[csagedy]

Is there a particular reason this links to the bowels of the web instead of, oh I don't know, the official Google blog on the subject?

Nothing new, Sudoku Grab for iOS already does this

[EMR]

The Sudoku Grab for the iphone has done this for quite some time..

Nothing new here, move long.

Wow. Great.

[Fishbulb]

Having a computer solve a mental exercise is like sending your robot to the gym to lift weights.

Re:Wow. Great.

[rockypg]

Getting a computer to solve a mental exercise is often times a greater and more fulfilling mental exercise.

Re:Just like "Sudoku Grab" on the iPhone has done

[slim]

I'm sure I've also seen a demo of an AR sudoku solver, which superimposes the solution onto video of the grid.

Old news for iPhone

[Anonymous Coward]

Sudoku Magic has been doing this since early 2009: http://phobos.apple.com/WebObjects/MZStore.woa/wa/viewSoftware?id=322457381

Still pretty neat, though!

Re:Is This Really AI & Developed By Eugene Var

[maxwell demon]

If it were true AI, I guess after pointing it to too many Sudokus it would refuse to solve yet another one due to boredom. :-)

Re:"AI is getting just a little be too commonplace

[Anonymous Coward]

I'm sorry, we're only granting one (1) non-human species person status this year.
You'll have to fight it out with the dolphins.

Prolog

[Anonymous Coward]

Prolog is fantastic for this class of problems:

See this excerpts from Seven Languages in Seven Weeks for the source code of a Sudoku solver in Prolog.

AI is getting to be just a little too commonplace?

[Anonymous Coward]

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

Does it please you to believe that AI is getting to be just a little too common place?

Tell me more.

linked above

[toby]

...and mod'd +5 informative by some incredible AI.

http://tech.slashdot.org/comments.pl?sid=1945980&cid=34836230

Now do that for competitive facebook grinders

[fleeped]

.. So that people cheat, others get frustrated by the cheats, all lose interest and maybe MAYBE some of them find something more interesting and productive to do.

Doesn't help when you are stuck

[John Marter]

Unless the app works better than demonstrated in the video this is not helpful for when you are stuck. By that time the puzzle is partially filled in and possible with wrong answers. In the video this was used only on a blank puzzle. And giving the answer would not be ideal. Better would be if it tells you which squares you need to erase. Or gives a hint for just one square.

pattern recognition?

[toby]

Usually search with backtracking.

AI

[Tom]

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

Uh, no?

Finding the solution to stuff that requires no creativity, lateral thinking, ethical judgement or other human qualities is what computers are freaking for. It frees our minds to tackle the tasks that computers suck at. Have we taken a time machine back to the 60s and are now all afraid that computers will replace us all?

Nothing new, Sudoku Grab for iOS already mentioned

[toby]

This post has been above for quite some time. http://tech.slashdot.org/comments.pl?sid=1945980&cid=34836230

Re:Is This Really AI & Developed By Eugene Var

[Siberwulf]

I was wondering the same thing. This isn't AI. This is OCR with a Sodoku solver. Tell me that it solves the puzzle without knowing it's a Sodoku, and we'll drop the AI word.

Re:Just like "Sudoku Grab" on the iPhone has done

[Java Pimp]

Cool. But neither of these fill in the puzzle automatically once it has the solution.

Is this really AI?

[wrencherd]

Just asking, but isn't the point of sudoku that it is solvable using only discrete logic?

Is it reading the digits and grid what qualifies this system as "intelligent"?

Re:"AI is getting just a little be too commonplace

[Jane Q. Public]

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

Precisely. There is nothing "AI" about this, in fact it's relatively simple. It's just a bit of OCR and some iterative math. Big deal.

A lot more often, I get the "feeling" that AI simply doesn't exist. I really despise the way the phrase is so often misused today.

Re:Just like "Sudoku Grab" on the iPhone has done

[Charliemopps]

But no one noticed because iPhone users don't play Sudoku.

Now the WholeFoods app was big news: http://www.wholefoodsmarket.com/iphone/
Then there's the Volvo app: http://www.commutegreener.com/
Then there's the Berkly app: http://www2.haas.berkeley.edu/News/Newsroom/2010-2011/100907iphone.aspx

Re:Just like "Sudoku Grab" on the iPhone has done

[harl]

An article on how he did it? Is that really necessary? It's a trivial problem.

Sudoku is the 8 queens algorithm; a stable of introduction to programming. Writing a program to solve sudoku is a high school level problem.

Not AI!

[Anonymous Coward]

Since when is "AI" a synonym for "generic computer program". I'm pretty sure this "AI" is merely following a fixed algorithm.

ObGrammarPolice

[harl]

That should be staple ya dork.

Re:Doodle

[TaoPhoenix]

Whoever Adrian Monk was modeled after.

Re:Frontiers

[TaoPhoenix]

I still have a pet theory that "if we really cared" we could have strong AI in about 5 years - we're just coming into the hardware specs needed.

However, we don't care, because it's a racial fear to have machines that can out-think us in "ordinary" things.

Same goes with the chat bot contests - if a serious team went to work, they'd build in defensive routines designed to slam the usual cheapos. "I took a plane to Hawaii but they airline didn't have any boats." "I screwed the Queen of England into a light socket." "What's bigger, a dreadnought or the economy of Zimbabwe?"

Same with translation, comps ought to be awesome at that - just build slang lists at the phrase level into the grammar parsing. But with only teams of 3-10 guys at a time, no wonder we can't make progress. We need a team of 400 and give them 7 years to do it.

In the news today

[wesleyjconnor]

Google extends their free app with cool functionality / Apple allows people to use their phone on a different provider....

im not trolling (the universal sign of trolling) but I found this interesting

Re:Songs

[TaoPhoenix]

Not all songs are NP-hard. Once again, we just haven't really bothered to make killer algorithms.

On a numerical note scale for a single octave, get the comp to play around with stuff like 666155455432432541 and pretty soon you have a song. That example was a mash of about 4 different top hit songs.

Obligatory mention...

[ysth]

Sudoku: The Pointless Puzzle

Re:Frontiers

[Anonymous Coward]

Same goes with the chat bot contests - if a serious team went to work, they'd build in defensive routines designed to slam the usual cheapos. "I took a plane to Hawaii but they airline didn't have any boats." "I screwed the Queen of England into a light socket." "What's bigger, a dreadnought or the economy of Zimbabwe?"

How does that make you feel?

Re:Just like "Sudoku Grab" on the iPhone has done

[TheLink]

What Word Lens does is more interesting than a sudoku solver: http://www.youtube.com/watch?v=h2OfQdYrHRs

Hardly new

[1s44c]

This is hardly new. I've been using OCR on and off for decades. I wrote a sudoku solver for 9x9 and 16x16 puzzles around 10 years ago and put it on the web for nothing when I realized that some slimeballs were charging to use a web based version.

I'll bet a whole load of slashdotters had more fun writing sudoku solvers than manually solving the puzzles.

On the NP-completeness of Sudoku

[jonaskoelker]

Graph-coloring (and sudoku) is NP-complete btw.

True. However, the argument emphatically isn't

Graph coloring is NP-complete. Sudoku is graph-coloring. Therefore, Sudoku is NP-complete. ... because "is" is used in two different senses in the two first occurences.

Consider the set of all 9-colourable graphs. There's a map, mapping every soluble sudoku instance to a 9-colourable graph. However, this map doesn't need to be surjective; there might be 9-colourable graphs that do not correspond to sudoku instances (for instance, by not having exactly 81 nodes).

The NP-completeness of the problem "is this graph an element of the set of 9-colourable graphs" doesn't directly translate to a statement about any subset of the set of 9-colourable graphs. For example, the empty set is such a subset, and deciding membership of the empty set is rather easy.

Re:Just like "Sudoku Grab" on the iPhone has done

[Anonymous Coward]

Which bit of "via the camera" are you unable to read?

Obligatory TBBT reference

[azgard]

Can it solve differential equations too? And recognize shoe vendors?

"I'm sorry, Dave, I just can't agree with that"

[TheLoneGundam]

"I'm sorry, Dave, I just can't agree with the idea that AI is getting too commonplace"

defeats the purpose.

[RockDoctor]

All properly constructed sudoku have a unique solution.

The challenge is in finding that solution.

If dealing with 3-sudoku (i.e. 3^3x3^2 grids), you should be able to solve it, if slowly.

4-sudoku (i.e. 4^2x4^2 grids) require either abnormal memory capabilities, or good record-keeping.

Does anyone have a source of 5-sudoku? I feel the need for a challenge.

Google googles...

[vikstar]

was written so that millions of chicks would send in pics of their breasts to search for comparisons. In terms of pics sent in to compare the sizes of body parts, most google engineers didn't not get what they were after.