27
$\begingroup$

Here's a problem that was posed to me but I haven't seen anything about it anywhere online! I'm beginning to wonder if I'm just getting played!

You have a chessboard and sixteen pawns. The puzzle is to have all sixteen pawns on the board such that no three are collinear (three in a row). It can be considered with Cartesian coordinates; the three pawns can't make the same slope, even at unequal distances (ex: 0,0 & 1,2 & 3,6 is not allowed).

I'm thinking that the solution must be so complex that there must be a logic, strategy, or algorithm for this. Could people help me out? Thanks!

$\endgroup$
  • 3
    $\begingroup$ can you place each pawn on top of each other? $\endgroup$ – JMP Sep 6 '16 at 3:41
  • 2
    $\begingroup$ No three (or more) pawns may be in any straight line of any direction. This is a special case of the no-three-in-line problem. Martin Gardner reprints the best-known solutions for all board sizes up to 16x16 in chapter 5 of Penrose Tiles to Trapdoor Ciphers, pub. Freeman, ISBN 0-7167-1987-8. $\endgroup$ – Rosie F Sep 6 '16 at 6:22
  • 1
    $\begingroup$ @Jamal commenting on an answer to this question cites a result from Achim Flammenkamp's web site. The portal to his research on the no-3-in-line problem is here. $\endgroup$ – Rosie F Sep 6 '16 at 8:59
  • $\begingroup$ ah... but must the pawns follow the chess rules? IE must start in rows 2 and 7 for the appropriate colors? or are all 64 spaces available to all pawns? $\endgroup$ – xQbert Sep 6 '16 at 15:38
  • $\begingroup$ @JonMarkPerry They cannot be placed on top of each other. Each has their own square. $\endgroup$ – Steve DSign Sep 6 '16 at 17:51
33
$\begingroup$

The Algoritm is :

Create a 4x4 table which each 2 pawns cannot be in 1 row, 1 column, and 1 diagonal including those diagonals obtained by "wrapping around" the edges.

Then

Expand it into 8x8 chess board
enter image description here

Here is the complete solution from Achim Flammenkamp Ph.D. There are totally 57 solutions

enter image description here

$\endgroup$
  • $\begingroup$ Ignoring rotations/reflections, is this a unique solution? $\endgroup$ – greenturtle3141 Sep 6 '16 at 4:41
  • $\begingroup$ @greenturtle3141 I do not know, I just find the answer today, with my second hypothesis (my first hypothesis is wrong). Maybe there is another solution. $\endgroup$ – Jamal Senjaya Sep 6 '16 at 4:44
  • 2
    $\begingroup$ check this : wwwhomes.uni-bielefeld.de/achim/no3in/no8.gif. It shoes all the solutions in tiny pixels. $\endgroup$ – Jamal Senjaya Sep 6 '16 at 8:01
  • 1
    $\begingroup$ @JamalSenjaya Ah, good ol' Achim Flammenkamp, who has contributed so much to this and other areas of mathematics. $\endgroup$ – Rosie F Sep 6 '16 at 8:16
  • 5
    $\begingroup$ then, "than" is to express a comparison, not a time sequence. $\endgroup$ – Federico Sep 6 '16 at 10:35
1
$\begingroup$

Note that each of the eight rows of the chessboard must contain exactly two pawns. If a row contained 3 or more pawns, it would violate the conditions of the problem. And if a row contained less than 2 pawns, then some other row would have to have 3 or more pawns, again violating the conditions of the problem.

There are 8*7/2 = 28 ways to place a pair of pawns on a given row.

So, with 8 rows, there are only 28^8 = 377x10^9 possible ways of solving the problem. This is a large number but within the realm of a computer search.

$\endgroup$
  • $\begingroup$ Starting at the third row, the number of choices will go down rapidly. $\endgroup$ – gnasher729 Sep 6 '16 at 21:39
  • 2
    $\begingroup$ Since there must be two pawns in each column, you have only one choice for the last row, and only at most six choices for the seventh row. $\endgroup$ – gnasher729 Sep 6 '16 at 21:45
  • $\begingroup$ Is anyone trying this approach, then? $\endgroup$ – ghosts_in_the_code Sep 14 '16 at 14:55
-2
$\begingroup$

The answer is based on Rotational symmetry.enter image description here

$\endgroup$
  • $\begingroup$ Hello, welcome to Puzzling.SE. Can you please add more explanation to your answer. Meanwhile why don't you take the tour to earn your first badge. $\endgroup$ – u_ndefined Jul 9 '18 at 5:29
  • 1
    $\begingroup$ A8, B6 and D2 are on the same line. (You have the chess board sideways, but luckily the position is symmetrical, so the coordinates work in any orientation.) $\endgroup$ – Bass Jul 9 '18 at 6:46
  • $\begingroup$ Similarly, A1, D2, G3 are collinear, as are F7, G4, H1; B6, E7, H8; and probably others. $\endgroup$ – Rubio Jul 11 '18 at 18:21

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.