Description
Write a program that finds all possible ways to place K queens on an K×K chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal, as shown in the diagram below:
Let (1, 1) be the top-left corner and x, y be the vertical as well as horizontal axes, respectively. We represent this solution as (1,5), (2,2), (3,4),(4,7),(5,3),(6,8),(7,6),(8,1).
For simplicity, since the x-axis is counted according to numerical order, we can simply represent this solution as the following 8 numbers: 5 2 4 7 3 8 6 1 .
The input will be the number of K. All you need to do is to output ALL POSSIBLE SOLUTIONS. If we count different rotations and flippings as different solutions, then there are 92 solutions for case K=8. You should output these solutions in lexicographic order (e.g. 15863724 should be placed before 17468253). Your program should have reasonable efficiency and you may need to use a stack to do that.
Notice:
1. Please submit all your designed function to OJ.
2. The output format for one solution is like 5 2 4 7 3 8 6 1 \n , where stands for one space.
Input
The number of Queen.
Output
All possible solutions.