The first task is to check the consistency of a partially filled Sudoku grid. A grid is said to be consistent if no positive number appears twice in a row, column, or a sub-grid. The grid is represented as a list of lists of non-negative integers, the latter lists being of equal lengths. The integer 0 represents a field which is not yet filled in. Positive integers represent fields that are filled in.

We now decompose the task of writing the predicate consistent/1 to some subproblems that can be implemented using a single Prolog predicate.

1. Let's start developing the program bottom up, i.e. by writing a predicate which does not depend on other predicates to be written.

   A good choice for such a base predicate seems to be the one checking that a list does not contain repetitions. A row is represented as a list, and both columns and sub-grids can also be transformed to lists (we will discuss it later), so you can use this predicate several times.

   Write a predicate which takes a list of non-negative integers as the only argument, and succeeds if, and only if, there are no two occurrences of the same positive integer in the list. You can write this predicate without using list handling built-in or library predicates, but then you will have to write an auxiliary predicate, which probably would be the same as one of the list handling predicates we discussed in class. So I suggest to use one of these pre-defined predicates. With a clever choice you can avoid writing recursive code alltogether, but a recursive solution is also OK.

   If you are going to use a predicate from library lists, you have to load the lists library by placing a line of the following form at the beginning of your Prolog program:

   :- use_module(library(lists)).

   Having written the predicate in question, test your program with some example queries.

   The predicate you wrote delivers just a "yes or no" answer, it does not bind any variables. For such predicates, the Prolog interactive top level does not give the user the option of exploring if there are any other ways in the program for arriving at a successful exit. Read the advice on this page, and repeat the successful tests in the form indicated there.

2. The next predicate is just a generalisation of the previous one in the following sense: it receives a list LL whose elements are lists of non-negative integers, and succeeds if, and only if, no element of the list LL contains two occurrences of the same positive integer. To implement this predicate, all you have to do is to call the predicate developed in step 1 for each element of the list LL.

3. You are now able to write the first working (although incomplete) variant of consistent/1. For this, first check out the documentation of the transpose/2 predicate from the lists library here.

   If you are using SWI Prolog, you can load the transpose from this file.

   Using the predicate developed in step 2, together with transpose/2, you should be able to write a version of consistent/1, which checks the consistency of rows and columns, but not of the sub-grids. Test this predicate using the examples in the description of the assignment. Also check that your solution does not produce multiple yes answers.

   To get some positive feedback, you can now submit your solution to ETS.

4. What remains now is to handle the sub-grids.

   There is a way to do that using higher order predicates instead of recursion, with some hints given here. However, you can also do that without higher order predicates, as described below and in point 5.

   Let us handle the subgrids in a bottom up way again.

   We start with a predicate which extracts the elements of a sub-square from a full grid. It receives the following arguments:
   • Input arg 1: the full grid, in the same form as consistent/1.
   • Input args 2 and 3: the row and column coordinates of the upper left corner of the sub-square to be extracted. To make the code simpler, the rows and columns should be numbered from 0.
   • Input arg 4: the size of the square to be extracted, i.e. the number of rows and columns the square should have.
   • Output arg (arg number 5): the elements of the square extracted, in the form of a single list. The order of elements of this output list should not matter.
   This predicate can be implemented without recursion, using the following predicates from library(lists): transpose/2, sublist/5, append/2.

5. Let's number the sub-grids starting from 0 and counting from left to right and from top to bottom. For example, the sub-grids of a classical 9x9 sudoku are numbered as follows:

   ---------------------------------------- | | | | | | | | | 0 | 1 | 2 | | | | | | | | | |------------|------------|------------| | | | | | | | | | 3 | 4 | 5 | | | | | | | | | |------------|------------|------------| | | | | | | | | | 6 | 7 | 8 | | | | | | | | | ---------------------------------------- The next predicate takes the full Sudoku grid, the size of sub-grids, and a serial number of a sub-grid, as defined above. It decides if there are repetitions in the sub-grid with the given number. This predicate can be defined without recursion, by doing some arithmetic, and using the predicates defined in steps 4 and 1.

6. The final step involves writing a procedure that calls the predicate defined in the previous step for all sub-grids.

   By inserting a call to this predicate into consistent/1 one obtains a full implementation. This invocation has to be preceded by some further calculations: you have to obtain the size of the grid (preferably using the built-in predicate length/2, or by copying in the list_length/2 predicate from your practice solutions). You also have to calculate the size of the sub-grid, a hint for how to do this is given at the end of the description of the assignment.

Last modified by Péter Szeredi, szeredi@cs.bme.hu, on 11.11.2018.