Menu

[ IVLE ]

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

Homework #2I: Hashiwokakero in Prolog

Hashiwokakero ( 橋 をかけろ Hashi o kakero; meaning "build bridges") is a logic puzzle game that is similar to cryptarithmetic and Sudoku that we studied in CSP.

This game is played on a rectangular grid of cells. Each island has a number 1-8 that shows the number of bridges that connects this island to other islands. The goal is to connect the islands by drawing a series of bridges between the islands. The bridges must be built follow certain criteria:

An example Hashiwokakero puzzle and one of its two solutions is shown below.

You will be creating an agent to solve Hashiwokakero puzzles 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 Hashiwokakero puzzle above.

5 5
2.1..
.....
4.3.1
.....
3...2

The first line specifies the size of the grid in terms of its number of rows and columns (which will always be an odd number). The subsequent lines contains the grid, with each '.' or number representing a cell.

Output

Your program is to print out a solution grid, with the positions of the bridges indicated. The following characters stand for the four possible bridge types:

The solution to the above puzzle should thus look like:

2-1..
|....
4=3-1
|....
3===2

The inputs given to your program may not have a solution, may have a unique solution, or may have multiple solutions. 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.

Min's hints (as informed by our previous 2007 TA, Yee Fan Tan, whom helped with a similar puzzle assignment): Do not attempt this assignment in one sitting. It requires a much better understanding of Prolog than what we are able to completely cover in class and it requires you to practice. We recommend doing it over several milestones.

  1. You will probably need to use lists in your solution. Prolog will not automatically generate lists for you, you have to do it yourself. Do make sure you spend some time getting yourself familiar with lists. We suggest you do it in the first or second week of the assignment.
  2. One of the key points in Prolog is unification. Make sure you understand how this works so that you can form a more elegant solution for your submission. In the past, some students did not make good use of this key facility in Prolog.
  3. Try coding a simple puzzle of Hashiwokakero (perhaps the above example) in Prolog on your own first, before thinking about how to do it programmatically.
  4. Try to think of the different types of constraints needed to solve the problem. For example, the fact that all islands need to be connected is not as easy to translate, because it refer to a global property, rather than a local one. You may want to try to tackle a relaxed version of the Hashiwokakero problem without this property (and/or others) first, and think about how to add this transitive property in later.

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: 2010 November 4, 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.

Please note that you are to only use the primitives and libraries that come with SWI-Prolog. Other optional libraries that could be installed with prolog are not to be used. If you have any doubt, please ask on the forum.

Important Links

Here you can find a sample submission file contains a sample input and output helper applications. It also includes sample Hashiwokakero 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 (5.10) 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/bin/swipl. 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.
  5. If you're more of a lecture / video oriented type, you might try doing a lecture search on YouTube. There's a nice 3 part series on Prolog [1] [2] [3] from Prof. Dasgupta at IIT Kharagpur, who teaches the A.I. subject too but over a longer period than we do.

Hashiwokakero links:

  1. A brief description of Hashiwokakero can be found on Wikipedia. Has some hints on strategies, which you might code after you figure out how to encode the basic problem.
  2. You can encode as many test cases as you like, taken from Puzzle-Bridges.com, from which we will get some test cases to grade your assignment.
  3. The Japanese logic puzzle company, Nikoli, which invented the game, has a tutorial on Hashiwokakero.

Min-Yen Kan <kanmy@comp.nus.edu.sg> Wed Sep 26 00:00:00 2007 | Version: 1.0 | Last modified: Wed Oct 8 00:00:00 2007