3091：Triangular N-Queens Problem

A “queen” piece on a triangular array of cells, N cells on a side, can attack any cell on a file parallel to one of the sides containing the queen’s cell. For example, in the array in Figure 1, a queen on the black cell, attacks all of the shaded cells. The Triangular N-Queens Problem of size N, is to find a maximal set of queen positions in a triangular array with N cells on a side so that no queen is attacking any other queen. For example, the black cells in Figure 2 give a maximal set of queen positions in a size 6 array. It turns out that a size N array always has floor((2 * N + 1) ⁄ 3) as the maximal number of non-attacking queen positions.

Write a program, which, given the size, N, of the triangular array, finds a maximal set of non-attacking queen positions on the array (floor((2 * N + 1) ⁄ 3) of them).

The input begins with a line containing an integer value specifying the number of datasets that follow, C (1 ≤ C ≤ 1000). Each dataset consists of a single line containing a single integer N, (1 ≤ N ≤ 1000), which is the size of the triangular array.

The first output line for each problem gives the problem number starting at 1, a single space, the input size, a single space and the number of queen positions. Following the first line will be the queen positions, 8 positions per line except perhaps for the last line of positions. Each position has the format open bracket (‘[’), row number starting with 1, a comma, the position from the left within the row starting at 1 and a close bracket (‘]’). Positions within a line are separated by a single space. For example, the queen positions in Figure 2 are [1,1] [4,2] [5,4] [6,3]. The lines of position values are followed by a single blank line.