The Programmer`s Hex#4635
The goal of this problem is to solve a puzzle that consists of hexagonally-shaped wooden pieces (hereafter referred to simply as "hexagons"), which must be placed on pegs mounted on a wooden base. The pegs are arranged as shown in Figure and are numbered from to for convenience. The hexagons are labeled with capital letters from 'A' to 'G' (see Figure ). An integer (from to , inclusive) is printed adjacent to each edge of each hexagon.
When all hexagons are placed on the 7 pegs, edges of each outer hexagon and all edges of the hexagon on peg will be adjacent to the edge of another hexagon. To solve the puzzle, you must find an arrangement and orientation of all hexagons so that the numbers on each pair of adjacent edges are equal (see Figure ).
Figure – Overhead view of a solved puzzle
Your program must read a description of seven hexagons, find a solution to the puzzle using these hexagons (if one exists), and print a description of the puzzle's solution. If more than one solution exists, you may output any one of them. (Once a solution is found, you could rotate the hexagon on peg and the others accordingly to obtain related solutions.) If no solution exists, your program should output an appropriate message. After printing the solution for one set of hexagons, your program should process the next set, and so on until the end of input.
The input consists of one or more test cases, each describing a set of hexagons. Each of the first lines contains digits (with no spaces), representing the numbers written on the edges of one hexagon. The first line corresponds to hexagon 'A', the second to 'B', and so on until the seventh line, which corresponds to 'G'. The first digit of each line is the number on the edge in the " O'Clock" or "TOP" position. The next digits are the numbers on the edges, listed in clockwise order starting from "TOP". For example, the hexagon in Figure might be given as . As seen in Figure , the numbers on a hexagon's edges are not required to be distinct.
After the seven hexagon descriptions, there is a line with a single asterisk (*), used as a separator between sets. After printing the output for the current set, your program should process the next lines for the following puzzle, and so on, until the end of the file. A separator line appears after each set, including after the last one.
For each set of hexagons in the input, output the solution according to the following format. The output must contain a -column table:
The first column lists pegs from to .
The second column lists the letters of the hexagons placed on pegs to in order.
The third column lists the edge numbers of the corresponding hexagon from column 2, starting from the edge in the "TOP" position for that peg/orientation, followed by the next digits in clockwise order.
Each column should be headed with its name: "PEG", "HEX", and "POSITION".
If there is no solution for a particular set, output the message: "No solutions possible".
After the output for each solution (or after the message "No solutions possible"), print a line containing asterisks (*), to visually separate results for different puzzles.
Example 1