This shows you the differences between two versions of the page.
sc330_f2016:prolog2 [2016/10/26 16:38] wingated |
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. | ||
- | |||
- | ---- | ||
- | ====Deliverables:==== | ||
- | |||
- | You will write a program in prolog that can solve 9X9 Sudoku puzzles. We've [[sc330_f2016:sudoku|provided template code]] to help solve the problem. To solve this problem, fill in the procedure named ''solve''. | ||
- | |||
- | **[[sc330_f2016:sudoku|Template code]]** | ||
- | |||
- | ''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. | ||
- | |||
- | ---- | ||
- | ====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 number 1 to 9 and be unique. | ||
- | -Each 9-square column must contain all number 1 to 9 and be unique. | ||
- | -Each 9-square 3x3 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: | ||
- | -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. | ||
- | *Check only constraints relative to changes made. | ||
- | *Reprocess the board to so all columns and 3x3 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. |