What is the minimum number
of knights that can be placed on a
standard 8x8 chess board, so that every
square (including those occupied by
knights) is threatened by a knight and
what is such a configuration?
A square
is threatened if a knight can move to
that square on its next move. A knight
moves two squares in one direction
and one square in another direction
(perpendicular to first direction)
to end up on a square of opposite
color. The move can occur even if
intervening squares are occupied.
Present your answer as an 8x8 grid
with ‘o’ representing an unoccupied
square and ‘N’ representing a square
occupied by a knight.
Hint: the
minimum is less than 16.
Since only black squares attack white and only white attack black,
there are two identical and completely independent problems
here. Solve one and you have solved both.
For this reason, the solution will involve an even number
of pieces, so I picked 14 (for being less than 16). Brute force
searching for the right placement of seven pieces is tractable.
I numbered the board 1 to 64 (L-R, B-T) and made a table of
all black squares potentially attacking each white square.
Each table row lists the white square index, the number
of attackers, and the list of the black attacker position indices.
Once a solution was found, that same solution was laid down for the
black squares too. Note that there are other solutions
via rotation about the diagonal and maybe more besides. The final
board, the program w/ output and the table follow. "Kn" are white,
"kn" are black, and the central hole is 3x2.
________________
____Kn__Kn______
____kn__kn__kn__
____Kn______Kn__
____kn______kn__
____Kn__Kn__Kn__
____kn__kn______
program kn
implicit none
integer i1,i2,i3,i4,i5,i6,i7,hit(32,8),hitn(32),hitee(32),
1 ii(7),gap,b(32),i,j
data b/2,4,6,8,9,11,13,15,18,20,22,24,25,27,29,31,
1 34,36,38,40,41,43,45,47,50,52,54,56,57,59,61,63/
common /board/ii,hit,hitn,hitee
open(1,file='sq.txt',status='old')
do i=1,32
read(1,*)hitee(i),hitn(i),(hit(i,j),j=1,hitn(i))
enddo
gap=0
do 1 i1=1,26
ii(1)=b(i1)
do 2 i2=i1+1,27
ii(2)=b(i2)
do 3 i3=i2+1,28
ii(3)=b(i3)
do 4 i4=i3+1,29
ii(4)=b(i4)
do 5 i5=i4+1,30
ii(5)=b(i5)
do 6 i6=i5+1,31
ii(6)=b(i6)
do 7 i7=i6+1,32
ii(7)=b(i7)
call check(gap)
if(gap.eq.1)go to 7
print*,'success'
print 8, (ii(j),j=1,7)
8 format(7(i2,x))
call exit
7 continue
6 continue
5 continue
4 continue
3 continue
2 continue
1 continue
end
subroutine check(gap)
implicit none
integer hit(32,8),hitn(32),hitee(32),ii(7),
1 xyn(64,2),gap,i,i7,j,k,l,big
common /board/ii,hit,hitn,hitee
gap=0
do j=1,32
do k=1,hitn(j)
do l=1,7
if(ii(l).eq.hit(j,k))go to 10 ! sq is attacked
enddo
enddo
gap=1
return
10 continue
enddo
return
end
lord@rabbit 14532 % kn
success
11 13 27 31 43 45 47
lord@rabbit 14532 % more sq.txt
1 2 11 18
3 4 9 13 18 20
5 4 11 15 20 22
7 3 13 22 24
10 4 4 20 25 27
12 6 2 6 18 22 27 29
14 6 4 8 20 24 29 31
16 3 6 22 31
17 4 2 11 27 34
19 8 2 4 9 13 25 29 34 36
21 8 4 6 11 15 27 31 36 38
23 6 6 8 13 29 38 40
26 6 9 11 20 36 41 43
28 8 11 13 18 22 34 38 43 45
30 8 13 15 20 24 36 40 45 47
32 4 15 22 38 47
33 4 18 27 43 50
35 8 18 20 25 29 41 45 50 52
37 8 20 22 27 31 43 47 52 54
39 6 22 24 29 45 54 56
42 6 25 27 36 52 57 59
44 8 27 29 34 38 50 54 59 61
46 8 29 31 36 40 52 56 61 63
48 4 31 38 54 63
49 3 34 43 59
51 6 34 36 41 45 57 61
53 6 36 38 43 47 59 63
55 4 38 40 45 61
58 3 41 43 52
60 4 43 45 50 54
62 4 45 47 52 56
64 2 47 54
Edited on January 25, 2025, 7:06 pm
soln
