Homework 4. Hess-style puzzle solver
Consider the following puzzle, written by Richard I. Hess in the Brain Ticklers section of the Winter 2010 issue of The Bent of Tau Beta Pi. "Fill in the following cross-number puzzle with 13 different three-digit perfect squares. No leading zeros. Read top-to-bottom and left-to-right as in a crossword puzzle."
In the above diagram, each letter represents a single base-10 digit of a number. For example, the middle entry LMN represents a three-digit square, whose first digit L is nonzero, and whose second and third digits are M and N, respectively. The digits need not be distinct, but the entries must all be distinct.
We'd like to have a program that solves cross-number puzzles of this form, in which every entry in the puzzle is a distinct square integer. However, this one is pretty simple, so let's generalize it in several ways. First, let's not assume base 10, but instead solve the problem in other bases. Second, let's not assume the numbers are three-digit squares: the numbers can have any positive number of digits (though they must still be squares). Third, the user should be able to specify any rectangular puzzle layout, not just this particular one.
Write a predicate that takes two arguments. is an integer giving the base; it must be at least 2. is a list of lists of base- digits, each giving an entry in the puzzle. The predicate succeeds if is a valid solution to a Hess-style puzzle, that is, the members of represent distinct base- integers, each a perfect square, and each with a nonzero leading digit.
The digits in may be logical variables; if so, fills in the logical variables with the solution that it finds. It is the caller's responsibility to ensure that there are no other logical variables in the arguments to . If the predicate succeeds it must do so in such a way that its arguments are , that is, terms that do not contain any logical variables.
Your solution may invoke the builtin arithmetic predicates of standard Prolog, that is, , , , , , , and . It may also invoke the builtin control constructs of standard Prolog, that is, , , , , , , , , and . Your solution may not invoke any of the other standard predicates; for example, it can't invoke or . You can define any auxiliary predicates that your solution needs, so long as these predicates invoke only the builtin predicates listed in this paragraph.
Submit a file named . If any extra text information is needed, other than what's in the comments, please submit it as a separate text file. Please do not put your name, student ID, or other personally identifying information in your files.
The following session solves Hess's puzzle listed above, along with the same puzzle in base-9 and base-11, and one other puzzle in base-16. For all queries, the user has typed "" once to get alternate solutions. There is only one solution for base 10, but there are at least two in base 11. When there are multiple solutions, your program can backtrack through them in any order. For the second puzzle, the query itself backtracks through all solutions; there are two.
© 2010 Paul Eggert. See copying rules.
$Id: hw4.html,v 1.56 2010/02/04 07:54:34 eggert Exp $
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:
- They must begin and end at distinct islands, travelling a straight line in between.
- They must not cross any other bridges or islands.
- They may only run perpendicularly.
- At most two bridges connect a pair of islands.
- The number of bridges connected to each island must match the number on that island.
- The bridges must connect the islands into a single connected group.
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.
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.
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:
- : (minus sign) a horizontal bridge
- : (equals sign) two horizontal bridges
- : (pipe character) a vertical bridge
- : (quotation mark) two vertical bridges
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:
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.
- 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.
- 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.
- 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.
- 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:
- A plain text documentation file (e.g., README-U000000X.txt): this is a text only file that describes any information you want us to know about your submission. You should not include any identifiable information about your assignment (your name, phone number, etc.) except your matric number and email (we need the email to contact you about your grade, please use your firstname.lastname@example.org address, not your email alias). This is to help you get an objective grade in your assignment, as we won't associate matrics with student names.
- Any source code: we will be reading your code, so please do us a favor and format it nicely.
These files will need to be suitably zipped in a single file called . 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.
- 55% Code
- 25% Test case accuracy
- 10% Performance
- 10% Documentation and instruction following
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.
- Here's Min's attempt at a Prolog tutorial. Enjoy!
- 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.
- A local version of the reference manual for SWI Prolog. Highly technical.
- A Google search for tutorials on Prolog.
- 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    from Prof. Dasgupta at IIT Kharagpur, who teaches the A.I. subject too but over a longer period than we do.
- 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.
- 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.
- The Japanese logic puzzle company, Nikoli, which invented the game, has a tutorial on Hashiwokakero.
Min-Yen Kan <email@example.com> Wed Sep 26 00:00:00 2007 | Version: 1.0 | Last modified: Wed Oct 8 00:00:00 2007