How do you know when a FEN position is legal?

Question

I am making a research on validating FEN positions, at first it is obvious the basics things to look for, such as checking if there are only two kings and making sure the rows or columns add up and those kinds of things. But what other checks should I do to completely make sure a FEN is legal?.

Answer 1

Here is a well organized list that should validate 99.99%+ of common positions:

Board:

• There are exactly 8 ranks (rows).
• The sum of the empty squares and pieces add to 8 for each rank (row).
• There are no consecutive numbers for empty squares.

Kings:

• See if there is exactly one w_king and one b_king.
• Make sure kings are separated and are at least 1 square apart.

Checks:

• Non-active color is not in check.
• Active color is checked less than 3 times (triple check is impossible); in case of 2 that it is never pawn+(pawn, bishop, knight), bishop+bishop, knight+knight.

Pawns:

• There are no more than 8 pawns from each color.
• There aren't any pawns in first or last rank (row) since they're either in a wrong start position or they should have promoted.
• In the case of en passant square; see if it was legally created (e.g it must be on the x3 or x6 rank, there must be a pawn (from the correct color) in front of it, and the en passant square and the one behind it are empty).
• Prevent having more promoted pieces than missing pawns (e.g extra_pieces = Math.max(0, num_queens-1) + Math.max(0, num_rooks-2) + Math.max(0, num_knights-2) + Math.max(0, num_bishops-2) and then extra_pieces <= (8-num_pawns)). A bit more processing-intensive is to count the light-squared bishops and dark-squared bishops separately, then do Math.max(0, num_lightsquared_bishops-1) and Math.max(0, num_darksquared_bishops-1). Another thing worth mentioning is that, whenever the extra_pieces is not 0, the other side must have less than 16 pieces because for a pawn to promote it needs to walk past another pawn in front and that can only happen if the pawn goes missing (taken or playing with a handicap) or the pawn shifts its file (column), in both cases decreasing the total of 16 pieces for the other side.
• The pawn formation is possible to reach (e.g in case of multiple pawns in a single col, there must be enough enemy pieces missing to make that formation), here are some useful rules:

