Toad is not amused by your exponential-time algorithm.
Picross, also known as Paint by Numbers or nonograms, is a classic pen-and-paper puzzle game originating in Japan in the late 1980s. Mario's Picross was a video game version of the puzzle released by Nintendo in Japan in 1995 (and later in the US).
Most nonograms are designed to be solved by hand, but where's the fun in that? As good AI students, you'll be writing a computational agent that solves Picross puzzles. Solving general nonograms is NP-complete, but most puzzles can actually be solved quickly using constraint programming techniques. (Legend has it that Spike gave a then-Ph.D.-student version of Prof. Littman this as a homework problem long ago.)
The stencil code is in /course/cs141/pub/src/mario_picross. Try solving the first level yourself with the command python mario_picross.py levels/1.lev (1.lev can be replaced by of the levels in levels).
To play the game click on squares to turn them black and right click to turn them white. In our game a gray square means it may either be black or white, whereas a white square will definitely end up white. Clicking (or right-clicking) on a square again will gray it out. The Check Solution button will tell you if your black squares meet the row and column constraints. The game also supports marking squares as guessed. Shift-left-clicking a square will guess that the square is black (it will turn blue with a white question mark). Similarly, shift-right-clicking will mark a guessed white square (white with a blue question mark). Guessed squares still "look like" solid squares to the Check Solution button, but the guess feature lets you undo guesses easier. In later parts of this assignment, you'll be able to use the guess feature in your code to make programmatic guesses.
Level files can be lists of constraints (.lev files) or solved puzzles (.sol files). The file extension will determine how the program treats the contents. Follow the examples in levels if you want to make your own puzzles. Note that not all grids have exactly one solution, but all of the ones we provide will. (We also recommend trying some of the puzzles from the Picross DS game.)
The game engine and visualizer are in mario_picross.py; you don't need to use or understand this. All of the methods you need are in the Board and Square classes, which are located in board.py. (The game will pass your agent a Board object.) The only file you need to change is picross_agents.py. This file contains stencil code for the DefaultAgent and CleverAgent classes, which contain methods you'll need to implement. In DefaultAgent, you should implement line_solve (see Constraint propagation). In CleverAgent, you need to add backtracking to the solve method and implement a better scheduler in forward_propagate (see Scheduling).
The command to run the solver is python mario_picross.py <level> [<agent> [<delay>]]. Once you've written the DefaultAgent and CleverAgent, you can test your agent by setting <agent> to Default or Clever, respectively. If you're solving with your agent, you can set <delay> to a floating-point number of seconds to wait between steps. This is useful if you want to observe your algorithm run in real time.
We strongly recommend solving some puzzles on your own before you start coding. Here are some solving techniques that humans use. Once you are familiar with how humans solve, think about how a computer could do it. An agent could try pure naive backtracking search, but that would be incredibly slow. Boards have exponential numbers of possibilities and so do rows. Instead, we'll adapt some human solving techniques.
Our basic strategy will be to propagate constraints to determine what is forced in each row and column until nothing is forced and then guess as needed. As in normal backtracking search each guess will further propagate the constraints.
The first thing we would like to know is what moves are forced in each (potentially partially filled) row and column. You could do this by enumerating the valid configurations of a given row and seeing which squares are always one color. A row with s squares, which needs c consecutive blocks with a total of b black squares has O((s - b)c) valid possibilities. While this is technically polynomial we don't want to enumerate them all. Fortunately we are only interested in two of the valid configurations. The leftmost configuration (the one where each block is as far to the left as possible) and the rightmost. You'll notice in the human techniques linked above Simple Boxes involves intersecting corresponding consecutive sequences of black boxes e.g. find the leftmost and rightmost configurations and see if counting in the same direction the nth black sequences intersect. If they do they will in all valid configurations. The same is true of the nth white gap as well. You should convince yourself of why this is the case before going on. This basic strategy encompasses nearly all the human strategies. Punctuation is one very important exception.
Your task is to fill in DefaultAgent's line_solve method. Using some combination of human techniques and the leftmost/rightmost insight you are to have your agent determine as much as they can about the squares in a line based on the squares already in it and the constraint it needs to meet. It may be alright for you to not use all information possible. It certainly is to start out with. However the less information you use the more lines will be examined and the more guesses may be needed.
DefaultAgent's forward_propogate method loops through all rows trying to update until nothing is updated. This is somewhat inefficient, if only in the fact that it doesn't recognize when rows have been updated. The second part of this assignment is to design a better forward_propogate for CleverAgent. Think about how AC3 improves upon a naive arc consistency enforcing algorithm, which would just loop over all constraints. It might be worth thinking about which lines seem more solvable from the outside, but you shouldn't need to use more information about the row or column than the number of white and black squares inside it.
Examining single lines isn't always sufficient to solve the puzzle, so you'll sometimes end up with gray squares remaining after constraint propagation runs. In the human version of Picross, guessing is generally frowned upon; instead difficult puzzles often require use of advanced multi-line logic. Your agent won't be sophisticated enough for that, so if constraint propagation doesn't solve all the squares in the puzzle, you'll have to make guesses. From the possible remaining gray squares, choose one to make a guess on, and fill in a tentative value for that square. Propagate the new information again and repeat this process.
Think back to the constraint satisfaction problems lectures for inspiration what guesses to make. As with scheduling, keep it simple. Don't consider more than the constraints and the number of black and white squares in the row and column of the candidate guess. Remember, backtracking search is much slower than constraint propagation regardless of branching rule! The more information your line solving step is able to incorporate, the fewer guesses your agent will have to make.
Fill in CleverAgent's solve method to allow it to carry on even if no line moves are forced. You may want to use the guessing methods of Square to give you visual clues about your agent's guessing, but this is optional.
You'll be graded on two things in this assignment.
The following table shows the target performance for each of the included test cases. We'll give partial credit for both partial solutions by the DefaultAgent and approximate line counts for the CleverAgent. Note that we may use additional test cases when grading your implementation.
| level | Default (solves?) | Clever (# of lines) |
|---|---|---|
| tiny | yes | 6 |
| 1 | yes | 50 |
| 3 | yes | 100 |
| tokyo | yes | 100 |
| hydrangea | yes | 144 |
| grandpiano | yes | 200 |
| watermill | yes | 200 |
| big | yes | 330 |
| guess | no | 32 |
| gameandwatch | no | 420 |
We'll allow up to 1 minute per test case while grading, but we won't be running your code with the graphics on. Also note that the graphics engine seems to run a little smoother on department machines than non-Linux systems.
The command is cs141_handin mario_picross. You only need to turn in picross_agents.py along with a readme declaring anything we should know such as requiring python2.7.