No Square Allowed

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?

• a square formed by pieces at (3,1)(1,2)(4,3)(2,4) also count ? – Jamal Senjaya Nov 1 '16 at 6:04
• Why yes, that's right. You gave me an idea. Tilted square also count – TSLF Nov 1 '16 at 6:43
• 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. – Matsmath Nov 1 '16 at 10:51

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.

• I accept this as most pieces on board – TSLF Nov 2 '16 at 12:10
• @Scott- Can there be a solution for 35? – TSLF Nov 2 '16 at 12:19
• @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. – Scott Nov 2 '16 at 12:29

I find 29 chess pieces, but not sure if this is the optimum solution or not.

• 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). – Scott Nov 1 '16 at 15:54
• @Scott Can you explain your coordinate system, please? – hexomino Nov 1 '16 at 16:04
• 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. – Scott Nov 1 '16 at 16:12
• Should have mentioned point (a, b) is down a over b. That might be a better way to say it. – Scott Nov 1 '16 at 16:27
• @Scott : OK, I did not realize it. So there is a hole my solution. – Jamal Senjaya Nov 2 '16 at 5:43

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.

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.

• 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 – hexomino Nov 1 '16 at 16:02
• Yes, this solution was made without the tilted squares requirement. – w l Nov 1 '16 at 16:04
• @wl-good one, but the unedited OP requires no "square" so any rectangular formation that has 4 equal length side should be considered. – TSLF Nov 2 '16 at 11:52