6
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ help? is this an ongoing contest of some sort? $\endgroup$ – lois6b Jan 25 '17 at 11:21
  • $\begingroup$ @Closevoter: This isn't a math question. This is a chess puzzle. However, it may be from a contest, so then it should be removed/closed (not sure). $\endgroup$ – Mithical Jan 25 '17 at 11:31
  • 1
    $\begingroup$ @Iois6b what makes u think that this is a contest question? this is combinatorics question and i am not sure why someone voted to close it. it is pretty good question actually! $\endgroup$ – Oray Jan 25 '17 at 16:12
  • $\begingroup$ @Mithrandir I guess it's a little of a chess knowledge + lot of maths $\endgroup$ – Techidiot Jan 25 '17 at 16:14
  • 1
    $\begingroup$ This seems only solvable by either manual or computational case by case analysis or brute force. $\endgroup$ – greenturtle3141 Jan 25 '17 at 17:26
6
$\begingroup$

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);
        }
     }
  }
$\endgroup$
  • $\begingroup$ Ah. I was 20 minutes late, but I'm glad I got the same result using a different weapon. Although I think I might have over-engineered it a bit. :) $\endgroup$ – Marius Jan 26 '17 at 14:16
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I'm not so sure that your lower bound calculations are valid. When you give 2000 as a lower bound, that should mean that your calculation shows that there are at least 2000 solutions. You have not established that the 5x4/2 arrangements of the knights that you choose to restrict yourself to all give rise to a solution because they could still attack one or both of the rooks. $\endgroup$ – Jaap Scherphuis Jan 26 '17 at 10:58
  • $\begingroup$ You're right, @JaapScherphuis. I realized that my answer is basically incorrect, as I somehow missed that knights can hit rooks as well, not just the other way around. I plan to improve the upper bound I gave as well. $\endgroup$ – elias Jan 26 '17 at 12:47
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Did you just divide by 4 to exclude rotations? Because I'm not sure if you can just do to get the right answer $\endgroup$ – Ivo Beckers Jan 26 '17 at 14:22
  • $\begingroup$ @IvoBeckers. I guess you are right. I will remove it before other people realize my stupidity. Thanks. $\endgroup$ – Marius Jan 26 '17 at 14:23
  • $\begingroup$ The reason that you can't do that is because some rotations for example are symmetrical. For example put the Rooks in opposing corners and the knights in same opposing corners of the middle 3x3 grid. If you rotate that 180 degrees you get exactly the same. this solution only has therefore only 2 seperate rotations instead of 4 $\endgroup$ – Ivo Beckers Jan 26 '17 at 14:24
  • $\begingroup$ I just realized it as soon as I read your first comment. $\endgroup$ – Marius Jan 26 '17 at 14:25
  • $\begingroup$ I've done the symmetry counts now and added them to my answer. $\endgroup$ – Jaap Scherphuis Jan 26 '17 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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