| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14154 | EE2310_Assg2 |
|
Description
The K-Queen Problem
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,4), (2,6), (3,8), (4,2), (5,7), (6,1), (7,3), (8,5).
For simplicity, since the x-axis is counted according to numerical order, we can simply represent this solution as the following 8 numbers: 4 6 8 2 7 1 3 5.
What you need to do
The input will be the number of K. All you need to do is output ALL SOLUTIONS in lexicographic order. If we count different rotations and flippings as different solutions, then there are 92 solutions for the case K = 8. You should output these solutions in lexicographic order (e.g. 15863724 should be placed before 17468253). Your program must be able to handle at least the cases K <= 8. Your program should have reasonable efficiency so that OJ can run and output the results. You can use what you have learned so far to write this assignment: both C or C++ will be fine. Since this assignment does not involve complex data types, you probably don't need to use a lot of C++ object oriented programming techniques. Most likely you need to either use a stack or recursion (which contains an implicit system stack). You should not hardcode any of the known solutions and output them in order to pass OJ. This will be regarded as cheating and you will fail this course. 請勿將已知的解直接寫入程式碼並輸出讓OJ能過，這樣會被視為作弊，總成績會以不及格論處。
Grading Criteria
Correctness 70% + Coding style 30% (same as Assg #1)
- Your program should be well-commented. All variables, functions, loops should be clearly explained in the comments.
- Blocks in your source code should have proper indentation (縮排).
- Do not use any global variable to pass data in and out of a function.
- For a good program style, please follow Recommended C style and coding rules.
Submission
Submit your source code on both the OJ and eLearn.
Input
4
Output
2 4 1 3 3 1 4 2 2 solution(s) for the 4-Queen problem.