Talk:N-queens minimum and knights and bishops
As the current task description has noted, we've already done this for queens.
Shouldn't knights and bishops be separate tasks?
Or is there something interesting about combining the three tasks? --Rdm (talk) 15:41, 20 April 2022 (UTC)
- Interesting night be a question like: I have 4 Rooks where should I place them to minimize the number of Knights I require to fulfil the requirement that no piece attacks another but all unoccupied squares are attacked.--Nigel Galloway (talk) 12:37, 24 April 2022 (UTC)
- Well that's easy-peasy: just place the 4 Rooks on a 4x4 board. 🤪 --13:07, 24 April 2022 (UTC)
- The task description asks for Queens and Bishops. The F# example shows Queens and Knights. --Loren (talk) 15:47, 20 April 2022 (UTC)
- Have we already done this? N-Queens is placing N-Queens on an NxN board, here you must place the minimum number such that they do not attack each other but every Unoccupied square is attacked--Nigel Galloway (talk) 12:32, 24 April 2022 (UTC)
F# errors
The F# entry fails with qbn.fsx(13,3): error FS0597: Successive arguments should be separated by spaces or tupled, and arguments involving function or method applications should be parenthesized (locally, tio, and replit). It does not seem possible to add any more parenthesis to that line. (Excruciatingly awful error message, btw, imo.)
Removing the leading space on line 2 lead me to qbn.fsx(2,16): error FS0039: The namespace 'SolverFoundation' is not defined. (ditto locally, tio, and replit)
The only relevant thing I cound find is that SolverFoundation has apparently been deprecated, certainly all work and maintenance on it indeed completely ceased in 2017, plus https://devblogs.microsoft.com/search?query=SolverFoundation (0 results) seems conclusive. What's the run time like? --Pete Lomax (talk) 02:57, 22 April 2022 (UTC)
Performance note
One thing I have found so far is that integer m=1; while not solveable(m) do m+=1 end while 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. --Pete Lomax (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 OEIS A075458, there's a link leading off it to some 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. --PureFox (talk) 08:44, 24 April 2022 (UTC)
- Just noticed that A075458 isn't quite the same problem anyway as the queens can still attack one another. If you try a 4 x 4 board in the above code, you get a minimum of 2 queens when the answer we want is 3. --PureFox (talk) 09:02, 24 April 2022 (UTC)
- Actually that cheat I mentioned isn't needed or particularly helpful (when paired off with a prove chaser that is), but glad I tried it as it lead to a quite helpful and probably obvious optimisation: if you can't solve a 7x7 board with 6 bishops, no point trying to solve an 8x8 with only 6. There's also "first bishop must be on the main diagonal", and again obviously if there is no answer up to the mid-point, there will not be one after. --Pete Lomax (talk) 09:36, 24 April 2022 (UTC)