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.

Template code (described below).

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:

• Your solution must be correct. (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. This requirement is not extremely rigid. With appropriate use of Prolog lists as shown in lecture, this shouldn't be a worry.)
• 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 numbers 1 to 9 (9 squares and 9 required numbers means no duplicates can exist in a row).
2. Each 9-square column must contain all numbers 1 to 9 (9 squares and 9 required numbers means no duplicates can exist in a column).
3. Each 9-square 3×3 subgrid must contain all numbers 1 to 9 (9 squares and 9 required numbers means no duplicates can exist in a subgrid).

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.
• Only check constraints relative to changes made (to be faster).
• Reprocess the board so all columns and 3×3 sub-grids are immediately available as data in some structure(s). The getCube/3 and columnAsList/3 helper functions are expensive and should not be repeated often.
• 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.