Answers.Body: <p>This is part of a whole genre of chess problem, retrograde analysis. People keep coming up with new tricks in positions that make it impossible to reach them, possibly in surprising ways.</p>
  
  <p>I'm copying a diagram here from the question <a href="https://chess.stackexchange.com/questions/23539/searching-for-a-where-is-the-black-king-puzzle">Searching for a &quot;where is the black king&quot; puzzle?</a>:</p>
  
  <pre><code>8/8/8/1r1b4/B7/8/8/3k4 w - - 0 1
  </code></pre>
  
  <p>Problem: place a white king on the board to make the position legal</p>
  
  <p><strong>Spoiler:</strong></p>
  
  <blockquote class="spoiler">
    <p> It's on c3. The reasoning is that it's black to move, so white's king can't be on b3 as it would be in check. So black is in check by the Ba4. But then the king must have just left b3, and it was in double check there. But how can it be in double check by a rook on b5 and a bishop on d5? Only by an en passant capture. There was a black pawn on b4, a white pawn on c2, and the last moves were 1.c2-c4 b4xc3e.p.++ 2.Kb3xc3.</p>
  </blockquote>
  
  <p>This means that <em>the position with the white king placed on that square is reachable, but with the king anywhere else it's unreachable</em>. That's not easy to spot just by checking items from a list!</p>
  
  <p>That's an easy retrograde analysis problem. Some of them need quite deep analysis, like several pieces have left the bottom rank, they could each have left it over some square, but only in the order they're in on the back row, and they must have left in some other order -- but I can't find a problem like that now.</p>
  
  <p>I believe your list can be made arbitrarily long.</p>
  
  <p>As for algorithms, there are better ways than the brute force approach I described in my comment on the question: there has been work on <em>finding proof games</em> in retrograde analysis. These take it a step further: they find a game that reaches the given position <em>in a set number of moves</em>. That should also be enough to find whether the position can be reached at all.</p>
  
  <p>I found the software <strong><a href="http://natch.free.fr/Natch.html" rel="nofollow noreferrer">Natch</a></strong> that can do this.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-18T10:11:15.403Z
