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

设计一个拉斯维加斯算法，对于给定的自然数n (1<= n<=100)计算在n*n个方格组成的棋盘上最少要放置多少个皇后才能控制棋盘上的所有方格，且放置的皇后互不攻击。

1 个正整数n

第一行是最少皇后数；接下来的1 行是皇后的最佳放置方案。