2013
11-12

# 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.

6
3
6
9
10
14
18

1 3 2
[1,1] [3,2]

2 6 4
[3,1] [4,3] [5,5] [6,2]

3 9 6
[4,1] [5,3] [6,5] [7,7] [8,2] [9,4]

4 10 7
[4,1] [5,3] [6,5] [7,7] [8,2] [9,4] [10,6]

5 14 9
[6,1] [7,3] [8,5] [9,7] [10,9] [11,11] [12,2] [13,4]
[14,6]

6 18 12
[7,1] [8,3] [9,5] [10,7] [11,9] [12,11] [13,13] [14,2]
[15,4] [16,6] [17,8] [18,10]

Notes

1. There may be many different correct answers to a particular problem, so your answers need not be the same as those in the Sample Output above.
2. Some solution methods for this problem may cause the time limit to be exceeded. Be sure to try the larger values before submitting your solution.

/* @author: */
import java.util.*;
import java.io.*;
import java.lang.reflect.Array;

public class Main {
static public void main( String [] str ) throws Exception{
int n;
int m;
Scanner cin = new Scanner( System.in );
n = cin.nextInt();
for( int k=1; k<=n; k++ ) {
m = cin.nextInt();
System.out.println( k+" "+m+" "+(m*2+1)/3 );
int j = 1;
int count = -1;
for( int i=(m+4)/3; i<=m; i+=2 ) {
System.out.print( "["+i+","+j+"] " );
j++;
count++;
if( count % 8 == 7 )
System.out.println();
}
j = (m+4)/3+1;

for( int i=(m+4)/3+1; i<=m; i+=2 ) {
System.out.print( "["+i+","+j+"] " );
j++;
count++;
if( count % 8 == 7 )
System.out.println();
}
if( count % 8 != 7 )
System.out.println();
System.out.println();
}

return;
}
}

1. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

3. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience