Course:CPSC312-2016-Project2-Sudoku
Sudoku
Authors: Mike Lee, Yun Meng, Andrew Pang
What is the problem?
We are going to reimplement the Sudoku program that we did in Prolog. We will attempt to generate a sudoku game of simple difficulty using Haskell and see if Haskell can solve it. We will begin with trying a bruteforce method to solve and see the feasibility of it.
What is the something extra?
- We will attempt to see if we can create higher levels of difficulties for Sudoku and have Haskell solve it too.
- We will attempt to see if we can create a smarter algorithm/method to solve the Sudoku puzzle.
- We will use sequence data structure.
- We will have the program print the solution in the format of the puzzle and also output it to a txt file.
What did we learn from doing this?
We learned that Haskell can be used to solve a Sudoku puzzle, even ones that are considered to be difficult.
We also noticed that Haskell is not very fast in solving logic-based games/problems. Although it is slightly faster than the Prolog implementation, it may take a long time to solve the puzzle when 35 or more numbers are missing. A typical sudoku puzzle has over half (40) the numbers missing, so a full puzzle may take well over a day to solve and is therefore unfeasible to use, or feasible for the lazy.
Two implementations were made. The first one uses lists and a simple algorithm to replace blanks. It finds all permutations of the missing numbers and tries each one until it works. The second implementation uses sequences and a better algorithm to replace blanks. It examines the row, column, and square of a missing element and saves the possible numbers that could fit to a sequence. After this is done for every element, the sequences are combined and saved to another sequence. Then, the program will keep filling the puzzle with a combination from the sequence until it works. The second implementation is significantly faster than the first one as it uses a faster data structure for replacing elements and a better algorithm.