Two knights and two rooks on a 5-by-5 chessboard

Question

In how many different ways can two knights and two rooks be placed on a $5\times5$ chessboard, so that no piece attacks another piece?

Answer 1

I ran a simple brute-force computer program, that simply iterates through all possibilities and counts them.

It found:

2184 solutions.

This number is not reduced for symmetry, so each arrangement may have been counted up to 8 times (4 rotations and their mirror images).

The trivial C# source code I used for this below.

Edit: I have now counted the number of symmetries of all the solutions, and the results are:

252 solutions with no symmetry (counted 8 times)
36 solutions with only mirror symmetry along diagonal (counted 4 times)
4 solutions with only 180 degree rotational symmetry (counted 4 times)
4 solutions with mirror and rotation symmetries (counted 2 times)
252*8 + 36*4 + 4*4 + 4*2 = 2184
252 + 36 + 4 + 4 = 296 essentially unique solutions

The solutions with only rotational symmetry are:

. R . . .    . R . . .    . R . . .    . . . . .
K . . . .    . . K . .    . . . . K    . R . . .
. . . . .    . . . . .    . . . . .    K . . . K
. . . . K    . . K . .    K . . . .    . . . R .
. . . R .    . . . R .    . . . R .    . . . . .

The ones with both rotation and reflection symmetry are:

R . . . .    R . . . .    K . . . .    K . . . .
. K . . .    . . . K .    . R . . .    . . . R .
. . . . .    . . . . .    . . . . .    . . . . .
. . . K .    . K . . .    . . . R .    . R . . .
. . . . R    . . . . R    . . . . K    . . . . K

Source code:

  private static long count = 0;
  private static void Main()
  {
     Rook1();
  }
  private static void Rook1()
  {
     for (int r1x = 0; r1x < 5; r1x++)
     {
        for (int r1y = 0; r1y < 5; r1y++)
        {
           Rook2(r1x, r1y);
        }
     }
  }
  private static void Rook2(int r1x, int r1y)
  {
     for (int r2x = r1x+1; r2x < 5; r2x++)
     {
        for (int r2y = 0; r2y < 5; r2y++)
        {
           if (r1y == r2y) continue;
           Knight1(r1x, r1y, r2x, r2y);
        }
     }
  }
  private static void Knight1(int r1x, int r1y, int r2x, int r2y)
  {
     for (int k1x = 0; k1x < 5; k1x++)
     {
        if (k1x == r1x || k1x == r2x) continue;
        for (int k1y = 0; k1y < 5; k1y++)
        {
           if (k1y == r1y || k1y == r2y) continue;
           if (Math.Abs(k1x - r1x) == 1 && Math.Abs(k1y - r1y) == 2) continue;
           if (Math.Abs(k1x - r1x) == 2 && Math.Abs(k1y - r1y) == 1) continue;
           if (Math.Abs(k1x - r2x) == 1 && Math.Abs(k1y - r2y) == 2) continue;
           if (Math.Abs(k1x - r2x) == 2 && Math.Abs(k1y - r2y) == 1) continue;
           Knight2(r1x, r1y, r2x, r2y, k1x, k1y);
        }
     }
  }
  private static void Knight2(int r1x, int r1y, int r2x, int r2y, int k1x, int k1y)
  {
     for (int k2x = k1x; k2x < 5; k2x++)
     {
        if (k2x == r1x || k2x == r2x) continue;
        for (int k2y = 0; k2y < 5; k2y++)
        {
           if (k2x == k1x && k2y <= k1y) continue;
           if (k2y == r1y || k2y == r2y) continue;
           if (Math.Abs(k2x - r1x) == 1 && Math.Abs(k2y - r1y) == 2) continue;
           if (Math.Abs(k2x - r1x) == 2 && Math.Abs(k2y - r1y) == 1) continue;
           if (Math.Abs(k2x - r2x) == 1 && Math.Abs(k2y - r2y) == 2) continue;
           if (Math.Abs(k2x - r2x) == 2 && Math.Abs(k2y - r2y) == 1) continue;
           if (Math.Abs(k2x - k1x) == 1 && Math.Abs(k2y - k1y) == 2) continue;
           if (Math.Abs(k2x - k1x) == 2 && Math.Abs(k2y - k1y) == 1) continue;
           count++;
           Console.WriteLine( "{8}: R{0}{1} R{2}{3} K{4}{5} K{6}{7}", r1x+1, r1y+1, r2x+1, r2y+1, k1x+1, k1y+1, k2x+1, k2y+1, count);
        }
     }
  }

Answer 2

Partial solution

I'd start with placing the rooks. If they don't hit each other, it means they are in different rows and different columns. That is, wherever they are actually placed, they allow two knights to be placed in the intersections in the other three rows and columns. This gives an upper bound for the possible placements:
the first rook can be placed on any of the 25 cells (factor of 25);
the second rook on the 16 cells which are neither same row, nor same column (factor of 16);
the two rooks cannot be differentiated (factor of 1/2);
the first knight on one of the remaining 9 tiles (factor of 9);
the other knight on as well, but not on the same tile (factor of 8);
the knight can be swapped as well (factor of 1/2);
which gives 7200 configurations, but again, these contain the ones, where the knights can hit each other or the rooks, so the final answer will be somewhat lower.

