Search code examples
algorithmmathsolverminesweeper

Algorithm that can compute values of variables based on the result of specific sums of those

This might be a duplicate question, but I wasn't able to find this on stack overflow.

Take some variables, which all represent a chance of something. That means that all variables have a value between zero and one (both inclusive). The values of these are unknown. However, I have some equations with some or all of these variables of which the result is known.

For example, take the variables a, b, c, x and y. Their values are all an unknown number between 0 and 1 (both inclusive). I have the following equations:

1: a + b + c = 1
2: a + b + x = 2
3: b + c + y = 2
4: a + x <= 1    ->    0 <= a + x <= 1
5: c + y <= 1    ->    0 <= c + y <= 1

Solving this gives the following result:

2: a + x + b = 2
   (something between 0 and 1) + b = 2
   b = 2 - (something between 0 and 1)
   1 <= b <= 2
   b = 1 (since 0 <= b <= 1 applies too)

1: a + b + c = 1
   a + 1 + c = 1
   a + c = 0
   a = -c
   a = 0  (since 0 <= a <= 1 and 0 <= c <= 1 apply)
   c = 0

2: a + b + x = 2   |   3: b + c + y = 2
   0 + 1 + x = 2   |      1 + 0 + y = 2
   x = 1           |      y = 1

-> a = 0, b = 1, c = 0, x = 1 and y = 1

I solved this on paper, my actual purpose was to prove the following minesweeper situation by assigning each unrevealed cell a variable, respectively x a b c y. Since x, y and b turn out to be one, they could be flagged:

Minesweeper 2

My general purpose is to solve minesweeper boards using this technique, but it could be used in other software. However, if I want a computer to solve a minesweeper board using this technique, a comupter has to use an algorithm for solving such situations with any amount of variables and any amount of equations. Is there a general algorithm that does this? And if there is, how should I implement that algorithm?

To make things obvious

  • An equation is one variable or a sum of some variables, having a limited or constant result, which is always positive.
  • A variable is an unknown value between zero and one (both inclusive).
  • The algorithm takes in the amount of variables with the respective variable names, and the equations that define some variables.
  • The algorithm tries to compute as many values as possible. Values that could not be determined remain undetermined.
Solution

  • In general, you have an N-dimensional vector space over which the N independent variables can vary. Each of your constraints defines a region of the vector space and the intersection of all such regions is the region you wish to determine. Really, you are looking for the simplest (least complex) description of that region, since the region is already described by the collection of constraints. There are three possibilities: first, that there are no solutions in the region; second, that there are a finite number of solutions in the region; third, that there are infinitely many solutions in the region.

    Your first step could be to treat the equations, if any, as a system of equations and use an algorithm for solving systems of equations to solve as much as possible from the equations alone. If nothing else, having some variables eliminated will help in the next step. 

    1: a + b + c = 1
2: a + b + x = 2
3: b + c + y = 2

1: a = 1 - b - c
2: 1 - b - c + b + x = 2
3: b + c + y = 2

1: a = 1 - b - c
2: c = x - 1
3: b + x - 1 + y = 2

1: a = 1 - b - c
2: c = x - 1
3: b = 3 - x - y

1: a = y - 1
2: c = x - 1
3: b = 3 - x - y

    This is as far as we can go. Next, we substitute into our full system of inequalities:

    A: 0 <= a <= 1
B: 0 <= b <= 1
C: 0 <= c <= 1
D: 0 <= x <= 1
E: 0 <= y <= 1
F: 0 <= a + x <= 1
G: 0 <= c + y <= 1

A: 0 <= y - 1 <= 1
B: 0 <= 3 - x - y <= 1
C: 0 <= x - 1 <= 1
D: 0 <= x <= 1
E: 0 <= y <= 1
F: 0 <= y - 1 + x <= 1
G: 0 <= x - 1 + y <= 1

A: 1 <= y <= 2
B: 3 >= x + y >= 2
C: 1 <= x <= 2
D: 0 <= x <= 1
E: 0 <= y <= 1
F: 1 <= y + x <= 2
G: 1 <= x + y <= 2

    At this point, you need to look for constraints on each variable in isolation (if any) and find the intersection of those constraints.

    A: 1 <= y <= 2 \
                > taken together, the only solution is y = 1
E: 0 <= y <= 1 /  this is the intersection of intervals [0,1] and [1,2]

C: 1 <= x <= 2 \
                > taken together, the only solution is x = 1
D: 0 <= x <= 1 /  this is the intersection of intervals [0,1] and [1,2]

B: 3 >= x + y >= 2 \  taken together, this means x + y = 2
F: 1 <= y + x <= 2  > this is the intersection of [1,2] and [2,3]
G: 1 <= x + y <= 2 /  note that G turns out to be redundant after subbing

    The solution x = 1, y = 1 is consistent with our system of inequalities. It is the only such solution. We can back-substitute in our system of equations to get the values of the other variables:

    1: a = y - 1
     = 1 - 1
     = 0
2: c = x - 1
     = 1 - 1
     = 0
3: b = 3 - x - y
     = 3 - 1 - 1
     = 1

    So the solution a = 0, b = 1, c = 0, x = 1, y = 1 works and is the only solution. Pretty much all of these steps should be things that you can automate.