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 be efficient by failing as quickly as possible to avoid extra work. The is_set/1 in the lists library :- use_module(library(lists)). predicate should be useful.
• 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.
• The code

  (nonvar(S00); var(S00), digit(S00), is_set(Row0), is_set(Col0), is_set(Cub0)) 

  will check if a single square is correct, where S00 is the spot at (0,0) and Row0, Col0, and Cub0 are the first row, col, and cube respectively. You shouldn't explicitly make variables for each of them, but access each space recursively. Do this for each spot, and use lists and helpers to traverse through the board.

If your code takes longer than a minute to run, consider the following ideas:

• Preprocess 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.
• Only check constraints relative to changes made.