CS440/ECE448 Fall 2018 Assignment 3: CSP - Nonogram Due date: Monday October 15th, 11:55pm

See the the main MP page for programming language requirements, policies about working in groups, submission procedures, etc. Also make sure you are familiar with the course policies on academic integrity, late submissions, etc.

Contents

• Introduction and Rules
• 1. Smaller Inputs
• 2. Bigger Inputs
• Extra Credit Suggestion
• Provided Code Skeleton
• Deliverables
• Report Checklist

Nonograms, also known as Picross or Griddlers, are picture logic puzzles in which cells in a grid must be filled or left blank according to numbers at the side of the grid to reveal a hidden picture. The numbers are a form of discrete tomography that measures how many unbroken lines of filled-in squares there are in any given row or column. For example, a clue of "4 8 3" would mean there are sets of four, eight, and three filled squares, in that order, with at least one blank square between successive groups. The following figure shows an example of the start state and goal state for one Nonogram instance. In this assignment, each puzzle in the basic part (excluding the extra credit part) only has one unique solution. Try to play the game here!

First, you need to formulate Nonogram as a CSP. In your report, give your definitions of variables, domains, and constraints. Next, with these in mind, implement your solution, includes any variable and value ordering heuristics that make sense for your formulation (which would probably include forward checking). In the report, describe your implementation and give a brief explanation of why you chose to use your particular combination of heuristics and inference techniques.

Your inputs will give you constraints as a numpy object, and you should return a 2D output of an array that satisfies the constraints. For this assignment, you will be autograded by your output. Your job is to implement the solve function in solve.py. The function should take in a set of constraints and output a 2D numpy array that satisfies the constraints. In order to run your code on an instance of a nonogram problem, we have provided a script nonogram.py which will load constraints and test your implementation of the solve function. We will soon also have a tool for viewing the 2D output array as well.

For each of the inputs below, please include a .npy file containing the solution to the input as well. Please also include the runtime for each in your report.

1. Smaller Inputs

1. 10*5 puzzle
2. 10*10 puzzle
3. 10*10 puzzle
4. 15*15 puzzle
5. 15*15 puzzle

1. 14*25 puzzle
2. 20*20 puzzle
3. 35*25 puzzle

• Try to solve the following larger inputs. We don't guarantee they have unique solution, but you can get credit as long as you give at least one solution.
  • 23*27 puzzle
  • 34*34 puzzle
  • 45*45 puzzle
• Come up with more than one heuristic and do comparison. You should analyze the reasons if one heuristic is better than others.
• Solve the following Colored mazes. (The numbers correspond to colors).
  • 4*4 puzzle
  • 7*7 puzzle
  • 15*15 puzzle
  • 25*25 puzzle
  • 45*45 puzzle
  • 15*15 puzzle (picture)
  • 15*15 puzzle (picture)

Moodle submission instructions will be posted on the the main MP page. You will be uploading three files

• Your report (pdf).
• A .zip/.tar file of the discovered solutions to the bigger nonograms and/or colored nonograms. For each set of constraints [FILENAME].npy, you should include a solution named [FILENAME]_solution.npy in the compressed library, where the solution is the saved numpy 2D solution.
• A copy of solve.py containing all your new code.
• (Groups only) Statement of individual contribution.

The statement of individual contribution is a brief summary of which group member was responsible for which parts of the solution and submitted material. We reserve the right to contact group members individually to verify this information.

Report Checklist