Artificial Intelligence > Sudoku & Artificial Intelligence

Sudoku & Artificial Intelligence

By LEONARD MCGAVIN
Published: March 15, 2009

Sudoku puzzles - everyone's favourite number puzzle. Not only do people love them but they also like building algorithms to solve them. One novel approach was to use dpkg - which is an application dependency program. This is an amazing idea because dpkg is almost the perfect tool for Sudoku-like puzzles, but it is the least likely because of what it is renowned for in the technology world.

Whether using such approaches is considered as AI is debatable. What is interesting is how we can see the way our minds need to work to solve problems.

Easy Sudoku puzzles are solvable through backtracking, whereby dependencies are confirmed and the answer for a turn is 100% certain. This is the most common form of the puzzle found in newspapers.

The next level of difficulty sees a turn in the game where 100% certainty cannot be achieved because there is more than one possibility, and there are no better moves available. This requires a 'leap of faith' and this is one of the finer points that deserve a closer look.

The Leap of FaithIf you reach the point of a leap of faith you understand that you are just guessing between a small set of values where one must be correct. For a human this is a big ask. You are asking them to possibly mess up the puzzle they have worked on up until this point because they may now guess incorrectly. Not only this but it will force the person to look back over what they have done to make sure there are no mistakes, and that the leap of faith is the only option. The person will guess, and if they have played the puzzle correctly they will either win or lose because it has come down to a bad guess at the leap of faith.

For a person this event is stressful and undesirable. Perhaps this is the reason that easier Sudokus are more often found in newspapers. Most people don't like to be stressed and face issues of uncertainty.

To write an algorithm to check dependencies and determine the probability of each turn is fairly easy. To further write the algorithm to guess at the point of the leap of faith then roll back to try again if it fails is also fairly straight forward. To write an algorithm to brute-force a solution to the puzzle is possibly even easier - it may just take some time for the puzzle to be solved.

It has to be said that computers are much more suited to solving these problems than humans. The rules to the game are so logical. Computers themselves are masters of logic. The algorithms can be seen as intelligent forms but they seem to solve the problems with such mindless efficiency it’s hard to believe they are intelligent at all. The need for a leap of faith will stop some algorithms from solving the harder puzzles - like the dpkg example at the beginning of the article. But, the leap that is so hard for us can be made trivial with just a bit of forethought when designing the algorithm.

To be outdone by computers is to perhaps realise that computers have surpassed us. It may not be called AI when it happens but its effects will surely be noted

.

Any Comments?


More...

The Forever Web App Project

By LEONARD MCGAVIN
Published: November 15, 2009

The Forever Web App Project is an AI project to demonstrate a web app's ability to exist on the web unassisted (except by strangers) for as long as possible after a given date.

Internet Lifeforms

By LEONARD MCGAVIN
Published: March 5, 2009

The Internet may give us strange clues as to what the definition of life really is. Seeing Alex Dragulescu's visualisations you really begin to wonder.