Sudoku solver iterating too much

Question

I need help reducing the number of iterations my current implementation takes to solve the puzzle. I've got a pre-built class I am attempting to implement, albeit I think my backtracking needs improvement.

If supplied a grid like so:

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

A time check takes: 7m39.038s; need to reduce that significantly (ideally to <= 60s).

My current algorithm:

void Sudoku::solve()
{
  solved = false;
  while ((!solved) && problem.more())
  {
      int known = problem.numberOfVariables();
      for (int i = 0; i < 81; i++) {
          int rw = row(i);
          int col = column(i);
          int sqr = square(i);
          for (int d = 0; d < 81; d++) {
              int w = row(d);
              int f = column(d);
              int e = square(d);
              if ((initial[i] > 0 && initial[i] != problem[i] + 1) ||
                  (d != i 
                      && problem[i] == problem[d] 
                      && (w == rw || col == f || sqr == e))) {
                  solved = false;
                  known = min(known, max(d, i));
              }
          }
      }
      if (known >= problem.numberOfVariables()) {
          solved = true;
      }
      else {
          problem.prune(known + 1);
      }
  }
}

The nested for goes through far too many iterations and I'm not sure of the best way to reduce them. Here are the supporting .h/.cpp files for the implementation.

While I understand pseudo-code is a typical response, something a bit more detailed goes a long way with me. Often I understand the problem, but cannot foresee the implementation with the given constraints (i.e. I know the nail needs to go into the wall, but do I use a hammer or a nail gun?).

I would appreciate any direction to improve the pruning/backtracking.

sudo.h

#ifndef SUDOKU_H
#define SUDOKU_H

#include "backtrack.h"

#include <iostream>
#include <vector>

class Sudoku {
public:
  // Create a new puzzle, given a vector of 81 ints
  // in the range 0-9 (0 denotes an initially empty square)
  Sudoku (std::vector<int> initialProblem);

  // Attempt to solve the puzzle.
  void solve();

  bool hasBeenSolved() const {return solved;}


  // Print the puzzle state
  void print (std::ostream&) const;

private:
  std::vector<int> initial;
  bool solved;
  BackTrack problem;

  /* ********************************************** */
  // Utility functions to interpret positions in the 
  // vectors in terms of the squares, rows, and columns
  // of a sudoku puzzle

  // Given a vector position k in the range 0..80

  int square(int k) const;
  // Which of the 9 large squares:
  //    0 1 2
  //    3 4 5
  //    6 7 8

  int innerSquare(int k) const;
  // Which of the 9 small squares with a large square:
  //    0 1 2
  //    3 4 5
  //    6 7 8

  int row(int k) const;
  // Which row (0..8) in the entire puzzle

  int column(int k) const;
  // Which column (0..8) in the entire puzzle


  // Given a outer square # ou and an inner square # in:
  int posBySquare(int ou, int in) const; 
  // returns the equivalent vector position in the range 0..80

  // Given a column and row
  int posByColRow(int col, int row) const;
  // returns the equivalent vector position in the range 0..80
};

inline
std::ostream& operator<< (std::ostream& out, const Sudoku& puzzle)
{
  puzzle.print(out);
  return out;
}

#endif

sudo.cpp

#include "sudoku.h"
#include "backtrack.h"

using namespace std;

// Create a new puzzle, given a vector of 81 ints
// in the range 0-9 (0 denotes an initially empty square)
Sudoku::Sudoku (std::vector<int> initialProblem)
  : initial(initialProblem), solved(false), problem(81, 9)
{}

// Attempt to solve the puzzle.
void Sudoku::solve()
{
  // Note - values 0..8 in Backtrack correspond to values 1..9 in the 
  // usual puzzle.
  solved = false;
  while ((!solved) && problem.more())
  {
      int known = problem.numberOfVariables();
      for (int i = 0; i < 81; i++) {
          int rw = row(i);
          int col = column(i);
          int sqr = square(i);
          for (int d = 0; d < 81; d++) {
              int w = row(d);
              int f = column(d);
              int e = square(d);
              if ((initial[i] > 0 && initial[i] != problem[i] + 1) ||
                  (d != i 
                      && problem[i] == problem[d] 
                      && (w == rw || col == f || sqr == e))) {
                  solved = false;
                  known = min(known, max(d, i));
              }
          }
      }
      if (known >= problem.numberOfVariables()) {
          solved = true;
      }
      else {
          problem.prune(known + 1);
      }
  }
}


// Print the puzzle state
void Sudoku::print (std::ostream& out) const
{
  int k = 0;
  for (int line = 0; line < 9; ++line)
    {
      for (int col = 0; col < 9; ++col)
    {
      out << problem[k]+1 << ' ';
      if (col % 3 == 2)
        cout << ' ';
      k++;
    }
      cout << endl;
      if (line % 3 == 2)
    cout << endl;
    }
}



// Utility functions to interpret positions in the 
// vectors in terms of the squares, rows, and columns
// of a sudoku puzzle

// Given a vector position k in the range 0..80

int Sudoku::square(int k) const
// Which of the 9 large squares:
//    0 1 2
//    3 4 5
//    6 7 8
{
  int r = row(k) / 3;
  int c = column(k) / 3;
  return c + 3 * r;
}

int Sudoku::innerSquare(int k) const
// Which of the 9 small squares with a large square:
//    0 1 2
//    3 4 5
//    6 7 8
{
  int r = row(k) % 3;
  int c = column(k) % 3;
  return c + 3 * r;
}


int Sudoku::row(int k) const
  // Which row (0..8) in the entire puzzle
{
  return k / 9;
}

int Sudoku::column(int k) const
  // Which column (0..8) in the entire puzzle
{
  return k % 9;
}

