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.
(In reply to
computer solution by Charlie)
If rotations and reflections are discounted, each trial takes longer to compute, as the rotations and reflections of each are counted so that each occurrence is divided by the number of occurrences.
For a 4x4 board:
1 3
2 18
3 40
4 66
5 49
6 30
7 8
8 3
9 0
For an 8x8 board:
1 10
2 257
3 4075
4 47485
5 398907
6 2528655
...
It's getting late and the results are so sloooww, so I'll stop there.
clearvars, clc
global boardSize board forbidden ct n
boardSize=8;
for n=1:8
board=zeros(boardSize);
forbidden=zeros(boardSize);
ct=zeros(1,8);
place(1,1)
tot= ct(1)+ct(2)/2+ct(4)/4+ct(8)/8;
disp([n tot])
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
board=sign(board);
boards={board};
for rotk=1:3
trialboard=rot90(board,rotk);
good=true;
for i=1:length(boards)
if isequal(boards{i},trialboard)
good=false;
break
end
end
if good
boards={boards{1:end} trialboard};
end
end
bp=board';
for rotk=0:3
trialboard=rot90(bp,rotk);
good=true;
for i=1:length(boards)
if isequal(boards{i},trialboard)
good=false;
break
end
end
if good
boards={boards{1:end} trialboard};
end
end
rots=length(boards);
ct(rots)=ct(rots)+1;
else
if boardSize*boardSize>psn+(n-pce)-1 && pce<n
place(pce+1,psn+1)
end
end
end
board=boardSave; forbidden=forbiddenSave;
end
end
|
|
Posted by Charlie
on 2021-11-07 21:17:09 |
dona nobis pacem
