7
 [FEN ""]

For the purposes of this question, a “square” is a set of four occupied cells on the chessboard whose centres form a geometric square. The cell may have any orientation. For example: a1,a2,b2,b1 or a2,b3,c2,b1 or a2,b4,d3,c1.

In the starting position, there are 24 squares that are formed by four Black and/or White pieces. Two squares are tilted. If regular moves/captures are played for Black and White, what could be the maximum number of pieces that can remain on the board without four them forming a square?

5
  • 1
    New idea as far as I know, and I'm sure that someone will also aim for shortest unique proof game too... – Laska Feb 10 at 5:28
  • There are actually more than 24 - b1-a7-g8-h2 is also a square, and there are 2 of those. I have a 32-piece solution not counting these tilted squares. – Remellion Feb 10 at 6:42
  • 2
    I make it 24 as OP stated: 14 with side 1, 3 of side 5, 4 of side 6 1 of side 7, and 2 tilted of side sqrt(37). – Laska Feb 10 at 7:26
  • And now after it is solved, same question with rectangles! :-)I – Hauke Reddmann Feb 11 at 15:50
  • How many rectangles are there in a chessboard? length not equal width – TSLF Feb 12 at 21:24
10

TL;DR: a solution!

[FEN "rnbq1bn1/p2pp1p1/1p2r1Nk/2p4p/6PN/1BPP1p1P/PP2PP2/R1BQK2R w - - 0 1"]

32 pieces, no squares.

According to OEIS sequence A240443 and this particular pair of examples, 34 is the maximum possible number of square-free points on an 8x8 grid. As long as each file has at least two points in ranks 2-6, this is likely to give us a solution, if we just drop a couple of the points. (I picked two from the more crowded files.)

This is not intended to be optimal in number of moves - it just shows that a capture-free solution is possible, and is a starting-point for the search for the shortest (non-unique) proof game (which we now know lies somewhere between 4.5 & 7.5 moves).

The rest of this post gives more details.

Generalization to abstract math problem

Overall, I make it 336 possible “squares” on the chessboard, of which 140 are non-tilted and 196 tilted. Since about 60% are tilted, avoiding the tilted squares in a general position is the harder challenge, although there were only 2 tilted squares to avoid in the game array.

Following an exploration into positions where ranks 3-6 were empty, I think the best general approach may be to forget about the chess for a while. We've got 64 nodes, and 336 "quartets", each of 4 nodes. What's the smallest subset of 64 which contains a member of each quartet? There is no a priori reason why that smallest subset should be greater than 32. (I.e. we might be able to have more than 32 pieces on a square-free board!) Anyway, after that smallest subset is determined, we can see how we can arrange chess pieces to avoid those squares on the board.

Having got a solution, the next thing might be to determine all maximal arrangements of 32-34 square-free points which allow for 2 pawns/file. (It’s the 34-pointers which are most interesting, although it’s possible that some position with 32 or 33 point might not be extensible to 34, so would be missed in any trawl of 34-pointers.) Can then look at the smallest number of moves to reach positions which have 32 pieces. In such open capture-free positions, it seems very unlikely that a unique proof game exists.

If anyone does get a list of these maximal 32-34 point diagrams, I would be grateful if they can be posted in GitHub. There is some python code in OEIS, I saw.

Bounds for shortest (non-unique) proof games

An earlier reconnaissance to look at homebase positions (i.e. where all surviving units are on their apparent starting squares) proved that a maximum of 23 units can remain on the board. A valid implication for the general problem is that any (non-unique or unique) proof game to a square-free position must have at least 4.5 moves (i.e. White moves at least 5 times). This bound is unlikely to be attainable.

Elsewhere in this thread, there is a solution in 7.5 moves. Any faster solution must therefore have at least 9 units on ranks 1 & 2, and at least 9 units on ranks 7 & 8. This constrains somewhat the search for interesting 32-34-pointers.

8
  • 1
    For Upright squares : 2x2,3x3,4x4,5x5,6x6,7x7,8x8 =49+36+25+16+9+4+1=140 – TSLF Feb 10 at 8:52
  • 1
    For tilted squares: [2/2,2/3,2/4,2/5,2/6,2/7]=36+25+16+9+4+1 [3/2,3/3,3/4,3/5,3/6]=25+16+9+4+1 [4/2,4/3,4/4,4/5]=16+9+4+1 [5/2,5/3,5/4]=9+4+1 [6/2,6/3]=4+1 [7/2=1] – TSLF Feb 10 at 9:11
  • 1
    You may move both white and black pieces not remove from start setup. Although the position above is attainable too many captures was done. – TSLF Feb 10 at 9:46
  • @TLSF yes as I explained, the homebase was just a first exploration. I am sure that a more economical solution is possible by shifting pieces around. BUT what I have shown absolutely best solution for the subcase where there are no pieces in ranks 3-6. And as I went on to say, the general problem is probably better tackled by forgetting about the chess, and reintroducing that at the end. – Laska Feb 10 at 9:50
  • @TLSF, yes total of 336 not 352: I double-counted the non-chiral tilted guys, thanks – Laska Feb 10 at 9:58
5

Playing around with Laska's board position, here is a 10 move sequence that gets there (with some pieces moved around):

[fen "rnbq1bn1/p2pp1p1/1p2k1Br/2p4p/6PP/1NPP1p1N/PP2PP2/R1BQK2R b KQ - 1 10"]
1. d3 c5 2. c3 h5 3. g4 Rh6 4. h4 f5 5. Nh3 Kf7 6. Bg2 f4 7. Be4 Ke6 8. Bg6 f3 9. Nd2 b6 10. Nb3
4

Here's an 8.5 move sequence that leaves no squares:

[fen "r3kb1r/pp1nq1pp/4b2n/2pppp2/1P1P1P2/N6P/P1P1P1PR/RNBQKB2 b Qkq - 0 1"]
1. d4 d5 2. b4 c5 3. f4 e5 4. h3 f5 5. Nf3 Be6 6. Nfd2 Nd7 7. Nc4 Nh6 8. Nca3 Qe7 9. Rh2

Edit: 7.5 moves (see comments)

[fen "rnbqkb2/p1p1p1pr/Q6p/1p1p1p2/2PPnP2/4B2N/PP1NP1PP/R3KB1R b KQq - 3 8"]
1. c4 b5 2. d4 d5 3. f4 f5 4. Qa4 Nf6 5. Qa6 Ne4 6. Be3 h6 7. Nd2 Rh7 8. Nh3
6
  • Hi this is great! I think it can be slightly trimmed from 8.5 to 8.0 by r3kb1r/pp1np1pp/4b2n/2ppPp2/1P1P1P2/q6P/P1P1N1PR/RNBQKB2. I haven't checked fully that there are no squares though. Does this come from a 34-point diagram, or how do you know? – Laska Feb 11 at 4:14
  • 1
    @Laska I used a SAT solver to find the piece configuration. – Ben Feb 11 at 4:51
  • 1
    @Laska Also, swapping the pawn and knight on e2 and e5 and flipping the colours allows us to save another ply, and get down to 7.5 moves. – Ben Feb 11 at 5:03
  • Can your SAT get all maximal arrangements of 32-34 points? – Laska Feb 11 at 5:21
  • 1
    @Laska: Did you consider the remote possibility that some 31-position could be reached faster? A formal minimality proof would need that too. – Hauke Reddmann Feb 11 at 15:48

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.