
ZOJ Problem Set  2778
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 NQueens 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 nonattacking queen positions. Write a program, which, given the size, N, of the triangular array, finds a maximal set of nonattacking queen positions on the array (floor((2*N + 1)/3) of them). Input 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. Output 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. Sample Input
6 Sample Output
1 3 2 Source: Greater New York Regional 2006 