Place two Knights, two Rooks, two Bishops and two Kings on a 4x4 chessboard, so that:
1) The Kings are not attacked at all.
2) All other pieces are attacked exactly once.
Ignore color, so every piece attacks every other piece whose square it can move to, including the Kings.
I don't know how many solutions there are, but there is at least one.
I'm not trying to solve the puzzle, I'm just interested in how many solutions there are, since the OP claims he doesn't know. I brute forced it with a program.
There are
264 solutions, not taking rotations and reflections into account. However, there are only 36 unique configurations. 30 of these solutions are multiplied by 8 (4 rotations * 2 reflections), while the other 6 only by 4. This is because the solution is already its own reflection.
First of all, there are 32432400 configurations, not taking rotations and reflections into account. Since the board has 16 squares, if we were to place the two kings anywhere, we'd be looking at their combinations using the formula C(16, 2). The knights would now have 14 available squares, so multiply the previous result with C(14, 2), etc.
I named each square with a number from 0 to 15 like so,
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
generated the piece configurations, checked for validity and saved the solutions. The numbers for each solution represent the board squares, with the kings placed first, then the knights, then the rooks and then the bishops. For example, Skyvask's solution is (2, 13, 0, 15, 7, 8, 1, 14).
The complete list can be found here and the unique solutions here.
Code:
from collections import defaultdict
import itertools as it
SIZE = 4
N = SIZE**2
def flatten(rank, file):
return rank * SIZE + file
def is_in_bounds(square):
return 0 <= square < SIZE
def king_moves(rank, file):
moves = []
if rank - 1 >= 0:
moves += [flatten(rank-1, f) for f in range(file-1, file+2) if is_in_bounds(f)]
moves += [flatten(rank, f) for f in (file-1, file+1) if is_in_bounds(f)]
if rank + 1 < SIZE:
moves += [flatten(rank+1, f) for f in range(file-1, file+2) if is_in_bounds(f)]
return moves
def rook_moves(rank, file):
moves = [[flatten(r, file) for r in range(rank-1, -1, -1)]]
moves += [[flatten(r, file) for r in range(rank+1, SIZE)]]
moves += [[flatten(rank, f) for f in range(file-1, -1, -1)]]
moves += [[flatten(rank, f) for f in range(file+1, SIZE)]]
return moves
def bishop_moves(rank, file):
down = range(-1, -rank-1, -1)
up = range(1, SIZE-rank)
moves = [[flatten(rank+i, file-i) for i in down if is_in_bounds(file-i)]]
moves += [[flatten(rank+i, file+i) for i in down if is_in_bounds(file+i)]]
moves += [[flatten(rank+i, file-i) for i in up if is_in_bounds(file-i)]]
moves += [[flatten(rank+i, file+i) for i in up if is_in_bounds(file+i)]]
return moves
def knight_moves(rank, file):
offsets = ((-2, -1), (-2, 1),
(-1, -2), (-1, 2),
(1, -2), (1, 2),
(2, -1), (2, 1))
moves = [flatten(rank+x, file+y) for x, y in offsets
if is_in_bounds(rank+x) and is_in_bounds(file+y)]
return moves
def filter_ray_moves(moves, occupied):
filtered_moves = []
for direction in moves:
for square in direction:
if square not in occupied:
filtered_moves.append(square)
else:
filtered_moves.append(square)
break
return filtered_moves
def solve(piece_moves_from):
solutions = []
attack_rule = [0, 0, 1, 1, 1, 1, 1, 1]
for k1, k2 in it.combinations(range(N), 2):
# if the kings attack each other, skip
if k2 in piece_moves_from['K'][k1]:
continue
allowed = [s for s in range(N) if s not in (k1, k2)]
for n1, n2 in it.combinations(allowed, 2):
n1_attacks = piece_moves_from['N'][n1]
n2_attacks = piece_moves_from['N'][n2]
knight_attacks = n1_attacks + n2_attacks
king_attacks = (piece_moves_from['K'][k1] +
piece_moves_from['K'][k2])
# if either knight attacks any king, skip
if k1 in knight_attacks or k2 in knight_attacks:
continue
# if two kings + one knight gang up on the other knight, skip
if (king_attacks + n1_attacks).count(n2) > 1:
continue
if (king_attacks + n2_attacks).count(n1) > 1:
continue
# Keep track of which squares are attacked more than once so far,
# so we can exclude rooks and bishops there.
# We can't take into account the rooks' attacks, because they
# may be blocked by the time every piece is on the board.
k_n_attacks = king_attacks + knight_attacks
allowed = [s for s in range(N) if s not in (k1, k2, n1, n2)]
for r1, r2 in it.combinations(allowed, 2):
if k_n_attacks.count(r1) > 1 or k_n_attacks.count(r2) > 1:
continue
allowed = [s for s in range(N) if s not in (k1, k2, n1, n2, r1, r2)]
for b1, b2 in it.combinations(allowed, 2):
if k_n_attacks.count(b1) > 1 or k_n_attacks.count(b2) > 1:
continue
piece_coords = (k1, k2, n1, n2, r1, r2, b1, b2)
attack_counter = defaultdict(int)
for coord in (k1, k2):
for square in piece_moves_from['K'][coord]:
attack_counter[square] += 1
for coord in (n1, n2):
for square in piece_moves_from['N'][coord]:
attack_counter[square] += 1
for coord in (r1, r2):
for square in filter_ray_moves(
piece_moves_from['R'][coord], piece_coords):
attack_counter[square] += 1
for coord in (b1, b2):
for square in filter_ray_moves(
piece_moves_from['B'][coord], piece_coords):
attack_counter[square] += 1
attacks = [attack_counter[piece] for piece in piece_coords]
if attacks == attack_rule:
solutions.append(piece_coords)
return solutions
piece_moves = {'K': king_moves,
'N': knight_moves,
'R': rook_moves,
'B': bishop_moves,
}
piece_moves_from = {}
for piece, moves in piece_moves.items():
piece_moves_from[piece] = {}
for rank in range(SIZE):
for file in range(SIZE):
piece_moves_from[piece][flatten(rank, file)] = moves(rank, file)
solutions = solve(piece_moves_from)
One can print a board representation of the solutions with the following function.
def print_board(solution):
squares = [' '] * N
pieces = tuple('KNRB')
sep = '\n' + '+'.join(['-'] * SIZE) + '\n'
for i in range(8):
squares[solution[i]] = pieces[i // 2]
print(sep.join('|'.join(squares[i:i+SIZE]) for i in range(0, N, SIZE)))
The unique solutions are then
K | | K | N K | | K | N K | | K | N K | | K | K | | K |
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
B | | | N B | | | B | | | B | | | N B | | | N
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
| | | B N | | | B | | | B N | | | B | | | B
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
| R | | R R | | | R N | R | | R R | | | R N | R | | R
K | | K | K | | K | K | | K | K | | K | K | | | K
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
| | | R | | | R | | | | | | R N | | | N
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
N | R | N | B N | | N | B N | B | | R N | B | | B B | | | B
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
B | | | R | | | B N | B | | R R | | | N R | | | R
K | | | K K | | | K K | | | K K | | | K K | | | K
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
N | | | B N | | | B N | | | B N | | | B N | | |
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
N | R | | N | | | B B | | | N | R | | B B | R | | B
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
B | | R | R | | | R R | | | R | | R | N | | R | N
K | | | K K | | | K K | | | K K | | | K K | | | K
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
N | | | B B | | | B | | | B B | | | B B | | | B
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
B | | | N | R | | N N | R | | N N | | | N N | R | |
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
R | | R | N | | R | B | | R | R | | | R N | | R |
K | | B | K K | | | K K | | | K K | | | N K | B | | N
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
| | | | | | B | | | B | | | K | | | K
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
N | | | B | R | | B B | R | | B N | | | B B | | |
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
N | R | | R N | | R | N N | | R | N R | R | | R | | R | N
K | | | K | | N | B K | | N | B K | | N | B B | K | | N
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
B | | | K | R | | N | R | | | R | | N | | | K
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
N | | | B | | R | N | | R | | | R | B | | |
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
R | R | | N B | | | K B | | | K B | N | | K R | | R |
| K | | N B | K | | N | K | | N B | K | | | K | |
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
N | | | K | | | K | | | K N | | | K N | | | K
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
B | | | B | | | N B | | | N B | | | N B | | | N
--+---+---+-- --+---+---+-- --+---+---+-- --+---+---+-- --+---+---+--
R | | R | B R | | R | R | | R | B R | | R | R | | R | B
| K | B | N
--+---+---+--
R | | |
--+---+---+--
| | | R
--+---+---+--
N | B | K |
(0, 3, 9, 14, 8, 11, 12, 15).
– Reti43
Dec 05 '17 at 23:55
(0, 3, 9, 14, 8, 11, 12, 15) is now (0, 3, 12, 15, 9, 14, 8, 11). The solution link has also been updated.
– Reti43
Dec 06 '17 at 00:38
Here is mine with passive kings, some minutes late :
Here's a solution with the additional constraint that no piece may attack more than one piece:
I also thought of a possible solution:
As a little bonus, the position of every horse can be interchanged with a bishop and vice-versa, giving 5 more possible solutions. Going top left to bottom right: we currently have hbhb; but we can also have hhbb, hbbh, bhhb, bhbh, bbhh
(bonus #2 is we can multiply this by 4 orientations of the board).
I wrote a quick little program to work them out; I agree with Reti43 that there are 264 with rotations and reflections, and 36 without.
The 36 possibilities are listed below, and I've included also the C# code if someone wants to play with it further. I represent boards as immutable bit vectors, so that they're nicely compact in memory and fast to compute. The core algorithm is just a big query comprehension.
My solution is not exactly exemplary code in either its design or execution; I wrote it very quickly and it is just brute force with ad-hoc pruning to quickly discard boards that can't work. A more sophisticated approach would be to use a backtracking constraint satisfaction solver, like you do for sudoku solvers.
K K
R
NRNB
B
----
K K
R
NB B
R N
----
K K
R
N NB
R B
----
K K
NB R
NB R
----
K KN
B
N B
R R
----
K K
B N
N B
R R
----
K KN
B N
B
R R
----
K KN
B
B
NR R
----
K K
B N
B
NR R
----
K K
B B
NR N
R
----
K K
B B
NR
N R
----
K K
N B
R B
RN
----
K K
B
R B
N RN
----
K K
N B
NR
B R
----
K K
B
NR N
B R
----
K K
N
BR B
RN
----
K K
BR B
N RN
----
KB K
B N
R RN
----
K K
N B
B
R RN
----
K K
B B
N N
R R
----
K K
B N
B N
R R
----
K K
B N
N B
R R
----
K K
N N
B B
R R
----
K N
B K
N B
RR
----
K
B K
N B
RR N
----
KB N
K
B
R RN
----
K NB
R N
R
B K
----
K NB
R
N R
B K
----
K NB
R
R
BN K
----
BK N
N K
B
R R
----
BK N
K
B N
R R
----
BK
N K
B N
R R
----
K N
N K
B
R RB
----
K N
K
B N
R RB
----
K
N K
B N
R RB
----
KBN
R
R
NBK
----
C# code:
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Math;
using static Board;
struct Board
{
public const long Space = 0x0;
public const long King = 0x1;
public const long Knight = 0x2;
public const long Bishop = 0x3;
public const long Rook = 0x4;
private const long Mask = 0xF;
public static readonly Board Empty = new Board(0);
private long b;
private Board(long b) {
this.b = b;
}
private Board WithX(int i, long x) => new Board((this.b & ~(Mask << (i * 4)) | (x << (i * 4))));
public Board WithKing(int i) => this.WithX(i, King);
public Board WithKnight(int i) => this.WithX(i, Knight);
public Board WithBishop(int i) => this.WithX(i, Bishop);
public Board WithRook(int i) => this.WithX(i, Rook);
// Are k1 and k2 adjacent as far as kings are concerned?
public static bool KingAdjacent(int i1, int i2) =>
i1 != i2 && Abs(i1 / 4 - i2 / 4) <= 1 && Abs(i1 % 4 - i2 % 4) <= 1;
public static bool RookAdjacent(int i1, int i2) =>
(Abs(i1 / 4 - i2 / 4) == 1 && i1 % 4 == i2 % 4) ||
(Abs(i1 % 4 - i2 % 4) == 1 && i1 / 4 == i2 / 4);
public static bool BishopAdjacent(int i1, int i2) =>
(Abs(i1 / 4 - i2 / 4) == 1) && (Abs(i1 % 4 - i2 % 4) == 1);
public static bool KnightAdjacent(int i1, int i2) =>
((Abs(i1 / 4 - i2 / 4) == 2) && (Abs(i1 % 4 - i2 % 4) == 1)) ||
((Abs(i1 / 4 - i2 / 4) == 1) && (Abs(i1 % 4 - i2 % 4) == 2));
private long At(int i) => (this.b >> (i * 4)) & Mask;
public bool EmptyAt(int i) => At(i) == Space;
public bool EmptyAt(int x, int y) => EmptyAt(y * 4 + x);
private char CharAt(int i)
{
switch (this.At(i))
{
case King: return 'K';
case Bishop: return 'B';
case Knight: return 'N';
case Rook: return 'R';
default: return ' ';
}
}
private int[] AttackCount()
{
int[] count = new int[16];
void AddAttack(int x, int y)
{
if (x < 0 || x >= 4 || y < 0 || y >= 4) return;
count[y * 4 + x] += 1;
}
for (int i = 0; i < 16; ++i)
{
int x = i % 4;
int y = i / 4;
switch (At(i))
{
case King:
AddAttack(x - 1, y - 1);
AddAttack(x - 1, y);
AddAttack(x - 1, y + 1);
AddAttack(x, y - 1);
AddAttack(x, y + 1);
AddAttack(x + 1, y - 1);
AddAttack(x + 1, y);
AddAttack(x + 1, y + 1);
break;
case Knight:
AddAttack(x - 2, y - 1);
AddAttack(x - 2, y + 1);
AddAttack(x - 1, y - 2);
AddAttack(x - 1, y + 2);
AddAttack(x + 1, y - 2);
AddAttack(x + 1, y + 2);
AddAttack(x + 2, y - 1);
AddAttack(x + 2, y + 1);
break;
case Rook:
for (int x2 = x - 1; x2 >= 0; --x2)
{
AddAttack(x2, y);
if (!this.EmptyAt(x2, y)) break;
}
for (int x2 = x + 1; x2 < 4; ++x2)
{
AddAttack(x2, y);
if (!this.EmptyAt(x2, y)) break;
}
for (int y2 = y - 1; y2 >= 0; --y2)
{
AddAttack(x, y2);
if (!this.EmptyAt(x, y2)) break;
}
for (int y2 = y + 1; y2 < 4; ++y2)
{
AddAttack(x, y2);
if (!this.EmptyAt(x, y2)) break;
}
break;
case Bishop:
for (int x2 = x - 1, y2 = y - 1; x2 >= 0 && y2 >= 0; --x2, --y2)
{
AddAttack(x2, y2);
if (!this.EmptyAt(x2, y2)) break;
}
for (int x2 = x - 1, y2 = y + 1; x2 >= 0 && y2 < 4; --x2, ++y2)
{
AddAttack(x2, y2);
if (!this.EmptyAt(x2, y2)) break;
}
for (int x2 = x + 1, y2 = y - 1; x2 < 4 && y2 >= 0; ++x2, --y2)
{
AddAttack(x2, y2);
if (!this.EmptyAt(x2, y2)) break;
}
for (int x2 = x + 1, y2 = y + 1; x2 < 4 && y2 < 4; ++x2, ++y2)
{
AddAttack(x2, y2);
if (!this.EmptyAt(x2, y2)) break;
}
break;
default:
break;
}
}
return count;
}
public bool Good()
{
int[] count = AttackCount();
for (int i = 0; i < 16; ++i)
{
int c = count[i];
switch (At(i))
{
case King:
if (c != 0) return false;
break;
case Bishop:
case Knight:
case Rook:
if (c != 1) return false;
break;
default:
break;
}
}
return true;
}
public Board Rotate() =>
Empty.WithX(0, At(3))
.WithX(1, At(7))
.WithX(2, At(11))
.WithX(3, At(15))
.WithX(4, At(2))
.WithX(5, At(6))
.WithX(6, At(10))
.WithX(7, At(14))
.WithX(8, At(1))
.WithX(9, At(5))
.WithX(10, At(9))
.WithX(11, At(13))
.WithX(12, At(0))
.WithX(13, At(4))
.WithX(14, At(8))
.WithX(15, At(12));
public Board Reflect() =>
Empty.WithX(0, At(3))
.WithX(1, At(2))
.WithX(2, At(1))
.WithX(3, At(0))
.WithX(4, At(7))
.WithX(5, At(6))
.WithX(6, At(5))
.WithX(7, At(4))
.WithX(8, At(11))
.WithX(9, At(10))
.WithX(10, At(9))
.WithX(11, At(8))
.WithX(12, At(15))
.WithX(13, At(14))
.WithX(14, At(13))
.WithX(15, At(12));
public static bool Equal(Board b1, Board b2)
{
return b1.b == b2.b;
}
public static bool EqualModuloRotationAndReflection(Board b1, Board b2)
{
var current = b1;
if (Equal(current, b2))
return true;
current = current.Rotate();
if (Equal(current, b2))
return true;
current = current.Rotate();
if (Equal(current, b2))
return true;
current = current.Rotate();
if (Equal(current, b2))
return true;
current = b1.Reflect();
if (Equal(current, b2))
return true;
current = current.Rotate();
if (Equal(current, b2))
return true;
current = current.Rotate();
if (Equal(current, b2))
return true;
current = current.Rotate();
if (Equal(current, b2))
return true;
return false;
}
public override string ToString() =>
$@"{CharAt(0)}{CharAt(1)}{CharAt(2)}{CharAt(3)}
{CharAt(4)}{CharAt(5)}{CharAt(6)}{CharAt(7)}
{CharAt(8)}{CharAt(9)}{CharAt(10)}{CharAt(11)}
{CharAt(12)}{CharAt(13)}{CharAt(14)}{CharAt(15)}
";
}
static class Extensions
{
public static IEnumerable<T> DistinctBy<T>(this IEnumerable<T> items, Func<T, T, bool> equal)
{
// Crappy n-squared algorithm is the best we can do without a hash code.
var seen = new List<T>();
foreach (T item in items)
{
if (!seen.Any(x => equal(x, item)))
{
yield return item;
seen.Add(item);
}
}
}
}
class MainClass
{
private static IEnumerable<int> Range(int start) {
for (int i = start; i < 16; ++i)
yield return i;
}
public static void Main(string[] args)
{
var query =
from k1 in Range(0)
let board1 = Empty.WithKing(k1)
from k2 in Range(k1 + 1)
where !KingAdjacent(k1, k2)
let board2 = board1.WithKing(k2)
from r1 in Range(0)
where board2.EmptyAt(r1) && !RookAdjacent(r1, k1) && !RookAdjacent(r1, k2)
let board3 = board2.WithRook(r1)
from r2 in Range(r1 + 1)
where board3.EmptyAt(r2) && !RookAdjacent(r2, k1) && !RookAdjacent(r2, k2)
let board4 = board3.WithRook(r2)
from b1 in Range(0)
where board4.EmptyAt(b1) && !BishopAdjacent(b1, k1) && !BishopAdjacent(b1, k2)
let board5 = board4.WithBishop(b1)
from b2 in Range(b1 + 1)
where board5.EmptyAt(b2) && !BishopAdjacent(b2, k1) && !BishopAdjacent(b2, k2)
let board6 = board5.WithBishop(b2)
from n1 in Range(0)
where board6.EmptyAt(n1) && !KnightAdjacent(n1, k1) && !KnightAdjacent(n1, k2)
let board7 = board6.WithKnight(n1)
from n2 in Range(n1 + 1)
where board7.EmptyAt(n2) && !KnightAdjacent(n2, k1) && !KnightAdjacent(n2, k2)
let board8 = board7.WithKnight(n2)
where board8.Good()
select board8;
var q = query.DistinctBy(EqualModuloRotationAndReflection).ToList();
foreach (var b in q)
Console.WriteLine(b + "----");
Console.WriteLine(q.Count);
}
}
Yet another solution!
N R X R
X X X B
B X X X
K X K N
This solution defied my initial intuition: that the bishops would share diagonals with the two middle squares attacked by the knights - intuitively that would minimise the number of squares under attack, which is quite in line with the problem!
K.K./...R/NB.B/R..Nhas a knight attacking a bishop, for example. – Eric Lippert Dec 06 '17 at 00:40