EDIT: As Jaap Scherphuis pointed out, a lower bound I tried to give in a previous version of my answer had a flawed calculation.

Answer 3

Even if I was a few minutes late I still want to post this because I'm really proud of my work and I invested some time in it.
I've brute forced it and got

2184 solutions.

I chose PHP as my weapon.
The script below can be extended to check for other pieces just by creating the additional classes like Queen, Bishop and implementing the method attack that returns true or false depending if the current position of a piece attacks or not a certain square.

<?php

class ReachedEndException extends Exception {}

class Point
{
    /**
     * @var int
     */
    private $x;
    /**
     * @var int
     */
    private $y;
    public function __construct($x, $y)
    {
        $this->setX($x);
        $this->setY($y);
    }

    /**
     * @return int
     */
    public function getX()
    {
        return $this->x;
    }

    /**
     * @param $x
     * @return $this
     */
    public function setX($x)
    {
        $this->x = $x;
        return $this;
    }

    /**
     * @return int
     */
    public function getY()
    {
        return $this->y;
    }

    /**
     * @param $y
     */
    public function setY($y)
    {
        $this->y = $y;
    }

    /**
     * @param Point $p
     * @return bool
     */
    public function equals(Point $p)
    {
        return ($this->getX() == $p->getX() && $this->getY() == $p->getY());
    }

    /**
     * used for debugging
     *
     * @return string
     */
    public function __toString()
    {
        return '('.$this->x.', '.$this->y.')';
    }
}

interface PieceInterface
{
    /**
     * @param Point $p
     * @return bool
     */
    public function attack(Point $p);
}

abstract class Piece implements PieceInterface
{
    /**
     * @var Point
     */
    protected $position;
    /**
     * @var string
     */
    protected $notation = '';

    /**
     * Piece constructor.
     * @param Point|null $position
     */
    public function __construct(Point $position = null)
    {
        $this->position = $position;
    }

    /**
     * @return Point
     */
    public function getPosition()
    {
        return $this->position;
    }

    /**
     * @return mixed
     */
    public function getNotation()
    {
        return $this->notation;
    }

    /**
     * @param Point $position
     */
    public function setPosition($position)
    {
        $this->position = $position;
    }

    /**
     * used for debugging
     * @return string
     */
    public function __toString()
    {
        return $this->notation.$this->getPosition();
    }

    public abstract function attack(Point $p);

}

class Rook extends Piece implements PieceInterface
{
    /**
     * @var string
     */
    protected $notation = 'R';

    /**
     * @param Point $p
     * @return bool
     */
    public function attack(Point $p)
    {
        if (!$this->position) {
            return false;
        }
        return ($this->getPosition()->getX() == $p->getX() || $this->getPosition()->getY() == $p->getY());
    }


}

class Knight extends Piece implements PieceInterface
{
    /**
     * @var string
     */
    protected $notation = 'K';

    /**
     * @param Point $p
     * @return bool
     */
    public function attack(Point $p)
    {
        if (!$this->position) {
            return false;
        }
        $thisX = $this->getPosition()->getX();
        $thisY = $this->getPosition()->getY();
        $pointX = $p->getX();
        $pointY = $p->getY();
        if (abs($thisX - $pointX) == 2 && abs($thisY - $pointY) == 1) {
            return true;
        }
        if (abs($thisX - $pointX) == 1 && abs($thisY - $pointY) == 2) {
            return true;
        }
        return false;
    }
}

class App
{
    /**
     * board X size
     * @var int
     */
    private $boardX;
    /**
     * board Y size
     * @var int
     */
    private $boardY;
    /**
     * pieces to add on the table
     * @var Piece[]
     */
    protected $piecesToAdd = array();
    /**
     * all solutions
     * @var string[]
     */
    protected $solutions = array();
    /**
     * already added pieces
     * @var Piece[]
     */
    private $pieces = array();

    /**
     * App constructor.
     * @param $boardX
     * @param null $boardY
     * @param $piecesToAdd
     */
    public function __construct($piecesToAdd, $boardX, $boardY = null)
    {
        if (is_null($boardY)) {
            $boardY = $boardX;
        }
        $this->boardX = $boardX;
        $this->boardY = $boardY;
        $this->piecesToAdd = $piecesToAdd;

    }

    /**
     * add a piece on the board
     * @param Piece $p
     * @param Point $point
     * @return bool
     */
    public function addPiece(Piece $p, Point $point)
    {
        $p->setPosition($point);
        $canPlace = true;
        //check of the piece does not attack the other set pieces or if it's not attacked by one
        foreach ($this->pieces as $piece) {
            if (
                $p->getPosition()->equals($piece->getPosition())
                || $p->attack($piece->getPosition()) ||
                $piece->attack($p->getPosition())
            ) {
                $canPlace = false;
            }
        }
        if ($canPlace) {
            $this->pieces[] = $p;
            $this->pieces = array_values($this->pieces);
            return true;
        } else {
            //if a piece cannot be added, move to the next position
            $nextPoint = $this->incrementPoint($point);
            if ($nextPoint) {
                return $this->addPiece($p, $nextPoint);
            }
        }
        //if there is no valid position return false
        return false;
    }

