sc330_f2016:prolog2
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
|
sc330_f2016:prolog2 [2016/10/26 16:37] wingated |
sc330_f2016:prolog2 [2018/10/26 02:02] morse |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====Objective:==== | ====Objective:==== | ||
| - | To gain deeper experience programming in prolog, and to implement a simple sudoku solver. | + | To gain deeper experience programming in Prolog, and to implement a simple Sudoku solver. |
| ---- | ---- | ||
| ====Prerequisites:==== | ====Prerequisites:==== | ||
| - | Use the latest version of SWI-prolog, as in the previous prolog lab. | + | Use the latest version of SWI-Prolog, as in the previous Prolog lab. |
| + | |||
| + | [[sc330_f2016:sudoku|Template code]] (described below). | ||
| ---- | ---- | ||
| ====Deliverables:==== | ====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''. | + | 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. | + | ''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 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. | + | *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. | + | *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 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. | You should turn in a single file consisting of your code. | ||
| Line 24: | Line 26: | ||
| ---- | ---- | ||
| ====Sudoku Explanation==== | ====Sudoku Explanation==== | ||
| - | The goal of Sudoku is to fill in all the empty squares of the grid with respect to the following constraints. | + | 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 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 number 1 to 9 and be unique. | + | -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 number 1 to 9 and be unique. | + | -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: | The idea is to implement a (mostly) naive solution, that follows this general pattern: | ||
| Line 36: | Line 38: | ||
| ---- | ---- | ||
| ====Hints==== | ====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. | + | * 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/1'' in the lists library '':- use_module(library(lists)).'' predicate should be useful. |
| - | *Check only constraints relative to changes made. | + | * 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. |
| - | *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. | + | * The code <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, 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. |
| - | *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. | + | |
| + | ===Tips to Make Faster (if needed)=== | ||
| + | If your code takes longer than a minute to run, consider the following ideas: | ||
| + | *Preprocess 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. | ||
| + | *Only check constraints relative to changes made. | ||
sc330_f2016/prolog2.txt · Last modified: 2021/06/30 23:42 (external edit)
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
