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. 🤪 --Pete Lomax (talk) 14:54, 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)

The title of the pages is, currently "N-queens minimum and knights and bishops". --Rdm (talk) 18:31, 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)

valid. --Rdm (talk) 14:14, 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)

I am thinking about to use a good strategy of finding the next possible place for a token like Spiral_matrix#Phix.
Starting in the middle at the highest number and checking next possible places along the spiral backwards.This should place the next token Q,B,K in a way, that they maximize the attacked places.
Hopefully an optimal solution with the lowest count of tokens is found this way faster, to stop search as soon as possible, if number of token exceeds this number. --Horsth (talk) 16:46, 26 April 2022 (UTC)

Simple solution for bishops

Just place them in one row or column next to the middle.
For example 10 by 10.

0000210000
0000120000
0001002000
0010000200
0100000020
bbbbbbbbbb
0000000000
0000000000
0000000000
0000000000

One can see that the GO -solution

b . . B . . 
. . . B . . 
. . . B . . 
. . . . . . 
. . b B . . 
. . . . . . 

can be easily transformed, by moving b's along their diagonals.

. . . B . . 
. . . B . . 
. . . B . . 
. . . b . . 
. . . B . . 
. . . b . . 

--Horsth (talk) 16:47, 25 April 2022 (UTC)

Although I realized this some time ago and several sources simply state the minimum number of bishops to be N for an N x N board I haven't been able to find a mathematical proof of this. In other words how do you know that there isn't a solution which only uses N-1 bishops?

If you number the diagonals (in one or either directions) it can be seen there must be at least one bishop on each diagonal. So the minimum number is the (number of rows) == (number of diagonals parallel to one direction). --Wherrera (talk) 00:18, 26 April 2022 (UTC)

OK, thanks, I can see now that there must be at least one bishop in every diagonal to achieve full coverage but, OTOH, there can't be more than one in any diagonal to avoid attacking one another.

But, now we're clear on that, I'm wondering why Nigel has bothered asking about bishops in the first place when we know the answer must be 'N' and it's trivial to construct an example? --PureFox (talk) 06:42, 26 April 2022 (UTC)

Incidentally, although I've written a Go solution, the only one I've posted so far is Wren *. The former is, of course, much quicker but still far too slow for my liking.

Any ideas on how the performance of the Wren solution could be improved? I've tried a number of things but (apart from improving the diagonal checking) no joy so far. --PureFox (talk) 17:11, 25 April 2022 (UTC)

*I've added Go now. --PureFox (talk) 18:16, 25 April 2022 (UTC)