How to make Sudoku solver with backtracking algorithm go back?

Question

This weekend I worked on a Sudoku Solver (Ruby quiz) based on a backtracking algorithm. The sudoku is loaded in an array sudoku_arr of 81 integers (9x9 grid) where 0's are empty spots. There is a valid? method which checks if the sudoku_arr can be a valid sudoku.

The official backtracking algorithm 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.

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 solve_by_increasing_value_previous_index in the SudokuSolver class. Here's the 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 < 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] << tmp_a[3]  << tmp_a[6]  << tmp_a[1]  << tmp_a[4]  << tmp_a[7]  <<
    tmp_a[2]  << tmp_a[5]  << tmp_a[8]  << tmp_a[9]  << tmp_a[12] << tmp_a[15] <<
    tmp_a[10] << tmp_a[13] << tmp_a[16] << tmp_a[11] << tmp_a[14] << tmp_a[17] <<
    tmp_a[18] << tmp_a[21] << tmp_a[24] << tmp_a[19] << tmp_a[22] << tmp_a[25] <<
    tmp_a[20] << tmp_a[23] << tmp_a[26]).flatten!)
  end

  def valid?
    rows_valid? && columns_valid? && squares_valid?
  end

  def rows_have_unique_values?(arr)
    (arr[0,9]- [0]).uniq.size == (arr[0,9]- [0]).size &&
    (arr[9,9]- [0]).uniq.size == (arr[9,9]- [0]).size && 
    (arr[18,9]-[0]).uniq.size == (arr[18,9]-[0]).size && 
    (arr[27,9]-[0]).uniq.size == (arr[27,9]-[0]).size && 
    (arr[36,9]-[0]).uniq.size == (arr[36,9]-[0]).size && 
    (arr[45,9]-[0]).uniq.size == (arr[45,9]-[0]).size && 
    (arr[54,9]-[0]).uniq.size == (arr[54,9]-[0]).size && 
    (arr[63,9]-[0]).uniq.size == (arr[63,9]-[0]).size && 
    (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(&:to_i)
    @indeces_of_zeroes = []
    @sudoku_arr.each_with_index { |e,index| @indeces_of_zeroes << 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 < 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

Unfortunately the code does not backtrack to the beginning. The code prints:

"increasing_index..." "increasing_value..." "increasing_value..." "increasing_value..." "increasing_value..." "increasing_value..." "increasing_value..." "increasing_value..." "increasing_value..." "Increasing previous index..." 16 2

in a loop till it throws a SystemStackError because the stack level is too deep.

What happens is that the "backtracking" does not go further back than one index. When the solve_by_increasing_value_previous_index 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.

Unfortunately I do not see an easy way to implement this algorithm. _{(What I thought of was a @too_much_looping variable that gets incremented when the solve_by_increasing_value_previous_index 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.} \

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.

Answer 1

I haven't yet waded through your code, but the backtracking algorithm boils down to the following:

int solve(char board[81]) {
    int i, c;
    if (!is_valid(board)) return 0;
    c = first_empty_cell(board);
    if (c<0) return 1; /* board is full */
    for (i=1; i<=9; i++) {
        board[c] = i;
        if (solve(board)) return 1;
    }
    board[c] = 0;
    return 0;
}

This is a recursive function that tries each value from 1 to 9 in the first empty cell it finds (returned by first_empty_cell()). If none of these values leads to a solution, then you must be on a dead branch of the search tree, so the cell in question can be reset to zero (or whatever value you use to indicate an unfilled cell).

Of course, there are a lot of other things you could do to make your software arrive at a solution faster, but as far as backtracking goes, that's all there is to it.

---

Addendum:

OK, I'm wading through your code now. It looks like you're storing index_of_tried_value as an attribute of the sudoku grid. That won't work. You need to store this value in a local variable of the solver routine so it can be pushed onto the stack and recovered when you backtrack down the search tree.

Answer 2

There is an algo called "Dancing links" invented by knuth, which can be applied in Sudoku. http://en.wikipedia.org/wiki/Dancing_Links

Soduko problem can be solved by exact cover problem. Here is the article http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz

here is my code to solve exact cover problem, it can also solve sudoku and the backtracing part is in dlx()

const int INF = 0x3f3f3f3f;
const int T = 9;
const int N = T*T*T+10;
const int M = T*T*T*4+T*T*4+10;
int id;
int L[M],R[M],U[M],D[M];
int ANS[N],SUM[N],COL[M],ROW[M],H[N];


struct Dancing_links
{
    Dancing_links() {}
    Dancing_links(int n,int m)
    {
        for(int i=0; i<=m; i++)
        {
            SUM[i] = 0;
            L[i+1] = D[i] = U[i] = i;
            R[i]=i+1;
        }
        L[m+1]=R[m]=0,L[0]=m,id=m+1;
        clr(H,-1);
    }

    void remove(int c)
    {
        L[R[c]] = L[c];
        R[L[c]] = R[c];
        for(int i=D[c]; i!=c; i=D[i])
            for(int j=R[i]; j!=i; j=R[j])
            {
                U[D[j]] = U[j];
                D[U[j]] = D[j];
                SUM[COL[j]]--;
            }
    }

    void resume(int c)
    {
        for(int i=U[c]; i!=c; i=U[i])
            for(int j=L[i]; j!=i; j=L[j])
            {
                U[D[j]] = D[U[j]] = j;
                SUM[COL[j]]++;
            }
        L[R[c]] = R[L[c]] = c;
    }

    void add(int r,int c)
    {
        ROW[id] = r,COL[id] = c;
        SUM[c]++;
        D[id] = D[c],U[D[c]] = id,U[id] = c,D[c] = id;

        if(H[r] < 0)
            H[r] = L[id] = R[id] = id;
        else
            R[id] = R[H[r]],L[R[H[r]]] = id,L[id] = H[r],R[H[r]] = id;
        id++;
    }

    int dlx(int k)
    {
        if(R[0] == 0)
        {
            /*output the answer*/return k;
        }

        int s=INF,c;
        for(int i=R[0]; i; i=R[i])
            if(SUM[i] < s)
                s=SUM[c=i];

        remove(c);
        for(int r=D[c]; r!=c; r=D[r])
        {
            ANS[k] = ROW[r];
            for(int j=R[r]; j!=r; j=R[j])   remove(COL[j]);

            int tmp = dlx(k+1);
            if(tmp != -1) return tmp; //delete if multipal answer is needed

            for(int j=L[r]; j!=r; j=L[j])   resume(COL[j]);
        }
        resume(c);
        return -1;
    }
};