Menu

[ IVLE ]

[ Overview ]
[ Syllabus ]
[ Grading ]
[ Homework ]
  [ HW 1 ]
  [ HW 2T ]
  [ >HW 2I ]
[ Misc. ]

Homework #2I: Light Up in Prolog

Light Up is a logic puzzle game that is similar to cryptarithmetic that we studied in CSP.

This game is played on a rectangular grid of black and white cells, and the objective is to place light bulbs in the white cells so that all the white cells are lit up. A light bulb sends light rays left, right, up and down, lighting up white cells along its row and column until the ray is blocked by a black cell. If a black cell has a number k (from 0 to 4) on it, then there must be exactly k light bulbs on the four white cells that are directly adjacent to it. Light bulbs that are diagonally adjacent to a numbered black cell do not contribute to its count. When a black cell is unnumbered, there are no restrictions on the number of light bulbs that can be placed on the cells adjacent to it. Finally, no two light bulbs is allowed to shine onto each other.

An example Light Up puzzle and its solution is shown below.

You will be creating an agent to solve Light Up puzzles, and your job is to implement a Light Up solver using Prolog. Prolog is a great language for solving constraint satisfaction problems and can handle these problems with relative ease. Prolog already has an inference engine capable of solving CSPs efficiently. Your job is to encode this assignment in a way that translates the problem effectively. To do this you will have to learn more about Prolog and how it represents constraints and programs.

Technical Description

Input

Your program will be given a text file as input, and asked to solve it. The text file will look like this for the sample Light Up puzzle above.

4 4
...#
.21.
.2..
#.#.

The first line specifies the size of the grid in terms of its number of rows and columns. The subsequent lines contains the grid, with each character representing a cell. White cells are represented by '.' (dot), unnumbered black cells will be labeled with '#', and numbered black cells will be labeled with the number itself.

Output

Your program is to print out a solution grid, with the positions of the light bulbs indicated by the letter 'L'.

.L.#
L21.
.2L.
#L#L

The inputs will always have a solution. If there are multiple solutions, any solution will be accepted.

Tricks and Tips

Prolog is great at CSPs, but pretty lousy when it comes to input and output. You should create helper programs in another imperative language to transform the input file into constraints to be added to the knowledge base. Then run Prolog on the output of the program. Process the output from Prolog using a second helper program to get it into the correct format for output. Sample input and output processors have been written for you (in C), if you choose to use it. The sample output processor requires both the original file and the output of the Prolog run to produce the final output.

Your pipeline should look like this:

Homework 2I pipeline

You should install SWI Prolog (see links at the end of this assignment as soon as possible or (better yet) do your assignment on sunfire, where it is already installed for you. Follow a simple tutorial to get started on how to program in Prolog. This may take you about 1-2 hours on its own.

Grading and submission formatting

The following submission guidelines is very similar to the HW1 guidelines. For us to grade this assignment accordingly, we need you to adhere strictly to the following submission guidelines. They will help us grade the assignment in an appropriate manner. You will be penalized if you do not follow these instructions. Your matric number in all of the following statements should not have any spaces and any letters should be in CAPITALS. You are to turn in the following files:

These files will need to be suitably zipped in a single file called submission-<matric number>.zip. Please use a zip archive and not tar.gz, bzip, rar or cab files. Make sure when the archive unzips that all of the necessary files are found in the current directory (please do not nest your files in internal folders). Upload the resulting zip file to the IVLE workbin by the due date: 2007 November 5, 11:59:59 pm SGT. There absolutely will be no extensions to the deadline of this assignment. Read the late policy if you're not sure about grade penalties for lateness.

Important Links

Here you can find a sample submission file contains a sample input and output helper applications. It also includes sample Light Up grids and their outputs. You will have to modify at least the sample input helper application or write your own.

Prolog links:

  1. Here's Min's attempt at a Prolog tutorial. Enjoy!
  2. SWI Prolog home: This is a free, LGPLed version of Prolog that you will need to install for this assignment. If you don't have access to a computer with administrative rights, let us know.
    There is a working version of SWI Prolog on sunfire that you can use if you choose to do this assignment in the Sun Solaris UNIX environment. It is located at /home/rsch/rpnlpir/tools/languages/programming/pl/bin/. You should place this in your PATH environment variable.
  3. A local version of the reference manual for SWI Prolog. Highly technical.
  4. A Google search for tutorials on Prolog.

Light Up links:

  1. A brief description of Light Up can be found on Wikipedia.
  2. Nikoli has a tutorial on Light Up.

Yee Fan Tan <tanyeefa@comp.nus.edu.sg> Wed Sep 26 00:00:00 2007 | Version: 1.0 | Last modified: Wed Oct 8 00:00:00 2007