title: Optimizing the backtracking algorithm solving Sudoku
body: <p>I'm hoping to optimize my backtracking algorithm for my Sudoku Solver.</p>
  
  <hr>
  
  <p>What it does now:</p>
  
  <p>The recursive solver function takes a sudoku puzzle with various given values.</p>
  
  <p>I will scour through all the empty slots in the puzzle, looking for the slot that has the least possibilities, and get the list of values.</p>
  
  <p>From the list of values, I will loop through it by placing one of the values from the list in the slot, and recursively solve it, until the entire grid is filled.</p>
  
  <hr>
  
  <p>This implementation still takes incredibly long for some puzzles and I hope to further optimize this. Does anyone have any ideas how I might be able to further optimize this?</p>
  
  <hr>
  
  <p>Here's my code in Java if you're interested.</p>
  
  <pre class="lang-java prettyprint-override"><code>public int[][] Solve(int[][] slots) {
      // recursive solve v2 : optimization revision
  
      int[] least = new int[3];
      least[2] = Integer.MAX_VALUE;
      PuzzleGenerator value_generator = new PuzzleGenerator();
      LinkedList&lt;Integer&gt; least_values = null;
  
      // 1: find a slot with the least possible solutions
      // 2: recursively solve.
  
      // 1 - scour through all slots.
      int i = 0;
      int j = 0;
      while (i &lt; 9) {
          j = 0;
          while (j &lt; 9) {
              if (slots[i][j] == 0) {
                  int[] grid_posi = { i, j };
                  LinkedList&lt;Integer&gt; possible_values = value_generator
                          .possibleValuesInGrid(grid_posi, slots);
                  if ((possible_values.size() &lt; least[2])
                          &amp;&amp; (possible_values.size() != 0)) {
                      least[0] = i;
                      least[1] = j;
                      least[2] = possible_values.size();
                      least_values = possible_values;
                  }
              }
              j++;
          }
          i++;
      }
  
      // 2 - work on the slot
      if (least_values != null) {
          for (int x : least_values) {
              int[][] tempslot = new int[9][9];
              ArrayDeepCopy(slots, tempslot);
              tempslot[least[0]][least[1]] = x;
  
              /*ConsoleInterface printer = new gameplay.ConsoleInterface();
              printer.printGrid(tempslot);*/
  
              int[][] possible_sltn = Solve(tempslot);
              if (noEmptySlots(possible_sltn)) {
                  System.out.println("Solved");
                  return possible_sltn;
              }
          }
      }
      if (this.noEmptySlots(slots)) {
          System.out.println("Solved");
          return slots;
      }
      slots[0][0] = 0;
      return slots;
  }
  </code></pre>