CSC 421: Algorithm Design & Analysis
Spring 2017

HW5: 3-In-A-Row and Recursive Backtracking


3-In-A-Row is a Japanese logic puzzle game featured on the BrainBashers site. The goal of 3-In-A-Row is to fill an NxN grid (where N is even) with blue and white squares so that each row and column has the same number of each color and there are not three adjacent squares of the same color. The grid will be partially filled with colored squares at the start. For example:

For a person, solving a 3-In-A-Row puzzle requires complex and careful logical reasoning. However, it turns out that even the most challenging 3-In-A-Row puzzles can be easily solved by a computer using recursive backtracking. You are to write such a program. Your program should prompt the user for a file that contains the specifications for a puzzle. An NxN grid will be represented with N rows consisting of the characters 'B' (for blue), 'W' (for white) and '-' (for empty). For example, the 6x6 grid shown above would be represented as:

B-BB-- ---W-W ------ B-B-B- ---B-- -W----

Assuming a solution exists, your program should display the solved grid, with the correct colored squares in place of the blanks. For the above grid:

BWBBWW BBWWBW WBWBWB BWBWBW WBWBWB WWBWBB

If there is no solution, your program should display a message to that effect.

FOR EXTRA CREDIT: Implement an additional feature that checks to make sure that the puzzle solution is unique. This will involve continuing the search after the first solution is found (i.e., pretending that solution doesn't exist) to see if another solution can be found. If so, your program should warn the user that the puzzle has multiple solutions.