* The implementation of the following problem: Place N queens on an NxN chess board so that none of them attack each other (the classic n-queens problem). Additionally, please make sure that no three queens are in a straight line at ANY angle, so queens on A1, C2 and E3, despite not attacking each other, form a straight line at some angle. * Run it with after build: #+begin_example shell // n = 15 $java -jar nqueen-1.0-SNAPSHOT.jar 15 #+end_example * Performance optimization test under N=15 (Solution size=18752). | # | | time | git branch | | | | (seconds) | | |---+----------------------+-----------+-------------------------| | 1 | initial version | 13.55 | recursive | |---+----------------------+-----------+-------------------------| | 2 | multi-thread | 7.07 | recursive_multi_threads | | | | | | | | | | | | | | | | | | | | | |---+----------------------+-----------+-------------------------| | 3 | multi-thread with | 5.73 | main | | | validation method | | | | | optimized | | | |---+----------------------+-----------+-------------------------| | 4 | iterative version | 9.72 | iterate_1st | | | (abandoned) | | | | | | | | |---+----------------------+-----------+-------------------------| | 5 | further optimization | N/A | N/A | | | (TODO) | | | | | | | | | | | | | | | | | | |---+----------------------+-----------+-------------------------| note for each version: 1. N/A 2. 4 threads does not provide 4 times better performance here due to my test host is 2 cores CPU with hyper-threading. Since this task is computational intensive, we will not benifit from hyper-threading here. 3. replace O(n^2) any angle validation algorithm with O(n) replace O(n) vertical validation algorithm with O(1) 4. iterative version is *abandoned* due to its the BFS behavior introduced some limitation. Refer more details at the interate_2nd branch. 5. from the profiling result. The any angle validation is still a hot spot. Profiling in more details level will guide me to optimize it to a better version, i.e. profiling tool like perf can give more details profiling result on assembly generated by OpenJDK's C2 compiler. ** profiling I did some basic CPU profiling. Here are the result for above version. (The iterate_2nd branch has more profiling result. But it is not very relevant now as I abandon the iterative path.) file: profile_recursive_single_thread.html is the profiling result for version #1. file: profile_recursive_multi_thread.html is the profiling result for version #3. #+begin_example shell // https://github.com/jvm-profiling-tools/async-profiler $java -XX:+UnlockDiagnosticVMOptions -XX:+DebugNonSafepoints -agentpath:$ASYNC_PROF_PATH/libasyncProfiler.dylib=start,event=cpu,file=profile.html,flamegraph -jar nqueen-1.0-SNAPSHOT.jar 15 #+end_example * Example output ** N=8 N=8. There are 8 solutions. Runtime (seconds): 0.026625877 by 4 threads The first 8 Solutions are: [[4, 6, 0, 3, 1, 7, 5, 2], [5, 1, 6, 0, 3, 7, 4, 2], [5, 2, 0, 6, 4, 7, 1, 3], [5, 3, 0, 4, 7, 1, 6, 2], [2, 4, 7, 3, 0, 6, 1, 5], [2, 5, 7, 1, 3, 0, 6, 4], [2, 6, 1, 7, 4, 0, 3, 5], [3, 1, 7, 4, 6, 0, 2, 5]] Solution(#1): [5, 1, 6, 0, 3, 7, 4, 2] | , , , , ,*, , | | ,*, , , , , , | | , , , , , ,*, | |*, , , , , , , | | , , ,*, , , , | | , , , , , , ,*| | , , , ,*, , , | | , ,*, , , , , | ** N=18 This biggest number tried is N = 18. N=18. There are 1001972 solutions. Runtime (seconds): 954.997365061 by 4 threads The first 10 Solutions are: [[0, 2, 5, 9, 6, 12, 16, 11, 13, 17, 3, 8, 4, 1, 10, 14, 7, 15], [0, 2, 5, 9, 14, 3, 8, 16, 13, 6, 17, 15, 7, 12, 10, 1, 4, 11], [0, 2, 5, 10, 12, 9, 4, 16, 14, 3, 7, 13, 17, 6, 1, 11, 15, 8], [0, 2, 5, 10, 12, 9, 4, 16, 14, 3, 7, 13, 17, 8, 6, 11, 15, 1], [0, 2, 5, 10, 13, 11, 8, 3, 1, 17, 14, 16, 6, 12, 9, 7, 4, 15], [0, 2, 5, 12, 6, 11, 14, 1, 13, 8, 17, 3, 16, 9, 4, 10, 7, 15], [0, 2, 5, 12, 9, 17, 8, 13, 1, 16, 14, 7, 4, 10, 3, 6, 15, 11], [0, 2, 5, 12, 15, 7, 3, 13, 6, 14, 17, 10, 16, 4, 8, 11, 9, 1], [0, 2, 5, 12, 15, 13, 16, 1, 6, 4, 14, 10, 8, 3, 11, 17, 7, 9], [0, 2, 5, 12, 15, 17, 3, 9, 6, 16, 14, 10, 1, 7, 4, 8, 11, 13]] Solution(#1): [0, 2, 5, 9, 14, 3, 8, 16, 13, 6, 17, 15, 7, 12, 10, 1, 4, 11] |*, , , , , , , , , , , , , , , , , | | , ,*, , , , , , , , , , , , , , , | | , , , , ,*, , , , , , , , , , , , | | , , , , , , , , ,*, , , , , , , , | | , , , , , , , , , , , , , ,*, , , | | , , ,*, , , , , , , , , , , , , , | | , , , , , , , ,*, , , , , , , , , | | , , , , , , , , , , , , , , , ,*, | | , , , , , , , , , , , , ,*, , , , | | , , , , , ,*, , , , , , , , , , , | | , , , , , , , , , , , , , , , , ,*| | , , , , , , , , , , , , , , ,*, , | | , , , , , , ,*, , , , , , , , , , | | , , , , , , , , , , , ,*, , , , , | | , , , , , , , , , ,*, , , , , , , | | ,*, , , , , , , , , , , , , , , , | | , , , ,*, , , , , , , , , , , , , | | , , , , , , , , , , ,*, , , , , , |