Donate to Remove ads

Got a credit card? use our Credit Card & Finance Calculators

Thanks to johnstevens77,Bhoddhisatva,scotia,Anonymous,Cornytiv34, for Donating to support the site

Knights

cinelli
Lemon Slice
Posts: 550
Joined: November 9th, 2016, 11:33 am
Has thanked: 231 times
Been thanked: 160 times

Knights

#235474

Postby cinelli » July 10th, 2019, 9:53 am

.--- --- --- --- --- --- --- ---
| | | | | | | | |
--- --- --- --- --- --- --- ---
| | | | | | | | |
--- --- --- --- --- --- --- ---
| | | | | | | | |
--- --- --- --- --- --- --- ---
| | | | | | | | |
--- --- --- --- --- --- --- ---
| | | | | | | | |
--- --- --- --- --- --- --- ---
| | | | | | | | |
--- --- --- --- --- --- --- ---
| | | | | | | | |
--- --- --- --- --- --- --- ---
| | | | | | | | |
--- --- --- --- --- --- --- ---

This puzzle is to place twelve knights on a chessboard so that every square is either occupied or attacked.

Cinelli

psychodom
Posts: 28
Joined: November 7th, 2016, 8:59 am
Has thanked: 12 times
Been thanked: 3 times

Re: Knights

#235561

Postby psychodom » July 10th, 2019, 3:07 pm

Hopefully the formatting works here:

Code: Select all

.--- --- --- --- --- --- --- ---
|   |   |   |   |   |   |   |   |
 --- --- --- --- --- --- --- ---
|   |   |   |   |   | K |   |   |
 --- --- --- --- --- --- --- ---
|   | K | K |   | K | K |   |   |
 --- --- --- --- --- --- --- ---
|   |   | K |   |   |   |   |   |
 --- --- --- --- --- --- --- ---
|   |   |   |   |   | K |   |   |
 --- --- --- --- --- --- --- ---
|   |   | K | K |   | K | K |   |
 --- --- --- --- --- --- --- ---
|   |   | K |   |   |   |   |   |
 --- --- --- --- --- --- --- ---
|   |   |   |   |   |   |   |   |
 --- --- --- --- --- --- --- ---

cinelli
Lemon Slice
Posts: 550
Joined: November 9th, 2016, 11:33 am
Has thanked: 231 times
Been thanked: 160 times

Re: Knights

#235814

Postby cinelli » July 11th, 2019, 10:30 am

Well solved, Dom. This is also my solution, with its rotational symmetry. I did wonder, though, whether it is unique. But probably not.

Cinelli

Gengulphus
Lemon Quarter
Posts: 4255
Joined: November 4th, 2016, 1:17 am
Been thanked: 2628 times

Re: Knights

#237193

Postby Gengulphus » July 17th, 2019, 9:14 am

cinelli wrote:Well solved, Dom. This is also my solution, with its rotational symmetry. I did wonder, though, whether it is unique. But probably not.

Well, I take it you mean "essentially unique", "unique up to reflection" or something similar, because obviously its mirror image is a non-identical solution. But the rest of what I have to say about it should be treated as a spoiler, I think...

Consider the three squares marked A, B and C in the following diagram of a corner of the chessboard:

+---+---+---+---+..
| A | B | | c |
+---+---+---+---+..
| | C | a | b |
+---+---+---+---+..
| b | a | b | c |
+---+---+---+---+..
| c | | c | |
+---+---+---+---+..
: : : : :

At least one of the square marked A and the two squares marked a must be occupied, otherwise the square marked A is neither occupied nor attacked. Similarly, at least one of the square marked B and the three squares marked b must be occupied, and at least one of the square marked C and the four squares marked c must be occupied. So that corner must contain at least three occupied squares. So must every other corner of the chessboard symmetrically, so:

* It's not possible to do the job with fewer than 12 knights.

* To do the job with exactly 12 knights, each corner must contain exactly 3 occupied squares, and the must be one among the squares marked A or a, one among the squares marked B or b and one among the squares marked C or c.

* So the four unmarked squares must be unoccupied in a solution with exactly 12 knights.

But by a symmetrical argument, the same must apply in the diagram reflected in the top-left to bottom-right diagonal. So the mirror images of the four blank cells must also be blank, which gives us three more blank squares - one of the original four blank squares being on the diagonal and thus identical to its own mirror image.

So dropping the upper/lower case distinction, which has served its purpose, each corner in a 12-knight solution must be of the form:

+---+---+---+---+..
| A | | | C |
+---+---+---+---+..
| | C | A | |
+---+---+---+---+..
| | A | B | C |
+---+---+---+---+..
| C | | C | |
+---+---+---+---+..
: : : : :

