Assignment 5: Minesweeper

This assignment is worth 30 points and has two parts.

1. CSP Solver (20 pts)

Write a class that can solve constraint satisfaction problems of the following nature:

For example, here is one such problem:

It's not difficult to see that this problem has a unique solution:

Your solver should live in a class Solver with the following API:

public class Constraint {
    int count;
    List<Integer> vars;

    public Constraint(int count, List<Integer> vars) {
        this.count = count;  this.vars = vars;
    }
}

public class Assignment {
        public int var;
        public boolean val;
        
        public Assignment(int var, boolean val) {
                this.var = var;  this.val = val;
        }
}

public class Solver {
  // Create a Solver for a problem with _n_ variables.
  public Solver(int n) { ... }
  
  // Add a constraint to the problem.
  public void add(Constraint c) { ... }
  
  // Assign a fixed value to a variable.  Return true if the assignment was made,
  // or false if it would violate an existing constraint.
  public boolean setVar(int i, boolean v) { ... }
  
  // Deduce that some variable must have a certain value, and assign that value
  // to the variable.  Return the assignment that was made, or null if
  // no deduction was possible.
  public Assignment solve() { ... }
}

For example, we could use your Solver to solve the constraint satisfaction problem defined above:

        Solver s = new Solver(4);
        s.add(new Constraint(1, List.of(0, 1)));
        s.add(new Constraint(1, List.of(1, 2)));
        s.add(new Constraint(1, List.of(2, 3)));
        s.add(new Constraint(2, List.of(0, 2, 3)));
                
        while (true) {
                Assignment a = s.solve();
                if (a == null)
                        break;
                System.out.format("%d = %b\n", a.var, a.val);
        }

The output might be

2 = true
0 = true
1 = false
3 = false

Suppose that we omit the last constraint from this problem:

        Solver s = new Solver(4);
        s.add(new Constraint(1, List.of(0, 1)));
        s.add(new Constraint(1, List.of(1, 2)));
        s.add(new Constraint(1, List.of(2, 3)));

Now it is not possible to deduce the value of any variable, and s.solve() will return null.

Let us fix the value of one variable:

s.setVar(0, false);

Now the values of the other variables can be deduced. The while loop above will print output such as

1 = true
2 = false
3 = true

Here is a test program SolverTest.java that checks all of the cases described above, plus one several test cases corresponding to various situations on small Minesweeper boards. It would be wise to ensure that your solver passes all these tests before you apply it to Minesweeper in general.

hints

Use a backtracking search as described in section 6.3 of the Russell & Norvig text (Artificial Intelligence: A Modern Approach).

The backtracking algorithm described there can determine whether a constrant satisfaction problem has any solution. Our problem here is a bit different: we want to determine whether some variable has the same value in every solution. In theory, we could use backtracking to find all solutions, and record which variables have the same value in all of them. But that would be impractically slow, because there could be exponentially many solutions.

So you will need to use a different approach. To try to determine the value of some variable, first choose a variable V using the degree heuristic, described in section 6.3.1. Assume that V is true. Now use a backtracking search to see if you can find any solution for all the other variables. If not, V must be false - and so you have solved one variable. Otherwise, now assume that V is false, and see if you can find any solution for all the other variables. If not, V must be true.

If you can find possible solutions both when V is true and when it is false, then you cannot determine the value of V. In this case you must move to another variable W (again, chosen using the degree heuristic). Assume that W is true or false, and see if you can determine its value by looking for a solution for the other variables. And so on.

If you go through all variables in this manner and cannot prove that any are true or false, you'll need to return null.

As you execute the algorithm above, you'll want to perform forward checking at every step, i.e. infer as many variable values as you can from individual constraints. This is called "maintaining arc consistency" in section 6.3.2 of the text, and will make your solver far more efficient than if you use backtracking alone.

The arcs in this solver are actually hyperarcs since constraints can be non-binary, i.e. on more than two variables. The text describes an arc consistency algorithm AC-3 for binary constraints; you will need to use a similar algorithm that works with the kind of constraints that this solver supports. Keep a queue of constraints that still need to be checked. In a loop, pull a constraint from the queue and check whether it determines the values of one of more variables. If so, set those values, and add all constraints involving those variables to the queue, since you now need to check those constraints as well.

2. Minesweeper (10 pts)

Write an agent that plays Minesweeper using your CSP solver.

Download the Minesweeper code from the Minesweeper4J repository. Use the Minesweeper API. You may modify MyAgent or write your own subclass of ArtificialAgent.

Your agent should be able to solve randomly generated Minesweeper boards of size 50 x 50 with a mine density of 20% in under 500 ms on average on a typical desktop or laptop computer, asking for an average of fewer than 8 hints while still solving the board safely. For boards of this size and mine density, typically 1-10 hints will be necessary, but occasionally as many as 20.

hints