title: Recursively Solving A Sudoku Puzzle Using Backtracking Theoretically
body: <p>Answer: My pseudo is fuzzy in the recursive aspect but this video is helpful along with the resources below </p>
  
  <p><a href="http://www.youtube.com/watch?v=p-gpaIGRCQI" rel="noreferrer">http://www.youtube.com/watch?v=p-gpaIGRCQI</a></p>
  
  <p><a href="http://norvig.com/sudoku.html" rel="noreferrer">http://norvig.com/sudoku.html</a></p>
  
  <p><strong>Can't grasp the implementation of this backtrack recursive algorithm in respect to a sudoku puzzle.</strong> </p>
  
  <p>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.</p>
  
  <p>The backtracking algorithm I'm trying to use seems standard but I can't follow the logic and know whats happening underneath.</p>
  
  <p>Included is the backtracking algorithm and its definition. </p>
  
  <p>Edit: "Again, took out the class definition, left the declaration and put up the pseudo code"</p>
  
  <p>Here's my pseudocode utilizing this.</p>
  
  <p>Pseudo Code (C++ implement) 
  backtrack game (81,9) // represents all possible combinations of input and values for game</p>
  
  <pre><code>    //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 &lt;int&gt; puzzle
  while(!not solved &amp;&amp; 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
  }
  </code></pre>
  
  <p>//initial state of the game </p>
  
  <pre><code>    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
  </code></pre>
  
  <p>Thank you</p>
  
  <p>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.</p>
  
  <pre><code>#ifndef BACKTRACK_H
  #define BACKTRACK_H
  
  #include &lt;vector&gt;
  #include &lt;algorithm&gt;
  
  class BackTrack {
  public:
    typedef std::vector&lt;unsigned&gt;::const_iterator const_iterator;
    typedef std::vector&lt;unsigned&gt;::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 &lt;class Iterator&gt;
    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&amp; 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&lt;unsigned&gt; arities;
    std::vector&lt;unsigned&gt; 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 &lt;class Iterator&gt;
  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
  </code></pre>