皇后控制问题

Description:

 

在一个nxn个方格组成的棋盘上的任一方格中放置一个皇后，该皇后可以控制他所在 的行，列以及对角线上的所有方格。对于给定的自然数n，在nxn个方格组成的棋盘上最少要放置多少个皇后才能控制棋盘上的所有方格，且放置的皇后互不攻击？

设计一个拉斯维加斯算法，对于给定的自然数n (1£ n £100)计算在

nxn个方格组成的棋盘上最少要放置多少个皇后才能控制棋盘上的所有方格，且放置的皇后互不攻击。

Input:

 

输入的第一行有1个正整数n。

Output:

 输出计算出最少皇后数及最佳放置方案,第一行是最少皇后数；接下来的1行是皇后的最佳放置方案。

Sample Input:

8

Sample Output:

5
0 3 6 0 0 2 5 8

Note:

 

本题由旧版NOJ导入，来源：算法设计与实验题解