BYU CS classes

To gain deeper experience programming in prolog, and to implement a simple sudoku solver.

Use the latest version of SWI-prolog, as in the previous prolog lab.

You will write a program in prolog that can solve 9×9 Sudoku puzzles. We've provided template code to help solve the problem. To solve this problem, fill in the procedure named solve.

Solve takes a list of nine lists. Each list represents a row in the puzzle. Each item in the list is either an integer 1 to 9 or an unbound variable.

You must meet the following requirements:

• You solution must be correct. So it will provide at least one solution if possible and fail when the board cannot be solved.
• Complete in a reasonable amount of time. This means about 10 seconds for the tests we run. The tests provided should complete in about a second.
• You must not use the clpfd library. The library was written around Sudoku, and a solution to Sudoku using the library is provided in the documentation.

You should turn in a single file consisting of your code.

The goal of Sudoku is to fill in all the empty squares of the grid with respect to the following constraints.

1. Each 9-Square row must contain all number 1 to 9 and be unique.
2. Each 9-square column must contain all number 1 to 9 and be unique.
3. Each 9-square 3×3 subgrid must contain all number 1 to 9 and be unique.

The idea is to implement a (mostly) naive solution, that follows this general pattern:

1. Bind each blank space to a number between 1 and 9.
2. Ensure no Sudoku rules are violated.
3. Repeat the previous two steps until a solution is found or we've tried all possible solutions.

• Whenever an integer is inserted into a blank space recheck the Sudoku constraints. The idea is to fail as quickly as possible to avoid extra work. The is_set/2 in the lists library (:- use_module(library(lists))) predicate should be useful.
• Check only constraints relative to changes made.
• Reprocess the board to so all columns and 3×3 sub-grids are immediately available in some data structures. The getCube/3 and columnAsList/3 helper functions are expensive.
• Instantiate blank squares form left to right, top to bottom. While not vital our test problems were chosen to run faster for algorithms that choose that order.