View source for 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? --[[User:Rdm|Rdm]] ([[User talk: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.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 12:37, 24 April 2022 (UTC)
::Well that's easy-peasy: just place the 4 Rooks on a 4x4 board. &#129322; --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 14:54, 24 April 2022 (UTC)

: The task description asks for Queens and Bishops. The F# example shows Queens and Knights. --[[User:Loren|Loren]] ([[User talk:Loren|talk]]) 15:47, 20 April 2022 (UTC)

:: The title of the pages is, currently "N-queens minimum and knights and bishops". --[[User:Rdm|Rdm]] ([[User talk: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--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 12:32, 24 April 2022 (UTC)
:: valid. 
:: On the other hand, the minimum "knights" example consumes an overwhelming amount of the computational time here. Bishops are trivial, queens are not trivial but are orders of magnitude faster than knights.
:: And, consequently, an efficient implementation would likely use a different placement algorithm for bishops vs. queens vs. knights. In the F# example, where most of the implementation is not visible, this might not seem relevant. But for other languages this is likely to be an issue. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 22:43, 27 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.)<br>
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)<br>
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? --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 02:57, 22 April 2022 (UTC)

== 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. <del>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.</del> --[[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)

: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. --[[User:PureFox|PureFox]] ([[User talk: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. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|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]].<br> 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.<br>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. --[[User:Horsth|Horsth]] ([[User talk:Horsth|talk]]) 16:46, 26 April 2022 (UTC)
::::I suppose I should summarise my approach. Within an as above mentioned while m++ loop, find all moves which either occupy or attack {1,1}. Then, for each of those moves, keeping within m total moves, scan [from {1,2} forward] for the first unoccupied and unattacked square, again find all suitable moves, and obviously mark solved/save answer/stop if no such squares found, and abandoning m once all moves for {1,1} have been tried. Basically recursive, but I use an explicit stack (or 30) to make it iterative/re-entrant/GUI compatible. Each such recursive call, for the kth of at most m moves, only ever contemplates the moves for just the ''one'' first needed square. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 14:40, 11 May 2022 (UTC)

== Simple solution for bishops ==
Just place them in one row or column next to the middle.<br>For example 10 by 10.<br>
<pre>0000210000
0000120000
0001002000
0010000200
0100000020
bbbbbbbbbb
0000000000
0000000000
0000000000
0000000000</pre>
One can see that the GO -solution
<pre>
b . . B . . 
. . . B . . 
. . . B . . 
. . . . . . 
. . b B . . 
. . . . . . </pre>
can be easily transformed, by moving b's along their diagonals.
<pre>
. . . B . . 
. . . B . . 
. . . B . . 
. . . b . . 
. . . B . . 
. . . b . . </pre>
Even the example solution of the [[N-queens_minimum_and_knights_and_bishops#Julia]] can easy be transformed
<pre>
 . . . . . . . . . .
 . . . . . 0 . . . .
 . . . . . 1 . . . .
 . 2 . . . . . . . .
 . 3 . . . . 4 . . .
 . . . . . . 5 . . .
 . . 6 . . . 7 . . .
 . . . . . . 8 . . .
 . 9 . . . . . . . .
 . . . . . . . . . .
 move along the diagonals, to get a straight row/column next to the middle
 . . . . 2 . . . . .
 . . . . 3 . . . . .
 . . . . 0 . . . . .
 . . . . 1 . . . . .
 . . . . 6 . . . . .
 . . . . 9 . . . . .
 . . . . 4 . . . . .
 . . . . 5 . . . . .
 . . . . 7 . . . . .
 . . . . 8 . . . . .</pre>
--[[User:Horsth|Horsth]] ([[User talk: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).  --[[User:Wherrera|Wherrera]] ([[User talk: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? --[[User:PureFox|PureFox]] ([[User talk: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. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 17:11, 25 April 2022 (UTC)

::My suggestion would be to save i,j at <code>allAttacked = false</code>, then test <code>if that square or attacks it</code>. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 15:37, 11 May 2022 (UTC)

:: *I've added Go now. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 18:16, 25 April 2022 (UTC)
::: As I'm sure you noticed, I've improved that. Feel free to make the needed tweaks and merge/replace original. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 15:14, 12 May 2022 (UTC)

:::: Hi Pete. Many thanks for doing that which is working great. It's a little faster on my machine (core i7) at 32.6 seconds for 9 bishops and 128 seconds for 10. I'll incorporate the changes into the original Go version and also into the Wren version when I have more time.

::::Do you think it's worth even bothering with bishops when we know from general reasoning that the answer will be 'n' for an 'n x n' board and its trivial to construct an example?
:::::Well, yeah, of course it is, though I'll grant you not very exciting. Simply only ever place bishops in the middle column, either by testing for that or even better yet changing the column loop. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 00:39, 13 May 2022 (UTC)

::::Incidentally, I'm working on a GLPK wrapper for Wren as I'd like to have something in the LP/MIP solver area which can at least solve 'small' problems relatively quickly. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 17:45, 12 May 2022 (UTC)

:Applied the suggested optimisations to the Phix entry (many thanks!):
:Confining bishops to middle column drops that to 0s. (Likewise you could confine rooks to the main diagonal.)
:First queen on a 10x10 now limited to 9 places (was 28), first knight for n>=3 now limited to 2 places (was 3).
:Time for all solutions to 10x10 dropped from 12 mins to 3 mins (almost all being 10N examining 21,801,024 positions). --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 14:12, 11 May 2022 (UTC)
::Found a cheeky little trick (aka a circumstantial optimisation) which made the tricky 10N only examine 8,163,658 positions, and the total time dropped to 1 min 20s, plus I resurrected cheat mode since that now drops it to 8.3s all in up to 10x0. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 18:16, 13 May 2022 (UTC)

==Some Observations==
My first observation would be don't start a task just before your first post pandemic holiday.</br>
I would agree with the suggestion to split the task into two seperating knights from bishops and queens if that generally wished.</br>
For bishops note that the graphs for the white and black squares are disjoint. That is the placing of the bishops on black squares is completely independent of the position of bishops on white squares. For knights quite the opposite, where the knights on 1 colour are placed fixes where knights on the other colour are placed. A knight placed on a white square will attack only black squares and vv. On an 8x8 board I can place 32 knights on white squares which will attack all black squares, so I can place no nights on white squares. This leads to an interesting minimum. If I place 1 knight on a black square it will cover up to 8 white squares leaving 24 that MUST have a knight placed on them, i.e. 25 knights in total. If I place 2 knights on white squares I MUST place 16 knights on black squares, i.e. a minimum of 18. If I place 3 knights on black squares I place 8 on white squares? Well no because it is easy to determine that the maximum number of squares you can attack with 3 on 1 colour.<br> 
By symmetry there must be a minimal solution which includes a Knight on a7 a5 b6 or c5. Initially the number of white squares removed by placing a Knight on a black square is:
<pre>
[["  "; " 3"; "  "; " 4"; "  "; " 4"; "  "; " 2"]
 [" 3"; "  "; " 6"; "  "; " 6"; "  "; " 4"; "  "]
 ["  "; " 6"; "  "; " 8"; "  "; " 8"; "  "; " 4"]
 [" 4"; "  "; " 8"; "  "; " 8"; "  "; " 6"; "  "]
 ["  "; " 6"; "  "; " 8"; "  "; " 8"; "  "; " 4"]
 [" 4"; "  "; " 8"; "  "; " 8"; "  "; " 6"; "  "]
 ["  "; " 4"; "  "; " 6"; "  "; " 6"; "  "; " 3"]
 [" 2"; "  "; " 4"; "  "; " 4"; "  "; " 3"; "  "]]

I choose c5, 8 removed and the counts are:

[["  "; " 1"; "  "; " 2"; "  "; " 2"; "  "; " 2"]
 [" 3"; "  "; " 4"; "  "; " 6"; "  "; " 3"; "  "]
 ["  "; " 4"; "  "; " 6"; "  "; " 6"; "  "; " 4"]
 [" 2"; "  "; " 0"; "  "; " 6"; "  "; " 4"; "  "]
 ["  "; " 4"; "  "; " 6"; "  "; " 6"; "  "; " 4"]
 [" 4"; "  "; " 6"; "  "; " 8"; "  "; " 5"; "  "]
 ["  "; " 2"; "  "; " 4"; "  "; " 4"; "  "; " 3"]
 [" 1"; "  "; " 2"; "  "; " 3"; "  "; " 3"; "  "]]

I choose e3 and the counts are:

[["  "; " 1"; "  "; " 2"; "  "; " 2"; "  "; " 2"]
 [" 3"; "  "; " 3"; "  "; " 4"; "  "; " 2"; "  "]
 ["  "; " 2"; "  "; " 4"; "  "; " 4"; "  "; " 2"]
 [" 1"; "  "; " 0"; "  "; " 4"; "  "; " 4"; "  "]
 ["  "; " 2"; "  "; " 4"; "  "; " 4"; "  "; " 2"]
 [" 2"; "  "; " 4"; "  "; " 0"; "  "; " 3"; "  "]
 ["  "; " 0"; "  "; " 2"; "  "; " 2"; "  "; " 1"]
 [" 0"; "  "; " 2"; "  "; " 1"; "  "; " 3"; "  "]]

and I am left only with knights that attach less than 8 additional squares.
</pre>

With 4 knights on white squares attacking 28 black squares I have a minimum of 8, the 32-28 must be filled with knights. I have ruled out 2,5 and 3,5 above so 4,4 is where I must start. It is possible to place 4 knights on 1 colour which cover 28 squares. The position of the extra 4 knights is fixed, do they cover the 28 uncover squares. You won't be surprised that the answer is no. Searching through the combinations of 4 I find an arrangement with 4 knights covering 22 squares which can be completed with 10 knights that do cover the remaining 28 squares for a minimum of 14 knights. I must now only check 5,5 5,6 5,7 5,8 6,6 6,7 to prove that 14 is minimum. Trying this I obtain:
<pre>
Solving for 1x1 board
Starting with white squares
Solution found using 1 knights in 00:00:00:
X

Solving for 2x2 board
Starting with white squares
Solution found using 2 knights in 00:00:00:
X~
~X

Solving for 3x3 board
Starting with white squares
Trying with black squares
Solution found using 4 knights in 00:00:00:
X~.
~Xo
.o.

Solving for 4x4 board
Starting with white squares
Solution found using 4 knights in 00:00:00:
.~Xo
oX~.
.o.o
o.o.

Solving for 5x5 board
Starting with white squares
Trying with black squares
Solution found using 5 knights in 00:00:00:
.~.o.
oXo.o
.~.o.
oXo.o
.~.o.

Solving for 6x6 board
Starting with white squares
Solution found using 8 knights in 00:00:00:
Xo.o.~
o.o.o.
.oX~.o
o.~Xo.
.o.o.o
~.o.oX

Solving for 7x7 board
Starting with white squares
Trying with black squares
Solution found using 13 knights in 00:00:00.9432799:
X~.~.~.
~.o.o.o
.o.o.~.
~.o.oXo
.o.o.o.
o.~XoXo
.oXo.oX

Solving for 8x8 board
Starting with white squares
Solution found using 14 knights in 00:00:02.2678491:
.o.oXo.~
o.o.o.oX
.~Xo.o.~
o.~.o.o.
.o.o.~.o
~.o.oX~.
Xo.o.o.o
~.oXo.o.

Solving for 9x9 board
Starting with white squares
Trying with black squares
Solution found using 14 knights in 00:00:21.1005398:
.o.o.o.o.
o.~.o.~.o
.oX~.~Xo.
o.o.o.o.o
Xo.o.o.oX
o.o.o.o.o
.oX~.~Xo.
o.~.o.~.o
.o.o.o.o.
</pre>
So I conclude that this task for knights is feasible without a solver, in fact it beats the solver. The code for the above is ,as yet, far from optimal, so I expect better timings. I stop at 9 because I run out of memory, but solving that is just programming.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 14:27, 8 May 2022 (UTC)
: I have replaced the solver with F# code and timings for knights up to 10. I am a little disappointed with 4minutes and 45seconds for 10 as that doesn't beat the solver(YET!). Otherwise 1/4 second for 8 is good enough.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 10:19, 12 May 2022 (UTC)
:: You're now also up against a Go entry that manages 10 knights in 49s on a ten year old box. &#128540; --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 15:23, 12 May 2022 (UTC)