title: Fast calculation of probability distribution in board game Da Vinci Code
body: <p>I'm interested in efficiently calculating the probability distribution over possible secret numbers given what one can observe of the opponents' hand (and your own hand) in the board game Da Vinci Code. A link to the game here: <a href="https://boardgamegeek.com/boardgame/8946/da-vinci-code" rel="nofollow noreferrer">https://boardgamegeek.com/boardgame/8946/da-vinci-code</a></p>
  <p>I have abstracted the problem into the following:
  You are given an array A of length N and a finite set of numbers Si for each index i of the array. Now,</p>
  <ol>
  <li>we are to place a number from Si at each index i to fill the entire array A;</li>
  <li>while ensuring that the number is unique across the entire array A;</li>
  <li>and for 3 disjoint subarrays A1, A2, A3 of A such that concat(A1, A2, A3) = A, the numbers in each subarray must follow a strictly increasing order;
  given all the possible numbers to form A that satisfy the above constraints, what is the probability ditribution over each number at each index?</li>
  </ol>
  <p>Here I provide an example below:
  Assuming we have the following array of length 5 with each column representing Si at the index of the column</p>
  <pre><code>| 6 6 | 6 6 | 6 |
  |   5 |   5 |   |
  | 4 4 |     | 4 |
  |     | 3 3 |   |
  | 2   | 2 2 |   |
  | 1 1 |     |   | 
  | ___ | __  | _ |
  | A1  | A2  | A3| 
  </code></pre>
  <p>The set of all possible arrays are:
  14236
  14256
  14356
  15234
  15236
  15264
  15364
  16234
  16254
  16354
  24356
  25364
  26354
  45236</p>
  <p>Therefore the probability distribution over each number [1-6] at each index is:</p>
  <pre> 
  6  0      4/14  0     3/14  6/14 <br/>
  5  0      6/14  0     6/14  0    <br/>
  4  1/14   4/14  0     0     8/14 <br/>
  3  0      0     6/14  5/14  0    <br/>
  2  3/14   0     8/14  0     0    <br/>
  1  10/14  0     0     0     0    <br/>
  ___________   __________   ______<br/>
      A1          A2          A3    <br/> </pre>
  <p>Brute forcing this problem is obviously doable but I have a gut feeling that there must be some more efficient algorithms for this.</p>
  <p>The reason why I think so is due to the fact that one can derive the probability distribution from the set of all possibilities but not the other way around, so the distribution itself must contain less information then the set of all possibilities have. Therefore, I believe that we do not need to generate all possibilites just to obtain the probability distribution.</p>
  <p>Hence, I am wondering if there is any smart matrix operation we could use for this problem or even fixed-point iteration/density evolution to approximate the end probability distribution? Some other potentially more efficient approaches to this problem are also appreciated.</p>