CSCI-142: Computer Science 2
Lab 9 - Nurikabe

Introduction

Nurikabe is a binary determination puzzle based on the fictional spirit from Japanese folklore. The puzzle is played out on a rectangular grid of cells, some of which contain numbers. Numbered cells are always white. Non-numbered cells are initially uncolored, e.g. grey, and can only be colored white or black. In the solution above green is used for an island cell and blue is used for a sea cell. Two same colored cells are considered "connected" if they are adjacent vertical or horizontally, but not diagonally. Connected white cells form "islands", while connected black cells form the "sea". The non-numbered cells must be painted white or black, subject to the following rules:

Input Specification

An initial Nurikabe config will be specified on the command line using an ASCII input file. Here is a link to a 5x5 puzzle.

We will use the following characters to represent the various possible input values for a cell:

Symbol Meaning
. Empty
1-9 Numbered Island
# Island
@ Sea

The format of the file is explained with comments "//" at the end of each line.

    5 5          // number_of_rows number_of_columns
    1 . . . .    // the first row
    . . . . 3    // second row
    . . 2 . .    // third row
    2 . . . .    // fourth row
    . . . . 3    // fifth row
                 // extra input that should be ignored
    A 5x5 puzzle with a solution:

    1 @ @ @ #
    @ @ # @ 3
    # @ 2 @ #
    2 @ @ @ @
    @ @ # # 3

For this lab we guarantee the format of the input file will always be completely valid.

If a cell is non-empty it means its value should not be changed and is either part of a solution, or not. Also, it is illegal to specify a starting configuration that is invalid.

Output Specification

The same cell values are used for output. If debugging is enabled, the backtracker will display each configuration and whether it is valid or not. You can see a sample of what the output looks like here.

When the main program finishes backtracking, it will first display the elapsed time:

    Elapsed time: # seconds.

If there is a solution to the puzzle it will be displayed. For example, the 5x5 puzzle from above would display:

    Solution:
    1 @ @ @ #
    @ @ # @ 3
    # @ 2 @ #
    2 @ @ @ @
    @ @ # # 3

If there is no solution to the puzzle, it will display:

    No solution!

Design

This lab uses the same design framework as the Map Coloring problem from lecture.

Documentation

Here is the main documentation page.

Implementation

Starter Code

Use the GitHub link from your instructor for your section and check out the project in IntelliJ. When you run the main program for the first time, change the working directory to point into the data directory of your project. In this way you only need to specify the names of the files without any additional path information.

The program runs with two command line arguments. The first is the name of the input file. The second is for debugging - if the string is true the backtracker will show all configurations generated, otherwise it will not.

For this assignment you must use the provided backtracking algorithm to obtain a solution. You are free to design your NurikabeClass class however you see fit.

Nurikabe Main Class

The main class is Nurikabe. You should make a run configuration for it and specify the following for the program arguments: data/input01.txt true

Nurikabe Configuration

Unlike with previous labs we are not giving you the private state to represent the Nurikabe puzzle in NurikabeConfig. It is up to you to decide what things you need. You are free and encouraged to add private helper methods, especially for when you do the validity checking.

Pruning

You must do a reasonable amount of pruning in order to receive full credit for this project:

Hopefully you realize that you can prune much faster if you know which cell was last populated. For example:

Timings

To assist you with measuring the effectiveness of your program, we are providing some sample data files for you to test with. Keep in mind that the speed of your machine is going to influence how long it takes to run the tests, so use these measurements as a "ballpark" figure.

Please note! the timings you need to achieve are with debugging disabled (debug flag on command line is set to false). This is done to eliminate the amount of time spent doing output, which can be quite massive for larger puzzles.

You can see all the output with timings for the instructor solution here. Note that the first four files were run with debugging enabled, and the rest were not.

Resources

Backtracking is a concept that a lot of new students have problems picking up. The first hurdle is understanding what exactly is going on. Recall that the lecture notes for the map coloring problem are at your disposal. Great effort was put into making those notes so that you can understand the problem and see how it is implemented in Java.

It is very hard for even a seasoned programmer to write a configuration class for a backtracker correctly on the first try. It requires that you have some pretty good debugging skills (e.g. setting breakpoints and analyzing code). To begin with, we suggest you work with these three smaller puzzles: Do not stop when you have these working. You should test with puzzles that truly have no solution, as well as the puzzle with the minimal pruning requirement, input05.txt


Submission

You should zip your Java src directory into lab9.zip and submit it to the dropbox on MyCourses by the due date.

Please note! To save your SLI time, please indicate in your dropbox submission (as a comment) if they should test for the extra credit puzzles.


Grading

The grade breakdown for this lab is as follows: