We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Super-Queens on a Chessboard
Super-Queens on a Chessboard
Sort by
recency
|
8 Discussions
|
Please Login in order to post a comment
I struggled with Time Limit Exceeded for n == 14 and 15 and tried to use memoization and other tricks to solve it with no luck.
Then I realized that all of the solutions on this page are building "one queen per column" (or one queen per row) into the placement function. This solves a lot of performance issues.
A Clojure solution that handles all test cases.
PERFORMANCE HINT: It pays to look at the "environment" link at the bottom of the page! My code was a bit too slow to handle case 4 (14), and it seems one bottleneck in union-ing sets. The test environment includes a library called int-map which is significantly faster and solved the problem.
The problem of the last test - some optimizatins. If all tests are passed except the last (timeout) - seems like your idea is ok. In my case the problem was in L-shaping. I collected all of them inside one set and passed it through the recursion. But (F# lang) the search is Log(O). I have changed 1 common storage to 2 separaged, level1 and level2. So when i checked (i,j) place - I have chacked (except lines and diagonales) only level1 set. if it was ok - add to level2 new L-shaped positions and add 2 points to new Level3 set. the next iteration is level2 as level1 and level3 as level2. Through this way every step have 3 check in Set(N) and 1 check in Set(4). Hope it is clear....
Well-commented code for Haskell beginners:
Not sure that my solution is right, but:
n = 14: it takes nearly 4 to 5 seconds to compute all queens n = 15: it takes nearly 39 seconds to compute all queens
If I am right, then, my solution should pass all tests for all integers in range [8, 14], not for 15.
Is it correct that #5 testcase use 14 as input?