1. it is impossible to have more than 6 pawns in a single file (column) (because pawns can't exist in the first and last ranks).
2. the minimum number of enemy missing pieces to reach a multiple pawn in a single col B to G 2=1, 3=2, 4=4, 5=6, 6=9 ___ A and H 2=1, 3=3, 4=6, 5=10, 6=15, for example, if you see 5 pawns in A or H, the other player must be missing at least 10 pieces from his 15 captureable pieces.
3. if there are white pawns in a2 and a3, there can't legally be one in b2, and this idea can be further expanded to cover more possibilities.

Castling:

• If the king or rooks are not in their starting position; the castling ability for that side is lost (in the case of king, both are lost).

Bishops:

• Look for bishops in the first and last ranks (rows) trapped by pawns that haven't moved, for example:

1. a bishop (any color) trapped behind 3 pawns.
2. a bishop trapped behind 2 non-enemy pawns (not by enemy pawns because we can reach that position by underpromoting pawns, however if we check the number of pawns and extra_pieces we could determine if this case is possible or not).

Non-jumpers:

• (Avoid this if you want to validate Fisher's Chess960) If there are non-jumpers enemy pieces in between the king and rook and there are still some pawns without moving; check if these enemy pieces could have legally gotten in there. Also, ask yourself: was the king or rook needed to move to generate that position? (if yes, we need to make sure the castling abilities reflect this).
• If all 8 pawns are still in the starting position, all the non-jumpers must not have left their initial rank (also non-jumpers enemy pieces can't possibly have entered legally), there are other similar ideas, like if the white h-pawn moved once, the rooks should still be trapped inside the pawn formation, etc.

Half/Full move Clocks:

• In case of an en passant square, the half move clock must equal to 0.
• HalfMoves <= ((FullMoves-1)*2)+(if BlackToMove 1 else 0), the +1 or +0 depends on the side to move.
• The HalfMoves must be x >= 0 and the FullMoves x >= 1.
• If the HalfMove clock indicates that some reversible moves were played and you can't find any combination of reversible moves that could have produced this amount of Halfmoves (taking castling rights into account, forced moves, etc), example: a side with many pawns and a king with castling rights and a rook (the HalfMove clock should not have been able to increase for this side).

Other:

• Make sure the FEN contains all the parts that are needed (e.g active color, castling ability, en passant square, etc).

---

Note: there is no need to make the 'players should not have more than 16 pieces' check because the points 'no more than 8 pawns' + 'prevent extra promoted pieces' + the 'exactly one king' should already cover this point.

Note2: these rules are intended to validate positions arising from the starting position of normal chess, some of the rules will invalidate some positions from Chess960 (exception if started from arrangement Nº518) and generated puzzles so avoid them to get a functional validator.

Answer 2

\s*([rnbqkpRNBQKP1-8]+\/){7}([rnbqkpRNBQKP1-8]+)\s[bw-]\s(([a-hkqA-HKQ]{1,4})|(-))\s(([a-h][36])|(-))\s\d+\s\d+\s*

Here's a regular expression that I use to ensure that a FEN string is actually valid. It doesn't do any testing for a legal/illegal position, but it's a good starting point.

Answer 3

For the others, there is a simple function in Stockfish engine, that validates a FEN String.

bool Position::is_valid_fen(const std::string &fen) {
   std::istringstream iss(fen);
   std::string board, side, castleRights, ep;

   if (!iss) return false;

   iss >> board;

   if (!iss) return false;

   iss >> side;

   if (!iss) {
      castleRights = "-";
      ep = "-";
   } else {
      iss >> castleRights;
      if (iss)
         iss >> ep;
      else
         ep = "-";
   }

   // Let's check that all components of the supposed FEN are OK.
   if (side != "w" && side != "b") return false;
   if (castleRights != "-" && castleRights != "K" && castleRights != "Kk"
       && castleRights != "Kkq" && castleRights != "Kq" && castleRights !="KQ"
       && castleRights != "KQk" && castleRights != "KQq" && castleRights != "KQkq"
       && castleRights != "k" && castleRights != "q" && castleRights != "kq"
       && castleRights != "Q" && castleRights != "Qk" && castleRights != "Qq"
       && castleRights != "Qkq")
      return false;
   if (ep != "-") {
      if (ep.length() != 2) return false;
      if (!(ep[0] >= 'a' && ep[0] <= 'h')) return false;
      if (!((side == "w" && ep[1] == '6') || (side == "b" && ep[1] == '3')))
         return false;
   }

   // The tricky part: The board.
   // Seven slashes?
   if (std::count(board.begin(), board.end(), '/') != 7) return false;
   // Only legal characters?
   for (int i = 0; i < board.length(); i++)
      if (!(board[i] == '/' || (board[i] >= '1' && board[i] <= '8')
            || piece_type_is_ok(piece_type_from_char(board[i]))))
         return false;
   // Exactly one king per side?
   if (std::count(board.begin(), board.end(), 'K') != 1) return false;
   if (std::count(board.begin(), board.end(), 'k') != 1) return false;
   // Other piece counts reasonable?
   size_t wp = std::count(board.begin(), board.end(), 'P'),
      bp = std::count(board.begin(), board.end(), 'p'),
      wn = std::count(board.begin(), board.end(), 'N'),
      bn = std::count(board.begin(), board.end(), 'n'),
      wb = std::count(board.begin(), board.end(), 'B'),
      bb = std::count(board.begin(), board.end(), 'b'),
      wr = std::count(board.begin(), board.end(), 'R'),
      br = std::count(board.begin(), board.end(), 'r'),
      wq = std::count(board.begin(), board.end(), 'Q'),
      bq = std::count(board.begin(), board.end(), 'q');
   if (wp > 8 || bp > 8 || wn > 10 || bn > 10 || wb > 10 || bb > 10
       || wr > 10 || br > 10 || wq > 9 || bq > 10
       || wp + wn + wb + wr + wq > 15 || bp + bn + bb + br + bq > 15)
      return false;

   // OK, looks close enough to a legal position. Let's try to parse
   // the FEN and see!
   Position p;
   p.from_fen(board + " " + side + " " + castleRights + " " + ep);
   return p.is_ok(true);
}

Answer 4

There is nothing in the FEN specification saying that the represented position must be reachable from the initial array. Proving that a given position is reachable from the initial array is an unsolved problem.

In a valid FEN string, the half move count must be in agreement with the en passant target square; if a target square is present, then the half move count must be zero. the half move count must also be in agreement with the full move number; e.g., a half move count of ten is incompatible with a full move number of three.

Answer 5

Coming to the party late.

Firstly I do not think it’s possible to validate 100% that a position is legal as the questioners asks. There are tens of thousands of retroanalytic problems which dance creatively on the border of legality and some of the reasons why a position is illegal are extremely subtle. I believe that the problem of legality is likely to be NP-complete (as the board size scales) although I haven’t seen any published results along those lines. Certainly features such as impostors, retro-shielding, tempo (both in races and in parity), blocking, castling right disruption, en passant and Ceriani-Frolkin promotions (including exotica such as Schnoebelen) as well as such recondite matters as dead position rule are not going to yield to simple rules.

So given that this broad program is likely unachievable, how far should one go in checking candidate positions?

If it’s for a conventional program to support orthodox over the board play then it might be appropriate to have checks as suggested in the top answers to pick up some typos like board size not right - that’s a common one if the engine does not support altered board sizes.

A programmer may enjoy specifying further legality checks but I’ve found from using many diagramming tools that less is more from a UX perspective.

I may want to show a mating matrix for example, which would only be a partial position. It’s distracting to insist that the uninvolved king be shown.

Or I may want to show a range of endgame positions in which one side has a definite win. This may involve having numerous bKs.

Even knowing that one is just focusing on forward play analysis for non-fairy chess only, I think validation should be modest.

It’s not possible to 100% validate whether a position is legal, but why should validation matter? We can play chess whether or not the position happens to derive from the starting position (so-called “game array”). There might be a very interesting position to analyse but it just happens that it’s illegal.

For example there’s a welll-known class of endgame zugzwang positions with wBa1 wPb2. Even tablebases include these kinds of positions because it’s more trouble to exclude them than include them, and losing them throws away interesting new information.

Or if I’m in the middle of constructing a problem, I might have e.g. 19 black pieces. That’s fine - I can try to reduce them later. Some published compositions have illegal diagrams. The idea may simply not be achievable with a sound diagram. According to the chess problem conventions (the Codex) legality is not required for soundness.

Finally - I’ve corrected hundreds of diagram errors in working with a database over the years, but only a tiny fraction resulted in illegality. Typically, it’s a piece on an adjacent square: still completely legal. If programmer effort is spent to help avoid transcription errors, e.g. by enabling easy import/export of different formats, including images, that would be more valuable.

The point I’m making is that rarely do I think “oh I’m glad the program is checking legality” but often I think “why did the programmer feel they need to check legality? It stops me from doing what I need to do here.”

I can’t imagine my perspective being popular in this thread but it’s a sincere answer.

So beyond checking for SQL injection etc, at most I would check just that forward moves can work in the engine which is going to be consulted, e.g.:

• Is there at most 1 king on each side?
• Are there no pawns on the first or eighth rank?
• Is the side to move not giving check already?

This is sensible defensive programming and there’s no reason to go further.

If that’s three YESes then we can play chess forwards from this diagram which is much more important than legality. And even this short list of conditions one might need to loosen sometimes (rex multiplex, dummy pawns, lese majeste).

Answer 6

Here is a simple backtracking algorithm, provided that you have a function that can check reverse legal moves at every board state (also known as position):

function is_legal_state(state,move)

   //Terminate if a starting state was found. This immediately implies there
   //was a legal game that generated this state, in fact the backtracking
   //can tell you precisely such a game       
   if (state in starting board state)
     return true

   //Apply some move to get to a new state, state is a persistent object
   apply_reverse_move(state,move)

   //Generate all legal "reverse" moves, that is, moves that could have
   //been performed to get to the current state from another position,
   //provided the previous position was valid. You do not have to check the
   //validness of the previous state, you just have to make sure the
   //transitioning move was valid
   legalmoves = enumerate_all_reverse_moves( state )

   for local_move in legalmoves:
     return is_legal_state(state,local_move)

   //Reverse the move that was previously applied so backtracking can
   //work properly 
   reverse_reverse_move(state,move)

   return false

Answer 7

Also , if the K is checked twice , the position must have resulted from a discovered check - Q and R,B or N , N and R or B , or R & B. Pawns are never involved in a discovered check.