28
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ I presume this is one piece of each colour of each type (i.e. W-King, B-King, W-Bishop, B-Bishop, etc.)? $\endgroup$ Dec 5, 2017 at 12:05
  • $\begingroup$ Can the king attack? $\endgroup$ Dec 5, 2017 at 12:08
  • $\begingroup$ @TomCarpenter If this is the case, the solution is very simple but if it's not it's seems prety impossible $\endgroup$
    – Skyvask
    Dec 5, 2017 at 12:09
  • 3
    $\begingroup$ All pieces are one color, $\endgroup$
    – Tweakimp
    Dec 5, 2017 at 12:14
  • 1
    $\begingroup$ @Arthur: Sure. K.K./...R/NB.B/R..N has a knight attacking a bishop, for example. $\endgroup$ Dec 6, 2017 at 0:40

7 Answers 7

28
$\begingroup$

I hope I didn't make any mistakes:

enter image description here

Edit : Replace queens by king

$\endgroup$
8
  • $\begingroup$ You have queens where I think you mean to have kings. $\endgroup$
    – Gareth McCaughan
    Dec 5, 2017 at 12:34
  • 1
    $\begingroup$ Yeah i just nether remember how to differencies queens and king but the logic is here :) $\endgroup$
    – Skyvask
    Dec 5, 2017 at 12:36
  • 1
    $\begingroup$ It works with queens swapped for kings. I had a very similar solution with the rooks moved one step closer to the knights. $\endgroup$
    – w l
    Dec 5, 2017 at 12:37
  • $\begingroup$ @wl I think there are the only 2 solutions for this puzzle $\endgroup$
    – Skyvask
    Dec 5, 2017 at 12:39
  • 1
    $\begingroup$ Interesting! In my solution the Kings do not attack, but this one is valid, too. $\endgroup$
    – Tweakimp
    Dec 5, 2017 at 12:40
34
$\begingroup$

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 |  
$\endgroup$
9
  • 1
    $\begingroup$ You can't just divide by eight to get rid of the rotations and reflections. Consider the solution of Jesse Barnett. Since it already has a reflection symmetry, there are only four rotations to get rid of, not eight. $\endgroup$ Dec 5, 2017 at 19:21
  • 4
    $\begingroup$ Nine minutes is not too bad. If you wanted to make it faster there are some things you could do to speed it up. For example, any position where a king is attacked you can prune, and you can prune a lot of those really fast. When you place the first king, you can automatically discard all the positions where the second king is adjacent to the first. That alone will decrease the amount of time you spend in the algorithm by about half! You can then also discard any positioning of the knights that attacks either king. And so on. $\endgroup$ Dec 5, 2017 at 19:28
  • $\begingroup$ Thank you for coding! Can you tell me in how many solutions both kings also dont attack anything? (compare Saeïdryl's answer) $\endgroup$
    – Tweakimp
    Dec 5, 2017 at 20:25
  • 1
    $\begingroup$ @Tweakimp There are two unique such solutions (so times 8 to include their rotations and reflections). One is what Saeidryl found, the other is (0, 3, 9, 14, 8, 11, 12, 15). $\endgroup$
    – Reti43
    Dec 5, 2017 at 23:55
  • 1
    $\begingroup$ It's my bad. I'm under counting. I have a bug... somewhere. $\endgroup$ Dec 6, 2017 at 1:21
23
$\begingroup$

Here is mine with passive kings, some minutes late :

enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ This is the one I thought of, nice! $\endgroup$
    – Tweakimp
    Dec 5, 2017 at 12:54
  • $\begingroup$ Thank you for your validation Tweakimp but Skyvask was faster and his solution is correct, so I think he deserves the green mark more than me ! $\endgroup$
    – Saeïdryl
    Dec 5, 2017 at 12:57
  • $\begingroup$ You are too kind :) I clicked on both of you, I didnt know I can only validate one. $\endgroup$
    – Tweakimp
    Dec 5, 2017 at 13:01
  • $\begingroup$ @Saeïdryl Nice ! I was not able to find a way with king not attacking anyone. $\endgroup$
    – Skyvask
    Dec 5, 2017 at 13:07
  • $\begingroup$ @Skyvask and I was not able to find a way with king attacking someone ! :) I was close to your solution with a circle (I thought it would be a central symmetry) but I could not find it. $\endgroup$
    – Saeïdryl
    Dec 5, 2017 at 13:13
17
$\begingroup$

Here's a solution with the additional constraint that no piece may attack more than one piece:

Solution

$\endgroup$
2
  • 1
    $\begingroup$ @Tas rooks..... $\endgroup$ Dec 6, 2017 at 3:56
  • $\begingroup$ I tried to get a solution where all pieces except kings are attacked once, and all pieces including kings attack one other piece. I haven't found one and don't think there is one. Seems once you have the knights attacking something you can't meet the other criteria. $\endgroup$
    – BobRodes
    Dec 6, 2017 at 19:42
9
$\begingroup$

I also thought of a possible solution:

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).

$\endgroup$
4
  • 1
    $\begingroup$ Cool! On apronus.com/chess/pgnviewer you can create a custom sized board at the bottom. Then click on position setup. $\endgroup$
    – Tweakimp
    Dec 5, 2017 at 16:00
  • $\begingroup$ The rooks aren't attacked though?? $\endgroup$
    – WhatEvil
    Dec 5, 2017 at 21:12
  • 4
    $\begingroup$ @WhatEvil Except by each other... $\endgroup$
    – Brilliand
    Dec 5, 2017 at 21:19
  • $\begingroup$ Oh yes, whoops. $\endgroup$
    – WhatEvil
    Dec 6, 2017 at 9:46
7
$\begingroup$

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);
    }
}
$\endgroup$
6
  • $\begingroup$ Now I'm curious how fast this program runs compared to Reit43's program. $\endgroup$
    – Mr Lister
    Dec 6, 2017 at 10:30
  • $\begingroup$ @MrLister, >>Main() Elapsed=00:00:01.1346445 Look ok to me.. $\endgroup$ Dec 6, 2017 at 14:26
  • $\begingroup$ @MrLister: Pruning boards where a king is attacked with an unblockable attack cuts down the number of boards you have to evaluate for goodness by an enormous amount; that's where the speed comes from. $\endgroup$ Dec 6, 2017 at 14:45
  • $\begingroup$ @EricLippert Thank you for your answer. I have another open chess problem, would you be interested in calculating what the best answer to it is? :) Place as many pieces on a standard chess board as you can. - You are only allowed to place Rooks, Knights and Bishops. - The number of rooks, knights and bishops must be equal. - Every piece has to be attacked by exactly one other piece (similar to this one) $\endgroup$
    – Tweakimp
    Dec 6, 2017 at 15:51
  • $\begingroup$ @Tweakimp: That is a much harder problem! $\endgroup$ Dec 6, 2017 at 21:57
3
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.