Recursively Solving A Sudoku Puzzle Using Backtracking Theoretically

Question

Answer: My pseudo is fuzzy in the recursive aspect but this video is helpful along with the resources below

http://www.youtube.com/watch?v=p-gpaIGRCQI

http://norvig.com/sudoku.html

Can't grasp the implementation of this backtrack recursive algorithm in respect to a sudoku puzzle.

I'm trying to solve a sudoku puzzle using recursive backtracking. I've been still unable to wrap the general algorithm around in my head given the problem domain I'm working in.

The backtracking algorithm I'm trying to use seems standard but I can't follow the logic and know whats happening underneath.

Included is the backtracking algorithm and its definition.

Edit: "Again, took out the class definition, left the declaration and put up the pseudo code"

Here's my pseudocode utilizing this.

Pseudo Code (C++ implement) backtrack game (81,9) // represents all possible combinations of input and values for game

    //All info is loading into a vector of size 81 with the initial state 
    //puzzle = the initial state 9x9 grid from left to right of integers  
        vector <int> puzzle
while(!not solved && not the end of the vector){
     for(int i =puzzle.begin::iterator i , puzzle.end()) //from 0-80 of the vector until end
        if puzzle[i] != 0
             //leave alone, original state of board
        else
              if (valid move) //a guess is allowed in this column/row/square of the board  
                   solution[i] = puzzle_guess[i]  //guess a move and insert 
              else  // one of previous guesses were wrong
                   game.prune(i); //backtracks, or reverses guesses until valid move
}

//initial state of the game

    4 0 0  6 0 5  2 0 3
    0 0 0  0 4 9  0 7 5
    0 0 0  1 0 7  6 0 0

    6 0 1  0 0 0  4 8 7
    0 8 0  0 0 0  0 3 0
    2 7 4  0 0 0  5 0 6

    0 0 8  7 0 3  0 0 0
    3 1 0  9 6 0  0 0 0
    7 0 9  2 0 8  0 0 1

Thank you

The only clue to know is the declaration using backtrack game (81,9) // signifying the 81 possibly numbers and 9 for the 9 different options.

#ifndef BACKTRACK_H
#define BACKTRACK_H

#include <vector>
#include <algorithm>

class BackTrack {
public:
  typedef std::vector<unsigned>::const_iterator const_iterator;
  typedef std::vector<unsigned>::const_iterator iterator;

  BackTrack (unsigned nVariables, unsigned arity=2);
  // Create a backtracking state for a problem with
  // nVariables variables, each of which has the same
  // number of possible values (arity).

  template <class Iterator>
  BackTrack (Iterator arityBegin,
         Iterator arityEnd);
  // Create a backtracking state in which each variable may have
  // a different number of possible values. The values are obtained
  // as integers stored in positions arityBegin .. arityEnd as per
  // the usual conventions for C++ iterators. The number of
  // variables in the system are inferred from the number of
  // positions in the given range.

  unsigned operator[] (unsigned variableNumber) const;
  // Returns the current value associated with the indicated
  // variable.

  unsigned numberOfVariables() const;
  // Returns the number of variables in the backtracking system.

  unsigned arity (unsigned variableNumber) const;
  // Returns the number of potential values that can be assigned
  // to the indicated variable.

  bool more() const;
  // Indicates whether additional candidate solutions exist that
  // can be reached by subsequent ++ or prune operaations.

  void prune (unsigned level);
  // Indicates that the combination of values associated with
  // variables 0 .. level-1 (inclusive) has been judged unacceptable
  // (regardless of the values that could be given to variables
  // level..numberOfVariables()-1.  The backtracking state will advance
  // to the next solution in which at least one of the values in the
  // variables 0..level-1 will have changed.

  BackTrack& operator++();
  // Indicates that the combination of values associated with
  // variables 0 .. nVariables-1 (inclusive) has been judged unacceptable.
  // The backtracking state will advance
  // to the next solution in which at least one of the values in the
  // variables 0..level-1 will have changed.

  BackTrack operator++(int);
  // Same as other operator++, but returns a copy of the old backtrack state


  // Iterator operations for easy access to the currently assigned values
  const_iterator begin() const {return values.begin();}
  iterator begin()             {return values.begin();}

  const_iterator end() const {return values.end();}
  iterator       end()       {return values.end();}

private:
  bool done;
  std::vector<unsigned> arities;
  std::vector<unsigned> values;

};
inline
unsigned BackTrack::operator[] (unsigned variableNumber) const
  // Returns the current value associated with the indicated
  // variable.
{
  return values[variableNumber];
}

inline
unsigned BackTrack::numberOfVariables() const
  // Returns the number of variables in the backtracking system.
{
  return values.size();
}

inline
unsigned BackTrack::arity (unsigned variableNumber) const
  // Returns the number of potential values that can be assigned
  // to the indicated variable.
{
  return arities[variableNumber];
}


inline
bool BackTrack::more() const
  // Indicates whether additional candidate solutions exist that
  // can be reached by subsequent ++ or prune operaations.
{
  return !done;
}

template <class Iterator>
BackTrack::BackTrack (Iterator arityBegin,
              Iterator arityEnd):
  // Create a backtracking state in which each variable may have
  // a different number of possible values. The values are obtained
  // as integers stored in positions arityBegin .. arityEnd as per
  // the usual conventions for C++ iterators. The number of
  // variables in the system are inferred from the number of
  // positions in the given range.
  arities(arityBegin, arityEnd), done(false) 
{
  fill_n (back_inserter(values), arities.size(), 0);
}


#endif

Answer 1

Here is a simple pseudocode which may help you understand the recursion and backtracking:

solve(game):
    if (game board is full)
        return SUCCESS
    else
        next_square = getNextEmptySquare()
        for each value that can legally be put in next_square
            put value in next_square (i.e. modify game state)
            if (solve(game)) return SUCCESS
            remove value from next_square (i.e. backtrack to a previous state)
    return FAILURE

Once you can understand that, the next thing is to understand how various implementations of getNextEmptySquare() will affect performance by pruning the state space graph in different ways.

I don't see any recursion or methodical searching in your original pseudocode, although it is not entirely clear, it appears to just try random permutations over and over?