Answers.Body: <p>Here's an 8.5 move sequence that leaves no squares:</p>
  <pre><code>[fen &quot;r3kb1r/pp1nq1pp/4b2n/2pppp2/1P1P1P2/N6P/P1P1P1PR/RNBQKB2 b Qkq - 0 1&quot;]
  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
  </code></pre>
  <p>Edit: 7.5 moves (see comments)</p>
  <pre><code>[fen &quot;rnbqkb2/p1p1p1pr/Q6p/1p1p1p2/2PPnP2/4B2N/PP1NP1PP/R3KB1R b KQq - 3 8&quot;]
  1. c4 b5 2. d4 d5 3. f4 f5 4. Qa4 Nf6 5. Qa6 Ne4 6. Be3 h6 7. Nd2 Rh7 8. Nh3
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-11T04:14:02.633Z
Answers.Text: 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?
Answers.UserDisplayName: Laska
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-11T04:51:30.690Z
Answers.Text: @Laska I used a SAT solver to find the piece configuration.
Answers.UserDisplayName: Ben
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-11T05:03:56.930Z
Answers.Text: @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.
Answers.UserDisplayName: Ben
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-11T05:21:18.460Z
Answers.Text: Can your SAT get all maximal arrangements of 32-34 points?
Answers.UserDisplayName: Laska
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-11T15:48:55.437Z
Answers.Text: @Laska: Did you consider the remote possibility that some 31-position could be reached faster? A formal minimality proof would need that too.
Answers.UserDisplayName: Hauke Reddmann
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-11T16:46:43.550Z
Answers.Text: @Hauke the main ask was to minimize the number of captures - and in fact zero turns out to be possible. That does imply that it's based on 32-34-pointer. The speed of reaching it is secondary, but could be primary in a different task
Answers.UserDisplayName: Laska
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-11T03:14:16.873Z
Answers.LastActivityDate: 2021-02-11T05:06:26.530Z
Answers.LastEditDate: 2021-02-11T05:06:26.530Z
Answers.UserDisplayName: Ben
Answers.Body: <p>Playing around with Laska's board position, here is a 10 move sequence that gets there (with some pieces moved around):</p>
  <pre><code>[fen &quot;rnbq1bn1/p2pp1p1/1p2k1Br/2p4p/6PP/1NPP1p1N/PP2PP2/R1BQK2R b KQ - 1 10&quot;]
  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
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-10T23:53:22.537Z
Answers.LastActivityDate: 2021-02-10T23:53:22.537Z
Answers.UserDisplayName: Michael Gottlieb
Answers.Body: <h2>TL;DR: a solution!</h2>
  <pre><code>[FEN &quot;rnbq1bn1/p2pp1p1/1p2r1Nk/2p4p/6PN/1BPP1p1P/PP2PP2/R1BQK2R w - - 0 1&quot;]
  </code></pre>
  <p>32 pieces, no squares.</p>
  <p>According to <a href="https://oeis.org/A240443" rel="nofollow noreferrer">OEIS sequence A240443</a> and this particular <a href="https://oeis.org/A240443/a240443.png" rel="nofollow noreferrer">pair of examples</a>, 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.)</p>
  <p>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 &amp; 7.5 moves).</p>
  <p>The rest of this post gives more details.</p>
  <h2>Generalization to abstract math problem</h2>
  <p>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.</p>
  <p>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 &quot;quartets&quot;, 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.</p>
  <p>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.</p>
  <p>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.</p>
  <h2>Bounds for shortest (non-unique) proof games</h2>
  <p>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.</p>
  <p>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 &amp; 2, and at least 9 units on ranks 7 &amp; 8. This constrains somewhat the search for interesting 32-34-pointers.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-10T08:52:03.670Z
