Differences

This shows you the differences between two versions of the page.

--- sc330_f2016:prolog2 [2018/10/26 02:02]
morse
+++ 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/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 <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.
-===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.

BYU CS classes

User Tools

Site Tools

Differences

Page Tools