A sudoku problem: Efficiently find or approximate probability distribution over chosen numbers at each index of an array with no repeats

user_17940040 0
Viewed 127

I'm looking for an efficient algorithm to generate or iteratively approximate a solution to the problem described below.

You are given an array of length N and a finite set of numbers Si for each index i of the array. Now, if we are to place a number from Si at each index i to fill the entire array, while ensuring that the number is unique across the entire array; given all the possible arrays, what is the probability ditribution over each number at each index?

Here I give an example: Assuming we have the following array of length 3 with each column representing Si at the index of the column

4 4 4
   2  2
1  1  1

We will have the following possible arrays:

421
412
124
142

And the following probability distribution: (over 1 2 4 at each index respectively)

0.5 0.25 0.25
      0.5   0.5
0.5 0.25 0.25

Brute forcing this problem is obviously doable but I have a gut feeling that there must be some more efficient algorithms for this.

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.

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.s. The reason why I am interested in this problem is because I wanted to generate probability distribution over candidate numbers for the empty cells in a sudoku and other sudoku-like games without a unique answers by only applying all the standard rules)

probability linear-algebra combinatorics optimization algorithm
1 Answers

Sudoku is a combinatorial problem. It is easy to show that the probability of any independent cell is uniform (because you can relabel a configuration to put any number at a given position). The joint probabilities are more complicated.

If the game is partially filled you have constraints that will affect this distribution.

You must devise an algorithm to calculate the number of solutions from a given initial configuration. Then you compute the fraction of the total solutions are will have a specific value at the position of interest.

counts = {}
for i in range(1, 10):
  board[cell] = i;
  counts[i] = countSolutions(board);
prob = {i: counts[i] / sum(counts[i] for i in range(1, 10))}

The same approach works for joint probabilities but in some cases the number of possibilities may be too high.

user_127503530
Related