Magic Star

Time limit1sMemory limit256 MB

Summary
Fill the twelve cells of a hexagram with distinct numbers 1 to 12 so each of the six lines sums to 26, choosing the lexicographically smallest completion of a partially given star.
Level

Medium7 of 10

Topics
Backtracking, Brute force, Implementation, Math
Solved
No attempts yet

Problem

A magic star is a hexagram (six-pointed star) whose 12 cells are each filled with a distinct number from 1 to 12.

It is called magic because the four numbers along every line add up to 26. In the illustration above, the six lines have these sums:

  • 1 + 4 + 10 + 11 = 26
  • 11 + 5 + 3 + 7 = 26
  • 7 + 6 + 12 + 1 = 26
  • 2 + 10 + 5 + 9 = 26
  • 9 + 3 + 6 + 8 = 26
  • 8 + 12 + 4 + 2 = 26

There are many ways to fill a magic star. Given a magic star that is only partially filled, write a program that fills in the remaining cells to complete it.

Input

The shape of the magic star is given on five lines. An empty cell is written as x, and a filled cell is written as one of the letters A through L, where the ii-th letter stands for the number ii (A = 1, B = 2, …, L = 12). A . is filler used only to draw the star and is never a number cell. Every input is laid out exactly like the example.

Output

If the magic star can be completed in more than one way, output the completion that is lexicographically smallest. (Concatenate the five lines in order into a single string and compare lexicographically; the string includes the . characters exactly as printed, and letters are ordered A < B < … < L.) The input is always guaranteed to admit at least one completion.

Examples1

  1. Example 1

    Input
    ....x....
.A.I.D.x.
..x...x..
.x.x.x.x.
....x....
    Expected output
    ....F....
.A.I.D.L.
..H...E..
.C.J.B.K.
....G....