Puzzles

The wide range of puzzles that have been devised to provide intellectual challenges and entertainment for humans can also provide

Sudoku

General Sudoku Resources

  • A wide selection of interesting videos on Sudoku and other puzzles (including many Sudoku variants and also cryptic crosswords) can be found on the Cracking the Cryptic YouTube channel. (They also produce software for doing Sudoku.)

Student Project Reports

Existing Software

  • Peter Norvig (co-author of the standard AI textbook Artificial Intelligence: a modern approach and Director of Research at Google had created a very nice Sudoko solver in Python. You can find the code with explanation on this page entitled Solving Every Sudoku.

  • Brandon's Man Meets Machine sudoku solver. This solves standard sudoku puzzles using a combination of rules commonly used by humans interleaved with the use of depth first search. Unfortunately there's not much documentation but hopefully the structure makes it clear enough what is happening. The top-level program is mmm_sudoku.py. At the end of the file you can see the code that selects the rules to be used and runs the solver using solve_range(start,end), where start and end are intexes into the global variable GRID_STRINGS which stores a list of Sodoku puzzles represented in a standard string format.

  • Software from Silvian Hu's project: Silvain-Hu-Sudoku.zip.

An algorithm known as Dancing_links has been found to be very effective for solving Sudoku puzzles. In fact, it seems that it can solve even the most difficult Sudoku's in a fraction of a second. It would be interesting to explore whether this algorithm can also work for other types of puzzle. Here are some relevant links:

Mazes

Previous Project Reports

These two projects both developed software for creating mazes that can have different levels of difficulty that can be used to adapt the challenge level of the puzzle to fit the player's ability. The projects are significantly different both in the maze generating algorithms that were used and in the style of the software that was produced.

Other Puzzles

The Undead Puzzle

  • Using AI to Solve Simon Tathan's Undead Game, Krishan Patel (2020) project report.