Futoshiki (also known as Unequal) is a Japanese logic puzzle game that appears in many newspapers, books, and Web sites (e.g., Futoshiki.org, BrainBashers). The goal of Futoshiki is to fill an NxN grid (where 4 ≤ N ≤ 9) with numbers so that no number appears more than once in a row or column. The grid may be partially filled with numbers at the start, and additional relational constraints may be placed on adjacent spaces, requiring one number to be larger than another. For example:

For a person, solving a Futoshiki puzzle requires complex and careful logical reasoning. However, it turns out that even the most challenging Futoshiki 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 2N-1 rows, each beginning and ending with a vertical bar (to ensure consistent spacing). Within the bars, characters specify the contents of the grid spaces (with - representing a blank space), as well as the potential constraints between those spaces (using < > v ^). For example, the Futoshiki grid shown above would be represented as:

Assuming a solution exists, your program should display the solved grid, with the columns aligned and the correct numbers in place of the blanks. For example:

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.