On a Chessboard, place as many chess pieces as you can.
Position the center of each piece on the center of a square.
Avoid placing any 4 pieces at the corners of a square (even a tilted square).
How many pieces can you place?
4
-
$\begingroup$ a square formed by pieces at (3,1)(1,2)(4,3)(2,4) also count ? $\endgroup$– Jamal SenjayaNov 1, 2016 at 6:04
-
$\begingroup$ Why yes, that's right. You gave me an idea. Tilted square also count $\endgroup$– TSLFNov 1, 2016 at 6:43
-
2$\begingroup$ I find this a difficult puzzle, because not only finding a solution, but the mere verification of a candidate solution seems to be quite difficult. $\endgroup$– MatsmathNov 1, 2016 at 10:51
-
1$\begingroup$ OEIS A240443 $\endgroup$– RobPrattApr 5, 2020 at 2:57
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
3
I found a solution with 34 generated with some code I wrote. But as the comments mention - this problem is tough to find solutions to and just as hard to verify a given solution. The code I wrote does not to solve for all possibilities so it is still possible that this is not optimum (or correct!).
Text Based:
O O O O O * O O * O * O * O O * O * * * * * O O O * * * O O O * O * * O * O * * O * * O * O O O O O * * * * * * * O O O O * O O
Edit: Original upload had 31. Putting a little bit of a random into the code I got a result with 34. I've replaced the 31 solution with the 34.
-
-
-
1$\begingroup$ @TSLF - Still looking for 35. On the other side, the smallest complete board (a piece cannot be added without creating a square) that I have found is 25. $\endgroup$– ScottNov 2, 2016 at 12:29
$\begingroup$
$\endgroup$
5
I find 29 chess pieces, but not sure if this is the optimum solution or not.
answered Nov 1, 2016 at 8:05
-
$\begingroup$ If I understand Tilted squares properly, I think you might have a titled square on points (4,1) - (0, 3) - (2, 7) - (6, 5). The four points are separated by a shift of (2, 4). $\endgroup$– ScottNov 1, 2016 at 15:54
-
1$\begingroup$ @Scott Can you explain your coordinate system, please? $\endgroup$– hexominoNov 1, 2016 at 16:04
-
$\begingroup$ 0 based coordinates. Top Left = (0,0) and Bottom Right (7,7). As for the offset, I am not sure how best to explain it. But I think of it like a knight in chess that can move 2 squares and 4 squares instead of the usual 1 square and 2 squares. $\endgroup$– ScottNov 1, 2016 at 16:12
-
1$\begingroup$ Should have mentioned point
(a, b)is downaoverb. That might be a better way to say it. $\endgroup$– ScottNov 1, 2016 at 16:27 -
$\begingroup$ @Scott : OK, I did not realize it. So there is a hole my solution. $\endgroup$ Nov 2, 2016 at 5:43
$\begingroup$
$\endgroup$
1
Me and two friends solved the problem using a backtracking algorithm with a lot of pruning. You can find the code we used on my GitHub. The computation considered 4096834073 states in a little less than 10 minutes. We made heavy use of symmetrical, geometrical and constraint-driven properties to limit the number of states.
As Scott showed, at least 34 pieces could be placed on the chessboard without forming any squares. Our exhaustive search proves (assuming the code is correct) this is the maximum.
-
$\begingroup$ Hi I would be very interested to see your code, but it's no longer on Github. Please contact me, thanks! $\endgroup$– LaskaFeb 10, 2021 at 12:39
$\begingroup$
$\endgroup$
3
A solution with 35 pieces:
XXXXXXXX X.X.X..X X.....XX XX.....X X.....XX XX.....X X..X.X.X XXXXXXX.
Shown above the no upright square solution with 35 pieces. And the no. of possible squares.
-
1$\begingroup$ There are quite a few squares here, I think. If you use algebraic chess notation, for example, you have one with vertices b8, h7, g1, a2 $\endgroup$– hexominoNov 1, 2016 at 16:02
-
$\begingroup$ Yes, this solution was made without the tilted squares requirement. $\endgroup$– w lNov 1, 2016 at 16:04
-
$\begingroup$ @wl-good one, but the unedited OP requires no "square" so any rectangular formation that has 4 equal length side should be considered. $\endgroup$– TSLFNov 2, 2016 at 11:52