# 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:

• Each numbered cell is an island cell and the number in it is the number of cells in that island.
• Each island must contain exactly one numbered cell.
• There must be only one interconnected sea. The sea cells must be connected in one of the four primary directions, not diagonally.
• The sea must not contain "pools", i.e. 2x2 areas of blue cells

## 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.

• Nurikabe: This is the main program, which you should not modify. It runs with two required arguments:
1. The name of the input file
2. "true" if debugging is enabled, "false" otherwise
• Backtracker: This is the backtracking algorithm that was developed in class. It should not be modified.
• Configuration: This is the interface the Backtracker uses for a puzzle's configuration representation. It should not be modified.
• NurikabeConfig: This is the class that is used to represent a configuration in the Nurikabe puzzle. It should be written by you.

## 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:

• First, when generating successors you should populate the next empty cell with an island and sea cell, left to right and top to bottom.
• Each time a successor is generated, you need to make sure in your validity checking method that neither the island cell count, or sea cell count exceeds what the maximum should be for either.
• Once the board is fully populated, your must check:
• The sea is completely connected and there are no pools.
• All of the islands sum up to the correct number of cells, and no two islands are connected to one another.

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

• If a sea cell was just placed you can check that there aren't 3 other sea cells in the N, NW and W neighboring cells.
• If an island was placed, you can check that it doesn't connect two separate islands, and that none of the island counts are exceeded.

### 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.

• input05.txt: A 6x6 puzzle that has a solution. For 20% of the functionality credit, you should be able to solve this puzzle in under a minute.
• input06.txt: A 7x7 puzzle that has a solution. For 5% extra credit, you should be able to solve this puzzle in under 1 second.
• input07.txt: A 8x8 puzzle that has a solution. For 10% extra credit, you should be able to solve this puzzle in under 2 minutes.
• input08.txt: A 9x9 puzzle that has a solution. We will not be testing with this one, but feel free to check out how your program works with it if you get deep into your pruning strategy. For reference, it takes the instructor solution roughly 600 seconds to find the solution.

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:
• Problem Solving: 15%
• In-Lab Activity: 10%
• Design: 15%
• Functionality: 50% (with +15% extra credit)
• Code Style & Version Control: 10%