Hour Maze

This assignment consists in solving the Hour Maze puzzle (see here an online game),  and described as follows. We have a grid of m columns by n rows where m x n is a multiple of 12. Each cell of the grid must be filled with one valid clock hour, from 1 to 12. The initial configuration provides some fixed cell values. Besides, each cell grid may be connected to each adjacent cell (looking up, down, left or right) or separated by a wall. The final configuration must satisfy the following constraints:

1. To fill the grid, we must use each hour value a fixed number of times given by (m x n)/12.
   
2. The hours of two adjacent, connected cells must be consecutive, either clockwise or anticlockwise
   

The first constraint means that, for instance, with 6 columns and 4 rows, we have 24 cells, and so, we must use each hour value 24/12 = 2 times. Similarly, for 6 columns and 6 rows, we must use 3 copies of each hour value. An example of initial configuration and the corresponding solution can be seen below.

Figure 1. Initial configuration	Figure 2. Solved puzzle

We will encode the scenario both as a SAT problem and as an ASP program.

1. SAT: write a program called hourmaze in any programming language of your choice (C, java, python, caml, prolog, etc) and used as:
   
   hourmaze <inputfile>
   
   This takes an ASCII file <inputfile> with the initial grid where the 2 first lines contain the number of rows and columns, and then it is followed by a grid configuration like this:
   

   6 4 1 x x|x x x -     - x x|x 5|x|x   - - - x|x 7 x x|x     - - - x x x x x 9

   
   so each x represents a cell where to place an hour and vertical and horizontal rows are respectively represented as | and -. For simplicity, hour values with 2 decimal digits (10, 11, 12) will be represented in the ASCII files using their corresponding hexadecimal digits, A, B, C. The input file shown above corresponds to the initial configuration in Figure 1. Your program will generate a DIMACS file (as explained in class) and make an external call to clasp to get a solution. It will also decode back the clasp output and print the complete solution. For instance, for the solution shown in Figure 2, the corresponding output file would be:
   
   

   123CBC 2145AB 36789A 456789

   
   Help code: this C function prints all combinations from m elements {0,...,m-1} taken in groups of n.
   
   ASP: write an ASP encoding of the same problem and use clingo to solve the puzzle. Warning: the ASP code must be kept in a standalone (set of) file(s), not embodied in C or python code.
   

File examples.zip contains a set of benchmarks of different sizes where domX.txt is the input file and solX.txt its corresponding solution.

Assessment & delivery