Answers.Text: For Upright squares : 2x2,3x3,4x4,5x5,6x6,7x7,8x8 =49+36+25+16+9+4+1=140
Answers.UserDisplayName: TSLF
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-10T09:11:53.507Z
Answers.Text: 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]
Answers.UserDisplayName: TSLF
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-10T09:46:52.090Z
Answers.Text: You may move both white and black pieces not remove from start setup. Although the position above is attainable too many captures was done.
Answers.UserDisplayName: TSLF
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-10T09:50:04.493Z
Answers.Text: @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.
Answers.UserDisplayName: Laska
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-10T09:58:12.773Z
Answers.Text: @TLSF, yes total of 336 not 352: I double-counted the non-chiral tilted guys, thanks
Answers.UserDisplayName: Laska
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-10T10:01:09.737Z
Answers.Text: @Laksa- the more than 32 pieces have been proven
Answers.UserDisplayName: TSLF
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-10T10:03:06.410Z
Answers.Text: @TLSF: have you got a reference to that, please? No point redoing this math programming if someone's already done that. Might as well get the result and apply to the chess
Answers.UserDisplayName: Laska
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-10T10:09:43.933Z
Answers.Text: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/119578/discussion-between-tslf-and-laska).
Answers.UserDisplayName: TSLF
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-10T06:58:36.410Z
Answers.LastActivityDate: 2021-02-11T10:48:55.237Z
Answers.LastEditDate: 2021-02-11T10:48:55.237Z
Answers.UserDisplayName: Laska
Body: <pre><code> [FEN &quot;&quot;]
  </code></pre>
  <p>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.</p>
  <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-10T05:28:10.093Z
Comments.Text: New idea as far as I know, and I'm sure that someone will also aim for shortest unique proof game too...
Comments.UserDisplayName: Laska
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-10T06:42:46.740Z
Comments.Text: 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.
Comments.UserDisplayName: Remellion
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-10T07:26:39.137Z
Comments.Text: 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).
Comments.UserDisplayName: Laska
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-11T15:50:05.177Z
Comments.Text: And now after it is solved, same question with rectangles! :-)I
Comments.UserDisplayName: Hauke Reddmann
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-12T21:24:07.137Z
Comments.Text: How many rectangles are there in a chessboard?  length not equal width
Comments.UserDisplayName: TSLF
Tags: <problems><puzzles><mathematics>
Title: Square Free Position
ThreadText: # Square Free Position
  
  (Asked by: username_0 on 2021-02-10)
  
  ```
   [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?
  
  **Tags:** problems, puzzles, mathematics
  
  > **Comments:**
  > **username_1**: New idea as far as I know, and I'm sure that someone will also aim for shortest unique proof game too...  
  > **username_2**: 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.  
  > **username_1**: 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).  
  > **username_3**: And now after it is solved, same question with rectangles! :-)I  
  > **username_0**: How many rectangles are there in a chessboard?  length not equal width  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2021-02-10. Score: 10 | Accepted answer
  
  ## 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](https://oeis.org/A240443) and this particular [pair of examples](https://oeis.org/A240443/a240443.png), 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.
  
  > **Comments:**
  > **username_0**: For Upright squares : 2x2,3x3,4x4,5x5,6x6,7x7,8x8 =49+36+25+16+9+4+1=140  
  > **username_0**: 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]  
  > **username_0**: You may move both white and black pieces not remove from start setup. Although the position above is attainable too many captures was done.  
  > **username_1**: @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.  
  > **username_1**: @TLSF, yes total of 336 not 352: I double-counted the non-chiral tilted guys, thanks  
  > **username_0**: @Laksa- the more than 32 pieces have been proven  
  > **username_1**: @TLSF: have you got a reference to that, please? No point redoing this math programming if someone's already done that. Might as well get the result and apply to the chess  
  > **username_0**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/119578/discussion-between-username_0-and-username_1).  
  
  ---
  
  ### Answer by username_5 on 2021-02-10. Score: 5
  
  Playing around with username_1'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
  
  ```
  
  
  ---
  
  ### Answer by username_4 on 2021-02-11. Score: 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
  
  ```
  
  > **Comments:**
  > **username_1**: 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?  
  > **username_4**: @username_1 I used a SAT solver to find the piece configuration.  
  > **username_4**: @username_1 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.  
  > **username_1**: Can your SAT get all maximal arrangements of 32-34 points?  
  > **username_3**: @username_1: Did you consider the remote possibility that some 31-position could be reached faster? A formal minimality proof would need that too.  
  > **username_1**: @username_3 the main ask was to minimize the number of captures - and in fact zero turns out to be possible. That does imply that it's based on 32-34-pointer. The speed of reaching it is secondary, but could be primary in a different task  
  
  ---
  
  