a. For n=1 to 9 evaluate f(n) as the number of distinct ways n peaceful knights may be placed on a 4*4 chessboard.
b. Extend the above task for 8*8 chessboard.
Peaceful knights means no knight is threatening another.
For a 4 x 4 board:
1 16
2 96
3 276
4 412
5 340
6 170
7 48
8 6
9 0
The 6 for n=8:
1 1 1 1
0 0 0 0
0 0 0 0
1 1 1 1
1 1 0 1
1 0 0 0
0 0 0 1
1 0 1 1
1 0 1 1
0 0 0 1
1 0 0 0
1 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
1 0 0 1
1 0 0 1
1 0 0 1
1 0 0 1
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
clearvars, clc
global boardSize board forbidden ct n
boardSize=4;
for n=1:9
board=zeros(boardSize);
forbidden=zeros(boardSize);
ct=0;
place(1,1)
disp([n ct])
end
function place(pce,st)
global boardSize board forbidden ct n
for psn=st:boardSize*boardSize
boardSave=board; forbiddenSave=forbidden;
row=ceil(psn/boardSize); col=psn-boardSize*(row-1);
if board(row,col)==0 && forbidden(row,col)==0
board(row,col)=pce;
for dr=-2:2
tmp=3-abs(dr);
for dc=-tmp:2*tmp:tmp
if dc~=0 && dr~=0
if row+dr>0 && row+dr<=boardSize
if col+dc>0 && col+dc <=boardSize
forbidden(row+dr,col+dc)=1;
end
end
end
end
end
if pce==n
ct=ct+1;
if n==8
disp(sign(board))
disp(' ')
end
else
if boardSize*boardSize>psn+(n-pce)-1 && pce<n
place(pce+1,psn+1)
end
end
end
board=boardSave; forbidden=forbiddenSave;
end
end
For board size of 8:
1 64
2 1848
3 32084
4 376560
5 3184708
6 20202298
7 98796304
8 379978716
9 1167053680
The computation for 9 on an 8x8 board took several hours (maybe 4 or 5).
Compare with A244081 in OEIS, though that's hard to read given the 2-dimensional nature of the input variables (board size and number of knights).
|
|
Posted by Charlie
on 2021-11-05 14:55:38 |
computer solution
