Place exactly 4 black Queens and precisely one black Bishop in a regular 8x8 chessboard in such a manner that it will NOT be possible to place the white King in any vacant square without being in check.
clearvars,clc
goodGrids={};
bestCt=999;
for q1r=1:4, for q1c=1:4
queen(1,1)=q1r; queen(1,2)=q1c;
for q2r=1:4, for q2c=5:8
queen(2,1)=q2r; queen(2,2)=q2c;
for q3r=5:8, for q3c=1:4
queen(3,1)=q3r; queen(3,2)=q3c;
for q4r=5:8, for q4c=5:8
queen(4,1)=q4r; queen(4,2)=q4c;
grid=zeros(8); g0=grid;
for i=1:4
g0(queen(i,1),queen(i,2))=1;
diff=queen(i,2)-queen(i,1); diff2 = 9-queen(i,1)-queen(i,2);
grid=grid+(diag(repmat(1,length(grid)-abs(diff),1),diff));
grid=grid+flip(diag(repmat(1,length(grid)-abs(diff2),1),-diff2));
grid(queen(i,1),:)=grid(queen(i,1),:)+1;
grid(:,queen(i,2))=grid(:,queen(i,2))+1;
end
gct=grid==0;
ct0=sum(gct(:));
if ct0<bestCt
bestCt=ct0;
goodGrids={grid g0};
elseif ct0==bestCt
goodGrids=[goodGrids {grid g0}];
end
end
end
end
end
end
end
end
end
bestCt
length(goodGrids)/2
goodGrids{:}
concerns itself only with the placement of the queens, and assumes that there will be one queen in each quadrant of the board. It reports the grid or grids that leave the fewest squares that are empty and not under attack by the queens.
It finds 64 such placements that leave only two safe spots for an opposing king. Of course, given rotations and reflections, this probably means only eight fundamental solutions. Of course the safe spots need to be on one diagonal to be attackable by the same bishop. The first found did meet that diagonal criterion:
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
where each 1 indicates a queen's placement.
The attack grid was
4 2 1 3 2 2 1 2
2 3 1 1 5 1 1 3
1 1 1 1 1 2 1 1
1 1 1 1 1 1 2 1
2 3 1 1 4 1 1 5
2 1 0 1 1 1 1 1
2 1 1 0 1 1 1 1
2 4 1 1 3 1 1 3
where a zero indicates an available spot to place an opposing king.
Making it readable as a solution:
Q - - - - - - -
- - - - Q - - -
- - - - - - - -
- - - - - - - -
- - - - - - - Q
- - b - - - - -
- - - b - - - -
- Q - - - - - -
Lower case b shows alternative locations of the Bishop; other locations might block a queen's line of sight.
Another solution is given by
4 1 4 1 2 1 3 1
1 1 1 2 1 1 1 1
2 1 3 1 5 1 3 1
1 0 1 2 1 3 1 1
3 1 3 1 4 1 5 1
1 2 1 1 1 2 1 2
3 1 4 1 3 1 3 1
1 1 1 2 1 0 1 1
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0
Q - - - - - - -
- - - - - - - -
- - - - Q - - -
- b - - - - - -
- - - - - - Q -
- - - - - - - -
- - Q - - - - -
- - - - - b - -
In each case one of the possible bishop locations is one of the two locations left unchecked by the queens; the one not chosen for the bishop is checked by the bishop as they are on the same diagonal.
Putting in a check for rotational/reflectional redundancy
good=true; gridA=grid;
for i=1:5
for j=1:length(goodGrids)
if isequal(gridA,goodGrids{j})
good=false;
break
end
end
gridA=rot90(gridA);
end
gridA=flip(gridA);
for i=1:5
for j=1:length(goodGrids)
if isequal(gridA,goodGrids{j})
good=false;
break
end
end
gridA=rot90(gridA);
end
if good
goodGrids=[goodGrids {grid g0}];
end
brings the total queen-placement solutions down to 8 from 64, but one of these "solutions" requires the addition of a rook rather than a bishop, as each of their two unchecked spaces share a row or a column rather than a diagonal.
Inserting some code at the end to prepare for printing:
for i=1:2:length(goodGrids)
grid1=goodGrids{i}; grid2=goodGrids{i+1};
grid3=repmat("-",8);
grid3(find(grid2==1))="Q";
grid3(find(grid1==0))="b"
end
and getting rid of double quotes in the text editor, where I also changed two instances where I had to change the two bishops (two each) with rooks:
Remember, the two b's are a choice: one gets a bishop and the other is checked by that bishop (same with the Rs for rooks, in that one case).
bestCt =
2
ans =
8
grid3 =
8×8 string array
Q - - - - - - -
- - - - Q - - -
- - - - - - - -
- - - - - - - -
- - - - - - - Q
- - b - - - - -
- - - b - - - -
- Q - - - - - -
grid3 =
8×8 string array
Q - - - - - - -
- - - - - - - Q
- - - - - - - -
- b - - - - - -
- - - Q - - - -
- - - - Q - - -
- - - - - - - -
- - - - - b - -
grid3 =
8×8 string array
Q - - - - - - -
- - - - - - - -
- - - - Q - - -
- b - - - - - -
- - - - - - Q -
- - - - - - - -
- - Q - - - - -
- - - - - b - -
grid3 =
8×8 string array
Q - - - - - - -
- - - - - - - -
- b - - - - - -
- - - - Q - - -
- - - - - Q - -
- - - Q - - - -
- - - - - - - -
- - - - - - b -
grid3 =
8×8 string array
- Q - - - - - -
- - - - - Q - -
- - - - - - - -
- - - - - - - -
Q - - - - - - -
- - - - Q - - -
- - - - - - b -
- - - - - - - b
grid3 =
8×8 string array
- - Q - - - - -
- - - - - - Q -
- - - - - - - -
- - - - - - - -
- Q - - - - - -
- - - - - Q - -
R - - - - - - R the Rook case
- - - - - - - -
grid3 =
8×8 string array
- - Q - - - - -
- - - - - - Q -
- - - - - - - -
- - - b - - - -
- Q - - - - - -
- - - - - - - -
- - - - Q - - -
- - - - - - - b
grid3 =
8×8 string array
- - Q - - - - -
- - - - - - - -
- - - - - - Q -
- - - b - - - -
Q - - - - - - -
- - - - - - - -
- - - - Q - - -
- - - - - - - b
If there are any solutions in which more than one queen is in any given quadrant, this program wouldn't find it/them.
|
|
Posted by Charlie
on 2022-05-24 12:39:05 |
computer solution
