Talk:N-queens minimum and knights and bishops: Difference between revisions
Talk:N-queens minimum and knights and bishops (view source)
Revision as of 14:28, 8 May 2022
, 2 years agoSome Observations
No edit summary |
(Some Observations) |
||
Line 99:
:: *I've added Go now. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 18:16, 25 April 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)
| |||