Course:CPSC312-2018-KillerSudokuPrologVersion

From UBC Wiki

Killer Sudoku Solver[edit | wikitext]

Authors: Rui Zhang, Wangzhou Yao

What is the problem?[edit | wikitext]

There is a variant of Sudoku called Killer Sudoku, which is a puzzle that combines elements of Sudoku and Kakuro. Sudoku is a logic-based, combinatorial number-placement puzzle whose goal is to  fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also called "boxes", "blocks", or "regions") contains all of the digits from 1 to 9. The objective of the game Kakuro is to insert a digit from 1 to 9 inclusive into each white cell such that the sum of the numbers in each entry matches the clue associated with it and that no digit is duplicated in any entry. Sometimes the hardest killer sudoku can take hours to crack. The player needs to fill in the partial filled board. The goal of our project is to design a solver that can solve the Killer Sudoku whenever there is solution available. If there is no solution at all, then we will return no solution. In this Prolog version of the game, we are basically reform the game that we  previously designed in Haskell so that it is more efficient and elegant.

What is the something extra?[edit | wikitext]

Instead of traditional Sudoku, our project Killer Sudoku is more sophisticated and interesting. The constraints that Sudoku have will still need to be satisfied in the Killer Sudoku. Other than that, this game also requires constraints on each cages to satisfy a specific sum that is indicated in the game. This constraint is borrowed from Kakuro. By imposing this additional constraint, the puzzle just becomes way more interesting. Also, we did some optimizations which involving arc consistency and pruning domains so that our Killer Sudoku Solver will be more efficient and elegant.

What did we learn from doing this?[edit | wikitext]

From High level point of view,

We learned how to prune domain

We learned how to impose arc consistency,

We learned how to search efficiently in prolog.

From Low level point of view, we learned a lot as well.

We learned how to implement the show class for the structure that we defined in prolog.

We learned how to define our own data type in prolog.

We learned how to implement Eq class for different types in prolog.

We learned how to use Guard in prolog.

We learned how to use backtracking in prolog.

We learned how to do search in prolog.

Links to code etc[edit | wikitext]

https://github.com/wxwszr/sudoku-prolog