CSC 421: Algorithm Design & Analysis
Spring 2018

HW5: ABC View and Recursive Backtracking

ABC View is a Japanese logic puzzle game featured on the BrainBashers site. The goal of an ABC View puzzle is to fill a 5x5 grid with the letters A, B and C, consistent with the edge constraints. An edge constraint specifies which letter must appear first in that row or column. Note that some of the letters may initially be filled in, and those letters cannot be changed. For example, the puzzle on the left is solved on the right:


For a person, solving an ABC View puzzle requires complex and careful logical reasoning. However, it turns out that even the most challenging ABC View 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. For example, the grid shown above would be represented as:

|B A A| -+-----+- | |A A| B | | | B| | A| | -+-----+- |CA AC|

Assuming a solution exists, your program should display the solved grid, with the letters placed in the rows and columns (consistent with the edge constraints). For the above grid:

|B A A| -+-----+- |B CA|A A|AC B | |C A B| B| BCA | A| AB C| -+-----+- |CA AC|

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

NOTE: You may assume that the borders of the grid and the letters and spacing inside the borders will always be specified. This ensures that there will be either letters or spaces on the top, left, and bottom edges (in place of any missing constraints). However, you may not assume that spaces will be provided at the end of a row if they are not needed. For example, only the first row of the grid has an edge constraint on the right. The other rows in the grid might have a space at the end, or might just end with the '|' character.

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.