Answers.Text: Natch (and Euclide, Popeye, [Jacobi](http://wismuth.com/jacobi/) and the like) are proof game solvers, designed to solve chess problems known as *proof games*. However, they have limitations: you need to specify the number of moves to reach the position, they are very slow for anything on the order of 20+ moves, and they might not work very well for positions without any typical retro features to guide them. Failure of the program to find a game should not be taken as proof of illegality either; some proof game problems are known to trip them up too.
Answers.UserDisplayName: Remellion
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-18T08:39:15.813Z
Answers.LastActivityDate: 2019-12-01T09:35:56.693Z
Answers.LastEditDate: 2019-12-01T09:35:56.693Z
Answers.UserDisplayName: RemcoGerlich
Answers.Body: <p>Here is a retro which needs deep analysis:</p>
  <pre><code>[Title &quot;Thierry le Gleuher; Economy Records in Add Unit(s) Problems, 5A&quot;]
  [StartFlipped &quot;0&quot;]
  [fen &quot;B5bn/5PrR/5prN/6pk/7p/5P2/PPPPPP2/KR1Q2N1 w KQkq - 0 1&quot;]
  </code></pre>
  <p>The stipulation is &quot;Add the missing unit(s)&quot;. A solution may be found in <a href="https://pdb.dieschwalbe.de/P1227636" rel="nofollow noreferrer">entry P1227636 in PDB</a>. In brief:</p>
  <blockquote class="spoiler">
  <p> To disentangle Black's kingside, White must retract most pieces back home so that White can retract g2xf3. Interleaved with these White moves are 19 Black moves. But, all this time, Black has no retrotempi with units in the diagram, so they must be provided by the added units. The only way is to add black pawns on a3, b3, c3, d3, e3. Each provides 4 retrotempi, except that the b and d pawns can't both retract home, because the bishop on g8 will need to retract to c8 eventually.</p>
  </blockquote>
  <p>Thus the position would be illegal if</p>
  <blockquote class="spoiler">
  <p> 5 black pawns were added but any of them were nearer rank 7, because Black would run out of retrotempi, but it would take deep analysis to show that this is the case.</p>
  </blockquote>
  <p>This might be the sort of situation RemcoGerlich was thinking of, seeing that</p>
  <blockquote class="spoiler">
  <p> Some White pieces need to leave the back rank and move back in a different order.</p>
  </blockquote>
  <p>In case you thought that there's a simpler way to add units:</p>
  <blockquote class="spoiler">
  <p> A Black piece captured White's c1 bishop on c1. White is not missing anything else, so no Black pawn ever left its file. Thus White's 3 captures g2xf3 and hxgxf were of Black's 3 missing pieces: the f8 bishop, the queen and a knight. So we may add Black pawns but not a piece.</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-21T12:15:35.033Z
Answers.LastActivityDate: 2022-01-30T03:39:49.983Z
Answers.LastEditDate: 2022-01-30T03:39:49.983Z
Answers.UserDisplayName: Rosie F
Answers.Body: <p>First of all, <strong>if you can't find a way to reach a position from an opening board, then it's likely illegal.</strong> I say <em>likely</em> only because you may have missed something.</p>
  
  <p><a href="https://www.chess.com/forum/view/fun-with-chess/illegal-position-contest" rel="nofollow noreferrer">Here</a> is a fairly nice collection of illegal positions that I ran across a while ago on a <a href="https://chess.com" rel="nofollow noreferrer">chess.com</a> forum. Some of the positions are extremely subtle. One common theme I noticed that isn't on your list is <strong>doubled pawns</strong> when there cannot be doubled pawns (for example, doubled pawns with no pieces captured, doubled pawns on the 2nd and third rows when the only piece of the opponent's captured is a bishop of the color of the unmoved pawn on the second row, etc, etc.)</p>
  
  <p>Another one is <strong>impossible move order</strong> - something that usually happens with knights. For example, it is impossible for it to be black's turn with all of the pieces in their starting position - this is because of the white-black, white-black, white-black pattern of the knight's moves.</p>
  
  <p>There are <strong>many</strong> more good examples, I'm sure. If anyone thinks of any, leave a comment and I'll add it in!</p>
  
  <p>It is probable that neither our posts nor the link I gave will ever provide a comprehensive list of all the <em>categories</em> of illegal positions, but again - if it can't be reached from the beginning of the game, it's illegal.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-18T00:23:04.637Z
Answers.LastActivityDate: 2019-01-18T00:23:04.637Z
Answers.UserDisplayName: Brandon_J
Body: <p>If one of the following is true, a position is <strong>not</strong> reachable from the starting position by a series of legal moves:</p>
  
  <ol>
  <li>One side has two or more kings or one side has no kings;</li>
  <li>One side has  a total of 10 or more queens and pawns, or a total of 11 or more rooks and pawns, or a total of 11 or more knights and pawns, or a total of 10 or more bishops of the same colour and pawns;</li>
  <li>One side has a total number of more than 16 pieces;</li>
  <li>At least one pawn is in the first rank or eighth rank;</li>
  <li>Both kings are being checked;</li>
  <li>The kings can capture each other in the next move;</li>
  <li>At least one bishop is in an "impossible square" blocked by pawns in their starting positions, such as the following:</li>
  </ol>
  
  <p><a href="https://i.sstatic.net/8mqPb.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/8mqPb.png" alt="enter image description here"></a></p>
  
  <ol start="8">
  <li>One king is being "impossibly" checked or checkmated such as the following (this should also include the case where a king is being checked by three or more pieces): (I am not sure how to define this more precisely);</li>
  </ol>
  
  <p><a href="https://i.sstatic.net/rznBt.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/rznBt.png" alt="enter image description here"></a></p>
  
  <ol start="9">
  <li>One side is checking and it is his turn.</li>
  </ol>
  
  <p>I am sure that this list is not exhaustive. Does one know a complete list? Is there an algorithm determing whether a position is reachable from the starting position by a series of legal moves?</p>
  
  <p><strong>Edit</strong>: I would also add the following:</p>
  
  <ul>
  <li>One side has more than 8 pawns.</li>
  </ul>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-17T14:19:39.750Z
Comments.Text: Yes, there is an algorithm, but it's like solving the game of chess -- work backwards by taking moves back to see if you can reach the starting position. Takes longer than the life expectancy of the universe, but it is an algorithm.
Comments.UserDisplayName: RemcoGerlich
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-17T14:23:53.313Z
Comments.Text: @RemcoGerlich, how about a more reasonable algorithm? At least can be finished by engines in a reasonable amount of time, say a few hours?
Comments.UserDisplayName: Zuriel
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-17T14:46:34.850Z
Comments.Text: It will be ahrd to reach a fulll list without precising what you take for granted, otherwise: - chessboard round and not square - three colors of pieces - Pieces not in the middle of squares but on the edges - Libellules, stones and cameleon instead of kings, bishop and pawns. - two goalsposts, one ball and 22 players wearing shorts - etc.
Comments.UserDisplayName: Evargalo
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-17T14:50:12.923Z
Comments.Text: @Evargalo you beat me!
Comments.UserDisplayName: Zuriel
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-17T17:59:27.960Z
Comments.Text: It is not in general easy to determine if a position is legal. How else would we have so many problems in the field of [retrograde analysis](https://www.janko.at/Retros/index.htm)? There are much subtler illegal positions that do not involve any trivial, visually obvious features in the position. The way in general is to try "retracting" moves from the diagram to reach the starting position, but in a smart way. And no engine has been developed for this, it's extremely tricky even for humans to not misjudge.
Comments.UserDisplayName: Remellion
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-18T00:07:31.033Z
Comments.Text: @Remellion Indeed! Such questions which generally pertain to the connectivity of the underlying state space sometimes end up as research topics in mathematics and stat mech. Papers such as *sequencing chess* come to mind, and [many discussions on mathoverflow](https://mathoverflow.net/questions/138133/what-proportion-of-chess-positions-that-one-can-set-up-on-the-board-using-a-leg). To the OP, additional easy rules: any position where an opponent's pawn has passed your pawn on a given file when no trades have occurred, or doubled pawns without trades, or triple pawns but with 1 trade, etc.
Comments.UserDisplayName: Ellie
Tags: <theory>
Title: How does one know if a position is not reachable from a series of legal moves from the starting position?
ThreadText: # How does one know if a position is not reachable from a series of legal moves from the starting position?
  
  (Asked by: username_0 on 2019-01-17)
  
  If one of the following is true, a position is **not** reachable from the starting position by a series of legal moves:
  
  1. One side has two or more kings or one side has no kings;
  2. One side has a total of 10 or more queens and pawns, or a total of 11 or more rooks and pawns, or a total of 11 or more knights and pawns, or a total of 10 or more bishops of the same colour and pawns;
  3. One side has a total number of more than 16 pieces;
  4. At least one pawn is in the first rank or eighth rank;
  5. Both kings are being checked;
  6. The kings can capture each other in the next move;
  7. At least one bishop is in an "impossible square" blocked by pawns in their starting positions, such as the following:
  
  [![enter image description here](https://i.sstatic.net/8mqPb.png)](https://i.sstatic.net/8mqPb.png)
  
  8. One king is being "impossibly" checked or checkmated such as the following (this should also include the case where a king is being checked by three or more pieces): (I am not sure how to define this more precisely);
  
  [![enter image description here](https://i.sstatic.net/rznBt.png)](https://i.sstatic.net/rznBt.png)
  
  9. One side is checking and it is his turn.
  
  I am sure that this list is not exhaustive. Does one know a complete list? Is there an algorithm determing whether a position is reachable from the starting position by a series of legal moves?
  
  **Edit**: I would also add the following:
  
  * One side has more than 8 pawns.
  
  **Tags:** theory
  
  > **Comments:**
  > **username_1**: Yes, there is an algorithm, but it's like solving the game of chess -- work backwards by taking moves back to see if you can reach the starting position. Takes longer than the life expectancy of the universe, but it is an algorithm.  
  > **username_0**: @username_1, how about a more reasonable algorithm? At least can be finished by engines in a reasonable amount of time, say a few hours?  
  > **username_2**: It will be ahrd to reach a fulll list without precising what you take for granted, otherwise: - chessboard round and not square - three colors of pieces - Pieces not in the middle of squares but on the edges - Libellules, stones and cameleon instead of kings, bishop and pawns. - two goalsposts, one ball and 22 players wearing shorts - etc.  
  > **username_0**: @username_2 you beat me!  
  > **username_3**: It is not in general easy to determine if a position is legal. How else would we have so many problems in the field of [retrograde analysis](https://www.janko.at/Retros/index.htm)? There are much subtler illegal positions that do not involve any trivial, visually obvious features in the position. The way in general is to try "retracting" moves from the diagram to reach the starting position, but in a smart way. And no engine has been developed for this, it's extremely tricky even for humans to not misjudge.  
  > **username_4**: @username_3 Indeed! Such questions which generally pertain to the connectivity of the underlying state space sometimes end up as research topics in mathematics and stat mech. Papers such as *sequencing chess* come to mind, and [many discussions on mathoverflow](https://mathoverflow.net/questions/138133/what-proportion-of-chess-positions-that-one-can-set-up-on-the-board-using-a-leg). To the OP, additional easy rules: any position where an opponent's pawn has passed your pawn on a given file when no trades have occurred, or doubled pawns without trades, or triple pawns but with 1 trade, etc.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2019-01-18. Score: 4
  
  This is part of a whole genre of chess problem, retrograde analysis. People keep coming up with new tricks in positions that make it impossible to reach them, possibly in surprising ways.
  
  I'm copying a diagram here from the question [Searching for a "where is the black king" puzzle?](https://chess.stackexchange.com/questions/23539/searching-for-a-where-is-the-black-king-puzzle):
  
  ```
  8/8/8/1r1b4/B7/8/8/3k4 w - - 0 1
  
  ```
  
  Problem: place a white king on the board to make the position legal
  
  **Spoiler:**
  
  > It's on c3. The reasoning is that it's black to move, so white's king can't be on b3 as it would be in check. So black is in check by the Ba4. But then the king must have just left b3, and it was in double check there. But how can it be in double check by a rook on b5 and a bishop on d5? Only by an en passant capture. There was a black pawn on b4, a white pawn on c2, and the last moves were 1.c2-c4 b4xc3e.p.++ 2.Kb3xc3.
  
  This means that *the position with the white king placed on that square is reachable, but with the king anywhere else it's unreachable*. That's not easy to spot just by checking items from a list!
  
  That's an easy retrograde analysis problem. Some of them need quite deep analysis, like several pieces have left the bottom rank, they could each have left it over some square, but only in the order they're in on the back row, and they must have left in some other order -- but I can't find a problem like that now.
  
  I believe your list can be made arbitrarily long.
  
  As for algorithms, there are better ways than the brute force approach I described in my comment on the question: there has been work on *finding proof games* in retrograde analysis. These take it a step further: they find a game that reaches the given position *in a set number of moves*. That should also be enough to find whether the position can be reached at all.
  
  I found the software **[Natch](http://natch.free.fr/Natch.html)** that can do this.
  
  > **Comments:**
  > **username_3**: Natch (and Euclide, Popeye, [Jacobi](http://wismuth.com/jacobi/) and the like) are proof game solvers, designed to solve chess problems known as *proof games*. However, they have limitations: you need to specify the number of moves to reach the position, they are very slow for anything on the order of 20+ moves, and they might not work very well for positions without any typical retro features to guide them. Failure of the program to find a game should not be taken as proof of illegality either; some proof game problems are known to trip them up too.  
  
  ---
  
  ### Answer by username_5 on 2019-01-21. Score: 4
  
  Here is a retro which needs deep analysis:
  
  ```
  [Title "Thierry le Gleuher; Economy Records in Add Unit(s) Problems, 5A"]
  [StartFlipped "0"]
  [fen "B5bn/5PrR/5prN/6pk/7p/5P2/PPPPPP2/KR1Q2N1 w KQkq - 0 1"]
  
  ```
  
  The stipulation is "Add the missing unit(s)". A solution may be found in [entry P1227636 in PDB](https://pdb.dieschwalbe.de/P1227636). In brief:
  
  > To disentangle Black's kingside, White must retract most pieces back home so that White can retract g2xf3. Interleaved with these White moves are 19 Black moves. But, all this time, Black has no retrotempi with units in the diagram, so they must be provided by the added units. The only way is to add black pawns on a3, b3, c3, d3, e3. Each provides 4 retrotempi, except that the b and d pawns can't both retract home, because the bishop on g8 will need to retract to c8 eventually.
  
  Thus the position would be illegal if
  
  > 5 black pawns were added but any of them were nearer rank 7, because Black would run out of retrotempi, but it would take deep analysis to show that this is the case.
  
  This might be the sort of situation username_1 was thinking of, seeing that
  
  > Some White pieces need to leave the back rank and move back in a different order.
  
  In case you thought that there's a simpler way to add units:
  
  > A Black piece captured White's c1 bishop on c1. White is not missing anything else, so no Black pawn ever left its file. Thus White's 3 captures g2xf3 and hxgxf were of Black's 3 missing pieces: the f8 bishop, the queen and a knight. So we may add Black pawns but not a piece.
  
  
  ---
  
  ### Answer by username_6 on 2019-01-18. Score: 2
  
  First of all, **if you can't find a way to reach a position from an opening board, then it's likely illegal.** I say *likely* only because you may have missed something.
  
  [Here](https://www.chess.com/forum/view/fun-with-chess/illegal-position-contest) is a fairly nice collection of illegal positions that I ran across a while ago on a [chess.com](https://chess.com) forum. Some of the positions are extremely subtle. One common theme I noticed that isn't on your list is **doubled pawns** when there cannot be doubled pawns (for example, doubled pawns with no pieces captured, doubled pawns on the 2nd and third rows when the only piece of the opponent's captured is a bishop of the color of the unmoved pawn on the second row, etc, etc.)
  
  Another one is **impossible move order** - something that usually happens with knights. For example, it is impossible for it to be black's turn with all of the pieces in their starting position - this is because of the white-black, white-black, white-black pattern of the knight's moves.
  
  There are **many** more good examples, I'm sure. If anyone thinks of any, leave a comment and I'll add it in!
  
  It is probable that neither our posts nor the link I gave will ever provide a comprehensive list of all the *categories* of illegal positions, but again - if it can't be reached from the beginning of the game, it's illegal.
  
  
  ---
  
  