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;
}