P1277 Word Puzzle

There is an unknown $4 \times 4$ grid $M$, where each entry is a positive integer. You are given the sums of the $4$ rows, the sums of the $4$ columns, and the sums of both diagonals. In addition, the values of any $4$ positions in the grid are given; their positions are specified in the input. Write a program to determine the positive integers in the remaining $12$ positions of the grid, such that the row sums, column sums, and diagonal sums match the values provided in the input. You may assume that no row, column, or diagonal sum exceeds $300$. You may also assume that a solution always exists for the given input.

The input contains $22$ space-separated positive integers. The first four numbers are the sums of the four rows, respectively; the next four numbers are the sums of the $4$ columns. The next number is the sum of the main diagonal elements, i.e., $M(0, 0)+M(1,1)+M(2, 2)+M(3, 3)$. The following number (the $10$th number) is the sum of the anti-diagonal elements, i.e., $M(0, 3)+M(1, 2)+M(2, 1)+M(3, 0)$. The remaining part contains $12$ numbers, grouped into triples $i, j, k$, meaning $M(i,j)=k$.

Output the $16$ numbers arranged as a $4 \times 4$ grid; within each row, separate the four numbers by a single space. Note: For a given input, there may be more than one valid solution. Any one of them is acceptable.

- For $10\%$ of the testdata, no row, column, or diagonal sum exceeds $20$. - For $30\%$ of the testdata, no row, column, or diagonal sum exceeds $80$. - For $60\%$ of the testdata, no row, column, or diagonal sum exceeds $200$. - For $100\%$ of the testdata, no row, column, or diagonal sum exceeds $300$. Thanks to @Jomoo for the contribution. Translated by ChatGPT 5