Did a computer really solve a Sudoku puzzle?
Those of us who write headlines for a living know that from time to time a really good pun or catchy phrase may win out over pure accuracy. The Browser suspects that something like this happened over at the august headquarters of Scientific American. An article posted yesterday on the SA site carried the headline "First 'Commercial' Quantum Computer Solves Sudoku Puzzles." It's a fascinating story about a Canadian company called D-Wave testing a "quantum" computer, which has digital bits that can apparently grasp something as 1 and 0 at the same time, and thus in theory take on more complex tasks than ordinary computers.
But if you read through the whole article, it doesn't actually say that the computer "solved" a Sudoku puzzle. What the writer said is this: "The quantum computer was given three problems to solve: searching for molecular structures that match a target molecule, creating a complicated seating plan, and filling in Sudoku puzzles." Nowhere does the article say that the computer actually FINISHED the puzzle, much less finished it with its unique correct solution. And the company's press release makes no mention of Sudoku at all. (The Browser is awaiting comment from D-Wave on this matter). And besides: as complex as Sudoku puzzles may be (I interviewed Wayne Gould a couple of years back; he spent seven years writing proprietary software that can create a near-infinite number of Sudoku puzzles), since when is solving one meant to be a benchmark for artificial intelligence? (UPDATE: A number of readers have noted in comments below that there are programs available for download that solve Sudoku puzzles. This reinforces the point: why are SA and a number of bloggers focusing on this apparently mundane accomplishment?) After all, IBM's (IBM) Deep Blue beat chess grandmaster Garry Kasparov in a six-game match back in 1997. Maybe I'm wrong, but I think chess is significantly more complicated than Sudoku. Perhaps the distinction here is that D-Wave is talking about a commercially viable computer, which Deep Blue isn't. But even so, I think Scientific American is overhyping this development, even if unintentionally. Sudoku, in fact, a far easier problem to solve for the computer. It is a very simple constraint satisfaction problem. Chess, on the other hand, requires the computer to make assume that the opponent is going to make a best possible move and then make decisions for its moves.
Inasmuch as (unlike chess)there is an absolute, finite number of possible values in Sudoku, it requires neither a supercomputer nor artificial intelligence to solve: I can
set up a Basic program to solve the simplest sets in about ten minutes. The complex relationships might require more elegant logic. Sudoku puzzles are easy to solve. I only spent a weekend to finish a program to solve easy to moderate to difficult Sudoku puzzles. Since then I lost my interest in Sudoku. It doesn't require much CPU time either.
What am I missing....aren't Sudoku puzzles just simultaneous equations? If so,wouldn't that be fairly straightforward for a math program?
Dr. Dobbs Journal published an article by Eytan Suchard, Raviv Yatom, and Eitan Shapir where graph theory was used in an application to solve sudoku. The on-line repository includes a Windows executable and its source code. I've used this program on my laptop to solve all levels of sudoku problems.
The achievement is not the complexity of the problem but the advanced technological base of computer - quantum principle. Until recently those computers just did not exist. And potential is huge.
One oversimplified explanaion of Quantum computing is that it tests all possible solutions simultaneously, then 'collapses' to the correct one. Solving a Sudoku puzzle in this manner would be a significant event, even if it isn't a mainstream AI grand challenge. As you note, they aren't making that claim.
The type of problems a quantum computer can solve in seconds would take Deep Blue's big brother (Deep Blue Gene/L the current fastest computer in the world) years.
The AES encryption cypher, for example, with it's 256 bit key would take Deep Blue Gene/L, theoretically, millions of years to crack. An appropriately configured quantum computer with as few as 256qubits should crack it in a matter of weeks. Sudoku puzzle is not the main point here, the main point is here they have a "quantum computer" that actually works... Anyone can write a program to solve Sudokku in a day or less (or a lot less depends on how good you're).
There is a nice little program that can be downloaded free and istalled on any computer that can solve these puzzles in the blink of an eye.
For your information, quantum computers have just learnt how to do sum of two integer numbers. Sodoku puzzle is still in the promisin future.
I have a Visual Basic program which solves a Sudoku puzzle in less that one second and most of that time is spent formatting the solution for printout.
I would guess you are not a computer scientist. You missed the point entirely. The point is that they are working on a computer that is not a binary computer at all. The quantum nature of the computational device is what this is about, not the type of problem solved. D-Wave's point is that quantum computers can be used to correctly solve math problems. Quantum computing is much more advanced in principle than binary computing and this proof is a necessary step in its development.
CNNMoney.com Comment Policy: CNNMoney.com encourages you to add a comment to this discussion. You may not post any unlawful, threatening, libelous, defamatory, obscene, pornographic or other material that would violate the law. Please note that CNNMoney.com makes reasonable efforts to review all comments prior to posting and CNNMoney.com may edit comments for clarity or to keep out questionable or off-topic material. All comments should be relevant to the post and remain respectful of other authors and commenters. By submitting your comment, you hereby give CNNMoney.com the right, but not the obligation, to post, air, edit, exhibit, telecast, cablecast, webcast, re-use, publish, reproduce, use, license, print, distribute or otherwise use your comment(s) and accompanying personal identifying information via all forms of media now known or hereafter devised, worldwide, in perpetuity. CNNMoney.com Privacy Statement.
|
|
| 
