title: Implementing a backtrack search with heuristic?
body: <p>I'm getting quite interested in search algorithms and backtrack programming. For now, I have implemented Algorithm X (see my other post here: <a href="https://stackoverflow.com/questions/16048609/determine-conflict-free-sets">Determine conflict-free sets?</a> ) to solve an exact cover problem. This works very well but I'm now interested in solving this with a more basic variant of backtracking. I just can't figure out how this can be done. The problem description is the same as before:</p>
  
  <p>Suppose you have a bunch of sets, whereas each set has a couple of subsets.</p>
  
  <p>Set1 = { (banana, pineapple, orange), (apple, kale, cucumber), (onion, garlic) }</p>
  
  <p>Set2 = { (banana, cucumber, garlic), (avocado, tomato) }</p>
  
  <p>...</p>
  
  <p>SetN = { ... }</p>
  
  <p>The goal now is to select one subset from each set, whereas each subset must be conflict free with any other selected subset (one element is not contained in any of the other chosen subsets).</p>
  
  <p>As an example, I wrote two Java classes that. The sets are identified by a single character and the elements are plain numbers.</p>
  
  <p>I specifically have two problems:</p>
  
  <ul>
  <li>How to iterate over all sets/subsets in such a way that the use of a heuristic is possible (choose subset with minimum elements, minimum cost, ...)</li>
  <li>How to maintain the selected sets+subsets and their contained elements.</li>
  </ul>
  
  <p>All other examples I can find are either Sudoku or n-Queens and are all using fixed for-loops. In addition to that, I was thinking about a rather general approach where a function "isPossiblePartialSolution" may be used to check, if a chosen path/set may be in conflict with a previously chosen subset/element.</p>
  
  <p>Here are the two Java classes:</p>
  
  <pre><code>import java.util.ArrayList;
  
  public class Main {
  
  public static void main(String[] args) {
  
      ArrayList&lt;Set&gt; allSets = buildRandomTest();
  
      for(Set r : allSets) {
          System.out.print("Set with id: " + r.id + " is subset in collection: " + r.name + " and contains: ");
          for(Integer n : r.listOfElements) {
              System.out.print(" " + n + " ");
          }
          System.out.println();
      }
  
  }
  
  public static int myRandomRange(int low, int high) {
      return (int) (Math.random() * (++high - low) + low);
  }
  
  public static ArrayList&lt;Set&gt; buildRandomTest() {
  
      ArrayList&lt;Set&gt; mySet = new ArrayList&lt;Set&gt;();
  
      int numberOfSets = myRandomRange(10, 12);
  
      for(int i=0; i&lt;numberOfSets; i++) {
          String nameOfSet = Character.toString((char) myRandomRange(65, 67));
          Set tmp = new Set(nameOfSet, i);
  
          ArrayList&lt;Integer&gt; listOfElements = new ArrayList&lt;Integer&gt;();
          int elementsInList = myRandomRange(2, 4);
  
          for(int j=0; j&lt;elementsInList; j++) {
              listOfElements.add(myRandomRange(1,30));
          }
  
          tmp.listOfElements = listOfElements;
          mySet.add(tmp);
      }
  
      return mySet;
  }
  
  }
  </code></pre>
  
  <p>and</p>
  
  <pre><code>import java.util.ArrayList;
  
  public class Set {
  
  public String name;
  public int id;
  public ArrayList&lt;Integer&gt; listOfElements;
  
  public Set(String name, int id) {
      this.name = name;
      this.id = id;
      listOfElements = new ArrayList&lt;Integer&gt;();
  }
  
  }
  </code></pre>