Talk:N-queens minimum and knights and bishops: Difference between revisions
Talk:N-queens minimum and knights and bishops (view source)
Revision as of 08:44, 24 April 2022
, 2 years ago→Performance note: Added some comments.
(→Performance note: Added some comments.) |
|||
Line 16:
== Performance note ==
One thing I have found so far is that <code>integer m=1; while not solveable(m) do m+=1 end while</code> is at least five times faster than finding "any solution" and then exhaustively eliminating the existence of anything better. Since it takes my current approach(/that^) around 15 mins (3 mins with cheat below) to solve, I'm currently writing a GUI version so you can at least explore (eg) the 8x8 solutions while it is still cranking on with the 10x10s in the background. If you (cheat) and set m to the right answer to start with it is five times faster again. I might yet go hybrid, as in cheat first, then prove. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 01:03, 24 April 2022 (UTC)
:As usual with Nigel's tasks, the difficulty is not so much finding a way to do them but finding a reasonably quick and efficient way. If he's having to resort to sophisticated stuff like the now deprecated Microsoft.SolverFoundation for his own F# solution, then I suppose that's telling you something.
:A simple backtracking algorithm is clearly not the answer here. If anyone's thinking that just throwing a faster language at it will soon get you up to the 10 x 10 boards for all 3 pieces, they're likely to be disappointed. Both Go and Java have no problem with 10 x 10 for Queens but hit a brick wall when you try to do 7 x 7 for bishops or 6 x 6 for knights. I haven't tried C++ but even if it's 2 or 3 times faster than the aforesaid languages it's still going to be unacceptably slow.
:There are, of course, better algorithms for solving the basic N-Queens problem such as 'branch and bound' and 'hill climbing'. If you check out [https://oeis.org/A075458 OEIS A075458], there's a link leading off it to some [https://oeis.org/A075458/a075458.java.txt Java code] written by one of their experts which uses 'hill climbing' to solve the problem for queens. However, whilst it produces quick results, I couldn't see an easy way to just plug in bishops and knights and another thing I didn't like is that the code seems to loop indefinitely so you're never quite sure if you've found an optimal solution or not. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 08:44, 24 April 2022 (UTC)
| |||