title: How to make Sudoku solver with backtracking algorithm go back?
body: <p>This weekend I worked on a Sudoku Solver (<a href="http://rubyquiz.com/quiz43.html" rel="nofollow">Ruby quiz</a>) based on a backtracking algorithm. The sudoku is loaded in an array <code>sudoku_arr</code> of 81 integers (9x9 grid) where 0's are empty spots. There is a <code>valid?</code> method which checks if the <code>sudoku_arr</code> can be a valid sudoku. </p>
  
  <p>The <a href="http://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Backtracking" rel="nofollow">official backtracking algorithm</a> goes like this: try value on next empty spot, check if it is valid sudoku, if not increase value by 1 (upto 9), if valid go on and try first value on next spot, if not increase value of previous 0. </p>
  
  <p>Hereby we have to keep track of the previous array, and that is where I am going wrong and I am not sure if it can be solved. The part of my code below that is not working is the <code>solve_by_increasing_value_previous_index</code> in the <code>SudokuSolver</code> class. Here's the code:</p>
  
  <pre><code>require 'pp'
  
  sudoku_str = "
  +-------+-------+-------+
  | _ 6 _ | 1 _ 4 | _ 5 _ |
  | _ _ 8 | 3 _ 5 | 6 _ _ |
  | 2 _ _ | _ _ _ | _ _ 1 |
  +-------+-------+-------+
  | 8 _ _ | 4 _ 7 | _ _ 6 |
  | _ _ 6 | _ _ _ | 3 _ _ |
  | 7 _ _ | 9 _ 1 | _ _ 4 |
  +-------+-------+-------+
  | 5 _ _ | _ _ _ | _ _ 2 |
  | _ _ 7 | 2 _ 6 | 9 _ _ |
  | _ 4 _ | 5 _ 8 | _ 7 _ |
  +-------+-------+-------+"
  
  class SudokuException &lt; StandardError
    attr_reader :sudoku_arr
    def initialize(message, sudoku_arr)
      super(message)
      @sudoku_arr = sudoku_arr
    end
  end
  
  class Sudoku
  
    attr_accessor :sudoku_arr, 
                  :index_of_tried_value,
                  :tried_value
  
    def initialize(sudoku_arr, index_of_tried_value, tried_value)
      @sudoku_arr = sudoku_arr
      @index_of_tried_value = index_of_tried_value
      @tried_value = tried_value
    end
  
    def rows_valid?
      rows_have_unique_values?(@sudoku_arr)
    end
  
    def columns_valid?
      rows_have_unique_values?(@sudoku_arr.each_slice(9).to_a.transpose.flatten!)
    end
  
    def squares_valid?
      tmp_a = @sudoku_arr.each_slice(3).to_a
  
      rows_have_unique_values?(
      (tmp_a[0] &lt;&lt; tmp_a[3]  &lt;&lt; tmp_a[6]  &lt;&lt; tmp_a[1]  &lt;&lt; tmp_a[4]  &lt;&lt; tmp_a[7]  &lt;&lt;
      tmp_a[2]  &lt;&lt; tmp_a[5]  &lt;&lt; tmp_a[8]  &lt;&lt; tmp_a[9]  &lt;&lt; tmp_a[12] &lt;&lt; tmp_a[15] &lt;&lt;
      tmp_a[10] &lt;&lt; tmp_a[13] &lt;&lt; tmp_a[16] &lt;&lt; tmp_a[11] &lt;&lt; tmp_a[14] &lt;&lt; tmp_a[17] &lt;&lt;
      tmp_a[18] &lt;&lt; tmp_a[21] &lt;&lt; tmp_a[24] &lt;&lt; tmp_a[19] &lt;&lt; tmp_a[22] &lt;&lt; tmp_a[25] &lt;&lt;
      tmp_a[20] &lt;&lt; tmp_a[23] &lt;&lt; tmp_a[26]).flatten!)
    end
  
    def valid?
      rows_valid? &amp;&amp; columns_valid? &amp;&amp; squares_valid?
    end
  
    def rows_have_unique_values?(arr)
      (arr[0,9]- [0]).uniq.size == (arr[0,9]- [0]).size &amp;&amp;
      (arr[9,9]- [0]).uniq.size == (arr[9,9]- [0]).size &amp;&amp; 
      (arr[18,9]-[0]).uniq.size == (arr[18,9]-[0]).size &amp;&amp; 
      (arr[27,9]-[0]).uniq.size == (arr[27,9]-[0]).size &amp;&amp; 
      (arr[36,9]-[0]).uniq.size == (arr[36,9]-[0]).size &amp;&amp; 
      (arr[45,9]-[0]).uniq.size == (arr[45,9]-[0]).size &amp;&amp; 
      (arr[54,9]-[0]).uniq.size == (arr[54,9]-[0]).size &amp;&amp; 
      (arr[63,9]-[0]).uniq.size == (arr[63,9]-[0]).size &amp;&amp; 
      (arr[72,9]-[0]).uniq.size == (arr[72,9]-[0]).size 
    end
  
  end
  
  
  class SudokuSolver
  
    attr_accessor :sudoku_arr, 
                  :indeces_of_zeroes
  
    def initialize(str)
      @sudoku_arr = str.gsub(/[|\+\-\s]/,"").gsub(/_/,'0').split(//).map(&amp;:to_i)
      @indeces_of_zeroes = []
      @sudoku_arr.each_with_index { |e,index| @indeces_of_zeroes &lt;&lt; index if e.zero? }
    end
  
    def solve
      sudoku_arr = @sudoku_arr
      try_index = @indeces_of_zeroes[0]
      try_value = 1
      sudoku = Sudoku.new(sudoku_arr, try_index, try_value)
      solve_by_increasing_value(sudoku)
    end
  
    def solve_by_increasing_value(sudoku)
  
      if sudoku.tried_value &lt; 10
        sudoku.sudoku_arr[sudoku.index_of_tried_value] = sudoku.tried_value
        if sudoku.valid?
          pp "increasing_index..."
          solve_by_increasing_index(sudoku)
        else
          pp "increasing_value..."
          sudoku.tried_value += 1
          solve_by_increasing_value(sudoku)
        end
      else
        pp "Increasing previous index..."
        solve_by_increasing_value_previous_index(sudoku)
      end
    end
  
    def solve_by_increasing_index(sudoku)
      if sudoku.sudoku_arr.index(0).nil? 
        raise SudokuException(sudoku.sudoku_arr.each_slice(9)), "Sudoku is solved."
      end
  
      sudoku.index_of_tried_value = sudoku.sudoku_arr.index(0)
      sudoku.tried_value = 1
  
      solve_by_increasing_value(sudoku)
    end
  
    def solve_by_increasing_value_previous_index(sudoku)
      # Find tried index and get the one before it
      tried_index = sudoku.index_of_tried_value
      previous_index = indeces_of_zeroes[indeces_of_zeroes.index(tried_index)-1]
  
      # Setup previous Sudoku so we can go back further if necessary:
  
      # Set tried index back to zero
      sudoku.sudoku_arr[tried_index] = 0
      # Set previous index
      sudoku.index_of_tried_value = previous_index
      # Set previous value at index
      sudoku.tried_value = sudoku.sudoku_arr[previous_index]
      pp previous_index
      pp sudoku.tried_value
      # TODO Throw exception if we go too far back (i.e., before first index) since Sudoku is unsolvable
  
      # Continue business as usual by increasing the value of the previous index
      solve_by_increasing_value(sudoku)
    end
  
  end
  
  sudoku_solver = SudokuSolver.new(sudoku_str)
  sudoku_solver.solve
  </code></pre>
  
  <p>Unfortunately the code does not backtrack to the beginning. The code prints:</p>
  
  <blockquote>
    <p>"increasing_index..." 
    "increasing_value..." 
    "increasing_value..."
    "increasing_value..." 
    "increasing_value..." 
    "increasing_value..."
    "increasing_value..." 
    "increasing_value..." 
    "increasing_value..." 
    "Increasing previous index..." 
    16 
    2</p>
  </blockquote>
  
  <p>in a loop till it throws a <code>SystemStackError</code> because the stack level is too deep.</p>
  
  <p>What happens is that the "backtracking" does not go further back than one index. When the <code>solve_by_increasing_value_previous_index</code> goes to the previous index it takes the previous value there. In this case it is a 2, but the 2 is not working and we should therefore decrease it to a 1 and continue, and if that does not work, discard the 2 and make it a 0 again and go back further. </p>
  
  <p>Unfortunately I do not see an easy way to implement this algorithm. <sub>(What I thought of was a <code>@too_much_looping</code> variable that gets incremented when the <code>solve_by_increasing_value_previous_index</code> gets called, and after 81 times gets a reset. But this only helps with going back one more time, we cannot loop back to the beginning.</sub> \</p>
  
  <p>I hope someone can provide me with some help! General code comments are very welcome too, I have a suspicion this is not 100% idiomatic Ruby.</p>