// Given a outer square # ou and an inner square # in:
int Sudoku::posBySquare(int ou, int in) const
  // returns the equivalent vector position in the range 0..80
{
  int r = (ou / 3) * 3;
  int c = (ou % 3) * 3;
  r += in / 3;
  c += in % 3;
  return posByColRow(c, r);
}

// Given a column and row
int Sudoku::posByColRow(int col, int row) const
  // returns the equivalent vector position in the range 0..80
{
  return 9 * row + col;
}

back.h

#ifndef BACKTRACK_H
#define BACKTRACK_H

#include <vector>
#include <iterator>
#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.
  done(false), arities(arityBegin, arityEnd)
{
  fill_n (back_inserter(values), arities.size(), 0);
}


#endif

back.cpp

#include "backtrack.h"

#include <vector>
#include <algorithm>

BackTrack::BackTrack (unsigned nVariables, unsigned arity)
  // Create a backtracking state for a problem with
  // nVariables variables, each of which has the same
  // number of possible values (arity).
  : done(false), arities(nVariables, arity), values(nVariables, 0)
{
}


void BackTrack::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.
{
  level = (level > numberOfVariables()) ? numberOfVariables() : level;
  fill (values.begin()+level, values.end(), 0);


  // Treat the top level-1 values as a level-1 digit number. Add one
  // to the rightmost "digit". If this digit goes too high, reset it to
  // zero and "carry one to the left".
  int k = level-1;
  bool carry = true;
  while (k >= 0 && carry)
    {
      values[k] += 1;
      if (values[k] >= arities[k])
    values[k] = 0;
      else
    carry = false;
      --k;
    }
  done = carry;
}


BackTrack& 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.
{
  prune(numberOfVariables());
  return *this;
}

BackTrack BackTrack::operator++(int)
  // Same as other operator++, but returns a copy of the old backtrack state
{
  BackTrack oldValue = *this;
  prune(numberOfVariables());
  return oldValue;
}

Answer 1

You are not handling all the constraints, and that is the main problem leading to long runtime. So the only change needed is in the solve member function:

  // Attempt to solve the puzzle.
  void Sudoku::solve()
  {
      // Note - values 0..8 in Backtrack correspond to values 1..9 in the 
      // usual puzzle.
      solved = false;
      while ((!solved) && problem.more())
      {
          int known = problem.numberOfVariables();
          for (int i = 0; i < 81; i++) {
              int rw = row(i);
              int col = column(i);
              int sqr = square(i);
              for (int d = 0; d < 81; d++) {
                  int w = row(d);
                  int f = column(d);
                  int e = square(d);
                  if ((initial[i] > 0 && initial[i] != problem[i] + 1) ||
                      (d != i 
                          && problem[i] == problem[d] 
                          && (w == rw || col == f || sqr == e))) {
                      solved = false;
                      known = min(known, max(d, i));
                  }
              }
          }
          if (known >= problem.numberOfVariables()) {
              solved = true;
          }
          else {
              problem.prune(known + 1);
          }
      }
   }

The problem is that you are not taking into account the already filled values in the same col, row or box. This leads to a huge amount of unnecessary backtracking iterations.

So the correct code would be (with some minor changes such as moving out the 1st condition, since when that is true then the 2nd was never getting executed anyway):

// Attempt to solve the puzzle.
void Sudoku::solve()
{
    // Note - values 0..8 in Backtrack correspond to values 1..9 in the 
    // usual puzzle.
    solved = false;
    while ((!solved) && problem.more())
    {
        int known = problem.numberOfVariables();
        for (int i = 0; i < 81; i++) {

            //existing value should be fixed first
            if (initial[i] > 0 && initial[i] != problem[i] + 1)
            {
                known = std::min(known,i);
                break;
            }

            int rw = row(i);
            int col = column(i);
            int sqr = square(i);

            for (int d = 0; d < 81; d++) {
                int w = row(d);
                int f = column(d);
                int e = square(d);
                if(w == rw || col == f || sqr == e)
                {
                    if(d != i && problem[i] == problem[d]) 
                    {  
                        known = min(known, max(d, i));
                    }
                    // you need to check if the same value exists in 
                    // the same row, col, or square 
                    // And if it does exist then fix i'th location first
                    if(d != i && initial[d]>0 && initial[d] == problem[i]+1)
                    {
                        known = std::min(known,i);
                    }
                }
            }
        }

        if (known >= problem.numberOfVariables()) {
            solved = true;
        }
        else {
          problem.prune(known + 1);
        }
    }
 }

Answer 2

In order to make your algorithm efficient, basically what you need is this: you march through the non-occupied cells in some particular order (does not matter which, but you could march one row at a time from top to bottom, each row one column position from left to right). When you encounter an empty cell (call it c), put the least non-conflicting digit into it (say, 4). Next move to the next empty cell in the march order and set it to the smallest possible value. If you find that the an empty cell cannot contain any digit, you need to backtrack (your algorithm should be recursive). Now, suppose you get back to c. Its current value is still 4, but you know that it does not lead to solution. Because of this, you increase it to the next feasible value (say 7). Continue in the same manner until your recursive algorithm sets the very last cell; halt then.

Answer 3

A few of thoughts:

First, use a cell class, this can have properties not only for the value of the cell, but also for a collection of possible values, the row, column, square and square position. This allows you to maintain by reference the cells in different collections(rows, columns, squares), without repeating all the data and having all cell changes reflected in all collections.

Second, build these collections as you build the puzzle.

Third, instead of starting randomly, start at a cell that has the lowest number of possibilities. For instance if the cell has 2 possibilities, you only have to follow 2 paths to either complete some cells, or fail. If both fail you have your answer. By constantly taking only the smallest number of possibilities, this will greatly reduce the number of nested iterations.