CSC 421: Algorithm Design & Analysis
Spring 2019

HW5: ABC Paths and Recursive Backtracking

ABC Path is a logic puzzle game featured on the BrainBashers site (among others). The goal of an ABC Path puzzle is to fill a 5x5 grid with the letters A through Y, with consecutive letters appearing adjacent to each other (either horizontally, vertically, or diagonally). In addition, edge constraints specify the row, column, or diagonal that each letter must appear in. The location for A is provided in the puzzle and you must fill in the rest. For example, the puzzle on the left is solved on the right:

       

For a person, solving an ABC Path puzzle requires complex and careful logical reasoning. However, it turns out that even the most challenging ABC Path 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:

M|XVCJO|U -+-----+- Y| |D H| |E L| A |G N| |T Q| |S -+-----+- I|WBRPK|F

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:

M|XVCJO|U -+-----+- Y|YDCJI|D H|XBEHK|E L|WAFGL|G N|TVRMN|T Q|USQPO|S -+-----+- I|WBRPK|F

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.