    /**
     * get the next position where you can add a piece if you need to move one
     * @return bool|Point
     */
    private function getNextPosition()
    {
        $nextPosition = false;
        while (!$nextPosition) {
            //remove last piece and increment the position for the previous one.
            $piece = end($this->pieces);
            if (!$piece) {
                throw new ReachedEndException();
            }
            $position = clone $piece->getPosition();
            $nextPosition = $this->incrementPoint($position);
            $this->removePiece(count($this->pieces) - 1);
        }
        return $nextPosition;
    }

    /**
     * do the dew
     * @return App
     */
    public function execute()
    {
        $currentPosition = new Point(0, 0);
        $added = true;
        while (true) {
            while ($added && !$this->isBoardFilled()) {
                $pieceToAdd = $this->piecesToAdd[count($this->pieces)];
                $added = $this->addPiece($pieceToAdd, $currentPosition);
                //if a piece was added start the next one from top left corner
                if ($added) {
                    $currentPosition = new Point(0, 0);
                }
            }
            //if we cannot add a piece, remove the last one(s) and check the next valid position
            if (!$added) {
                try {
                    $currentPosition = $this->getNextPosition();
                } catch (ReachedEndException $e) {
                    //it means we cannot move anything arround anymore
                    return $this;
                }
                $added = true;
            } elseif ($this->isBoardFilled()) {
                //if the board is in a valid position save the state
                $solution = $this->printBoardState();
                //remember a hash of the position to avoid duplicates
                $hash = sha1($solution);
                $this->solutions[$hash] = $solution;
                try {
                    $currentPosition = $this->getNextPosition();
                } catch (ReachedEndException $e) {
                    //it means we are done
                    return $this;
                }
            } else {
                $added = true;
                //start over
                $currentPosition = new Point(0, 0);
            }
        }
        return $this;
    }

    /**
     * form a readable string with the solutions
     * @return string
     */
    public function printSolutions()
    {
        $string = '';
        $increment = 1;
        foreach ($this->solutions as $solution) {
            $string .= 'Solution '.$increment++.'<br />'.$solution.'<br />';
        }
        return $string;
    }

    /**
     * remove a piece
     * @param $index
     * @return App
     */
    private function removePiece($index)
    {
        unset($this->pieces[$index]);
        return $this;
    }

    /**
     * check if all pieces are on the board
     * @return bool
     */
    public function isBoardFilled()
    {
        return count($this->pieces) == count($this->piecesToAdd);
    }

    /**
     * generate the board configuration string
     * @param string $positionSeparator
     * @param string $blank
     * @param string $lineSeparator
     * @return string
     */
    private function printBoardState($positionSeparator = '|', $blank = '--', $lineSeparator = '<br />')
    {
        $board = array();
        $text = '';
        foreach ($this->pieces as $piece) {
            $position = $piece->getPosition();
            $board[$position->getX()][$position->getY()] = $piece->getNotation();
        }
        for ($i = 0;$i<$this->boardX; $i++) {
            $text .= $positionSeparator;
            for ($j = 0;$j<$this->boardY; $j++) {
                if (isset($board[$i][$j])) {
                    $text .= $board[$i][$j];
                } else {
                    $text .= $blank;
                }
                $text .= $positionSeparator;
            }
            $text .= $lineSeparator;
        }
        return $text;
    }

    /**
     * get the next valid point
     * @param Point $p
     * @return bool|Point
     */
    private function incrementPoint(Point $p)
    {
        if ($p->getX() == $this->boardX - 1) {
            if ($p->getY() == $this->boardY - 1) {
                return false; //reached the end
            }
            return new Point(0, $p->getY() + 1);
        }
        return new Point($p->getX()+1, $p->getY());
    }

    /**
     * take a whild guess
     * @return string
     */
    public function debug()
    {
        $string = "state: ";
        foreach ($this->pieces as $piece) {
            $string.= ' '.$piece.'--';
        }
        return $string.'<br />';
    }
}

//configure the pieces to be added
$pieces = array(
    new Rook(),
    new Rook(),
    new Knight(),
    new Knight()
);
$boardSize = 5;
$app = new App($pieces, $boardSize);
//run it
$app->execute();
//see if it worked
echo $app->printSolutions();

you can give it a try by copy/pasting it into http://phpfiddle.org/.

You will see results like:

Solution 1  
|R |--|--|--|--|  
|--|R |--|--|--|  
|--|--|K |--|--|  
|--|--|--|--|--|  
|--|--|K |--|--|  

or

Solution 481
|--|--|--|--|--|
|--|K |--|--|--|
|R |--|--|--|--|
|--|--|--|R |--|
|--|--|K |--|--|

Just chose 2 at random.