Course:CPSC312-2018-Sudoku-Solver

From UBC Wiki

Sudoku Solver

Authors:

Rui Zhang, Yanyun Bu, Wangzhou Yao

What is the problem?

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. There is one variant of the game called Killer Sudoku, which is a puzzle that combines elements of Sudoku and Kakuro. Sometimes the hardest ones 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.

What is the something extra?

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?

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 functional programming language.

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 Haskell.
  • We learned how to define our own data type in Haskell.
  • We learned how to implement Eq class for different types in Haskell.
  • We learned how to use Guard in Haskell.
  • We learned how to use backtracking in Haskell.
  • We learned how to do search in Haskell.

Links to code etc

https://github.com/buyanyun/CPSC312-sudoku