Course:CPSC312-2016-Project1-Sudoku

Sudoku

Authors: Andrew Pang, Yun Meng, Mike Lee

What is the problem?

Sudoku is a classic game where a grid of 9x9 is divided into 9 subgrids of 3x3, and in each row, column, and subgrid can only contain but also must contain the numbers 1-9 once. We will attempt to generate a sudoku game of simple difficulty using Prolog and see if Prolog 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 Prolog solve it too.

- We will attempt to see if we can create a smarter algorithm/method to solve the Sudoku puzzle.

What did we learn from doing this?

We learned that Prolog can be used to solve a Sudoku puzzle, even ones that are considered to be difficult.

We also noticed Prolog is slow in solving logic-based games/problems when a bruteforce method is used. The program solves the puzzle fairly quickly when some elements from each square is missing. Nevertheless, when several rows/columns/squares are missing, it may take up to several minutes to solve the puzzle. A typical sudoku puzzle has over half the numbers missing, whereas our test attempts only tried up to a third of the numbers missing. 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 has columns of a Sudoku puzzle as parameters, and the second one has squares of a Sudoku puzzle as parameters. The second implementation was significantly faster than the first one. It is suspected the first one is slower because extracting rows from columns is costly than extracting rows and columns from squares.