with a square marked A, a square marked B and a square marked C occupied, and the blank squares definitely unoccupied. But there is only one square marked B, so that square must be occupied.

Expanding our attention to the full board and reassigning letters, that says that a 12-knight solution must be of the form:

+---+---+---+---+---+---+---+---+
| A | | | B | D | | | C |
+---+---+---+---+---+---+---+---+
| | B | A | | | C | D | |
+---+---+---+---+---+---+---+---+
| | A | * | B | D | * | C | |
+---+---+---+---+---+---+---+---+
| B | | B | | | D | | D |
+---+---+---+---+---+---+---+---+
| H | | H | | | F | | F |
+---+---+---+---+---+---+---+---+
| | G | * | H | F | * | E | |
+---+---+---+---+---+---+---+---+
| | H | G | | | E | F | |
+---+---+---+---+---+---+---+---+
| G | | | H | F | | | E |
+---+---+---+---+---+---+---+---+

with the asterisked squares definitely occupied, one each of the squares marked A, the squared marked B, the squares marked C, the squares marked D, the squares marked E, the squares marked F, the squares marked G and the squares marked H occupied, and the blank squares definitely unoccupied.

Now start looking at how the definitely-unoccupied squares are attacked from occupied squares. Most of them are attacked from the four definitely-occupied squares marked with asterisks: marking such definitely-unoccupied-but-also-definitely-attacked squares with full stops, we get to the following:

+---+---+---+---+---+---+---+---+
| A | . | | B | D | | . | C |
+---+---+---+---+---+---+---+---+
| . | B | A | . | . | C | D | . |
+---+---+---+---+---+---+---+---+
| | A | * | B | D | * | C | |
+---+---+---+---+---+---+---+---+
| B | . | B | . | . | D | . | D |
+---+---+---+---+---+---+---+---+
| H | . | H | . | . | F | | F |
+---+---+---+---+---+---+---+---+
| | G | * | H | F | * | E | |
+---+---+---+---+---+---+---+---+
| . | H | G | . | . | E | F | . |
+---+---+---+---+---+---+---+---+
| G | . | | H | F | | . | E |
+---+---+---+---+---+---+---+---+

But what about the still-blank squares? Restricting our attention to a 5x5 region in the top left corner and moving back to mostly using lower-case letters, we get the following picture:

+---+---+---+---+---+..
| a | . | | b | d |
+---+---+---+---+---+..
| . | b | A | . | . |
+---+---+---+---+---+..
| | A | * | B | d |
+---+---+---+---+---+..
| b | . | B | . | . |
+---+---+---+---+---+..
| h | . | h | . | . |
+---+---+---+---+---+..
: : : : : :

In that, the still-blank square on the top row can only be attacked from the two squares I've left marked with upper-case letters on the third row, and similarly, the still-blank square in the first column can only be attacked from the two squares I've left marked with upper-case letters in the third column. So at least one of the squares marked A and B in the third row must be occupied, and at least one of the squares marked A and B in the third column must be occupied, and they cannot both be marked with the same letter. Furthermore, between them those squares marked A/B must fully account for the single occupied square marked A/a and the single occupied square marked B/b, so all the squares marked a/b must be blank. Together, those mean that the occupied squares in the top-left 4x4 region can only be as shown in (with additional full-stop markings for squares now known to be attacked):

+---+---+---+---+---+..
| . | . | . | . | d |
+---+---+---+---+---+..
| . | . | | . | . |
+---+---+---+---+---+..
| . | * | * | | d |
+---+---+---+---+---+..
| . | . | * | . | . |
+---+---+---+---+---+..
| h | . | h | . | . |
+---+---+---+---+---+..
: : : : : :

or its mirror image when reflected in the top-left-to-bottom-right diagonal. I'll refer to the depicted possibility as the 'clockwise' possibility and its mirror image as the 'anticlockwise' possibility, i.e. basically according to the direction that the small triangle of three occupied squares can be viewed as pointing around the centre of the board.

The same two possibilities exist in the other three 4x4 corners. But now look at the still-blank square in the second row of the depicted 'clockwise' possibility: it can only be attacked from one of the two squares marked d, and neither of those is occupied if the 'anticlockwise' possibility is used in the top-right corner. So if the 'clockwise' possibility is used in the top left corner, it must also be used in the top right corner, and by equivalent arguments, also in the bottom right corner and then also in the bottom left corner. Symmetrically, if the 'anticlockwise' possibility is used in the top left corner, it must also be used in all of the other corners.

So the only solutions are psychodom's solution and its mirror image.


Gengulphus


Return to “Games, Puzzles and Riddles”

Who is online

Users browsing this forum: No registered users and 4 guests