# Piece rank probability in this Stratego-like game

There's this game in a 9x8 board where 2 players take turns moving pieces. The players have pieces ranked 1-21. Players can't see the opponent's pieces' ranks, just positions. Pieces landing on the same block is a challenge, which is resolved by removing the lower value piece (or both if same value). Challenges are decided by a third party arbiter.

I need a way to calculate the probability of opponent's pieces being a certain rank. Information about the player's pieces are revealed through challenges. Say, my rank 2 piece challenges an opponent's piece and loses. Now I know the opponent's piece has $0\%$ probability of being a 2 or 1 and higher probability for being a 3, 4, 5 etc. I also need to adjust other piece's probabilities to account for this.

I've reduced the problem to a constraints problem. Let's limit the problem to a 4 piece set. I represent the possible values of piece $x_i$ like this:

$x_1 = \{1,2,3\}$

$x_2 = \{2,3\}$

$x_3 = \{1,2\}$

$x_4 = \{2,3,4\}$

(In this example, piece $x_1$ was challenged by my rank 4 piece, etc.)

The solutions are $\{1,3,2,4\}$, $\{3,2,1,4\}$ and $\{2,3,1,4\}$.

So, empirically, the probabilities are:

$P(x_1 = 1) = 33\%, P(x_1 = 2) = 33\%, P(x_1 = 3) = 33\%, P(x_1 = 4) = 0\%$

$P(x_2 = 1) = 0\%, P(x_2 = 2) = 33\%, P(x_2 = 3) = 66\%, P(x_2 = 4) = 0\%$

$P(x_3 = 1) = 66\%, P(x_3 = 2) = 33\%, P(x_3 = 0) = 0\%, P(x_3 = 4) = 0\%$

$P(x_4 = 4) = 100\%$

For the full set, calculating all of the solutions empirically is not feasible. Is there a way to do this not empirically?