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 | ||
|
sc330_f2016:prolog2 [2016/10/26 17:02] jhansen |
sc330_f2016:prolog2 [2021/06/30 23:42] (current) |
||
|---|---|---|---|
| Line 7: | Line 7: | ||
| 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''. |
| - | **[[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. |
| - | + | ||
| - | ''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:\\ | ||
| Line 38: | 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 **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. |
| - | *Only check constraints relative to changes made (to be faster). | + | * 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 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. | + | * 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.1477501355.txt.gz · Last modified: 2021/06/30 23:40 (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
