This shows you the differences between two versions of the page.
sc330_f2016:prolog2 [2016/10/27 03:44] dcostello |
sc330_f2016:prolog2 [2021/06/30 23:42] |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====Objective:==== | ||
- | |||
- | To gain deeper experience programming in Prolog, and to implement a simple Sudoku solver. | ||
- | |||
- | ---- | ||
- | ====Prerequisites:==== | ||
- | |||
- | Use the latest version of SWI-Prolog, as in the previous Prolog lab. | ||
- | |||
- | [[sc330_f2016:sudoku|Template code]] (described below). | ||
- | |||
- | ---- | ||
- | ====Deliverables:==== | ||
- | |||
- | You will write a program in prolog that can solve 9X9 Sudoku puzzles. We've provided **[[sc330_f2016:sudoku|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. | ||
- | |||
- | ---- | ||
- | ====Sudoku Explanation==== | ||
- | The goal of Sudoku is to fill in all the empty squares of the grid with respect to the following constraints: | ||
- | -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). | ||
- | -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). | ||
- | -Each 9-square 3x3 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: | ||
- | -Bind each blank space to a number between 1 and 9. | ||
- | -Ensure no Sudoku rules are violated. | ||
- | -Repeat the previous two steps until a solution is found or we've tried all possible solutions. | ||
- | |||
- | ---- | ||
- | ====Hints==== | ||
- | *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 3x3 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. | ||
- | * <code prolog>(nonVar(S00); var(S00), digit(S00), is_Set(Row0), is_Set(Col0), is_set(Cub0)) </code>, will check if a single square is correct. Do this for each spot, use lists and helpers to traverse through the board. | ||