i need help with my sudoko solve function void Sudoku::solve() //backtrack.h #if
ID: 3739316 • Letter: I
Question
i need help with my sudoko solve function
void Sudoku::solve() //backtrack.h #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); template <class Iterator> BackTrack (Iterator arityBegin, Iterator arityEnd); unsigned operator[] (unsigned variableNumber) const; unsigned numberOfVariables() const; unsigned arity (unsigned variableNumber) const; bool more() const; void prune (unsigned level); BackTrack& operator++(); BackTrack operator++(int); // 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 { return values[variableNumber]; } inline unsigned BackTrack::numberOfVariables() const { return values.size(); } inline unsigned BackTrack::arity (unsigned variableNumber) const { return arities[variableNumber]; } inline bool BackTrack::more() const { return !done; } template <class Iterator> BackTrack::BackTrack (Iterator arityBegin, Iterator arityEnd): arities(arityBegin, arityEnd), done(false) { fill_n (back_inserter(values), arities.size(), 0); } //backtrack.cpp #endif #include "backtrack.h" #include <vector> #include <algorithm> BackTrack::BackTrack (unsigned nVariables, unsigned arity) { } void BackTrack::prune (unsigned level) { level = (level > numberOfVariables()) ? numberOfVariables() : level; fill (values.begin()+level, values.end(), 0); 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++() { prune(numberOfVariables()); return *this; } BackTrack BackTrack::operator++(int) { BackTrack oldValue = *this; prune(numberOfVariables()); return oldValue; } //sudoku.h
#ifndef SUDOKU_H #define SUDOKU_H #include "backtrack.h" #include <iostream> #include <vector> class Sudoku { public: Sudoku (std::vector<int> initialProblem); // Attempt to solve the puzzle. void solve(); bool hasBeenSolved() const {return solved;} const std::vector<int>& getSolution() const; void print (std::ostream&) const; private: std::vector<int> initial; bool solved; BackTrack problem; int square(int k) const; int innerSquare(int k) const; int row(int k) const; int column(int k) const; int posBySquare(int ou, int in) const; 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 //sudoku.cpp include "sudoku.h" #include "backtrack.h" using namespace std; Sudoku::Sudoku (std::vector<int> initialProblem) : initial(initialProblem), problem(81, 9), solved(false) {} const std::vector<int>& Sudoku::getSolution() const { if (solved) { vector<int> solution (problem.begin(), problem.end()); for (int i = 0; i < 81; ++i) ++solution[i]; } else return initial; } void Sudoku::solve() { solved = false; while ((!solved) && problem.more()) { } } 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; } } int Sudoku::square(int k) const { int r = row(k) / 3; int c = column(k) / 3; return c + 3 * r; } int Sudoku::innerSquare(int k) const { int r = row(k) % 3; int c = column(k) % 3; return c + 3 * r; } int Sudoku::row(int k) const { return k / 9; } int Sudoku::column(int k) const { 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; }
Explanation / Answer
In the Below code I have includes the sudoku solve method and added required libraries. Please through go this,
//backtrack.h
#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
template <class Iterator>
BackTrack (Iterator arityBegin,
Iterator arityEnd);
// Create a backtracking state in which each variable may have
unsigned operator[] (unsigned variableNumber) const;
unsigned numberOfVariables() const;
unsigned arity (unsigned variableNumber) const;
bool more() const;
void prune (unsigned level);
BackTrack& operator++();
BackTrack operator++(int);
// 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
{
return values[variableNumber];
}
inline
unsigned BackTrack::numberOfVariables() const
{
return values.size();
}
inline
unsigned BackTrack::arity (unsigned variableNumber) const
{
return arities[variableNumber];
}
inline
bool BackTrack::more() const
{
return !done;
}
template <class Iterator>
BackTrack::BackTrack (Iterator arityBegin,
Iterator arityEnd):
arities(arityBegin, arityEnd), done(false)
{
fill_n (back_inserter(values), arities.size(), 0);
}
//backtrack.cpp
#endif
#include "backtrack.h"
#include <vector>
#include <algorithm>
BackTrack::BackTrack (unsigned nVariables, unsigned arity)
{
}
void BackTrack::prune (unsigned level)
{
level = (level > numberOfVariables()) ? numberOfVariables() : level;
fill (values.begin()+level, values.end(), 0);
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++()
{
prune(numberOfVariables());
return *this;
}
BackTrack BackTrack::operator++(int)
{
BackTrack oldValue = *this;
prune(numberOfVariables());
return oldValue;
}
//sudoku.h
#endif
#include "sudoku.h"
#include "backtrack.h"
#include "utility"
using namespace std;
Sudoku::Sudoku (std::vector<int> initialProblem)
: initial(initialProblem), problem(81, 9), solved(false)
{}
const std::vector<int>& Sudoku::getSolution() const
{
if (solved)
{
vector<int> solution (problem.begin(), problem.end());
for (int i = 0; i < 81; ++i)
++solution[i];
}
else
return initial;
}
// Attempt to solve the puzzle.
void Sudoku::solve()
{
solved = false;
while ((!solved) && problem.more())
{
vector<int> solution (problem.begin(), problem.end());
for (int i = 0; i < 81; ++i)
++solution[i];
if(!solved)
++problem;
}
}
// 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;
}
}
int Sudoku::square(int k) const
{
int r = row(k) / 3;
int c = column(k) / 3;
return c + 3 * r;
}
int Sudoku::innerSquare(int k) const
{
int r = row(k) % 3;
int c = column(k) % 3;
return c + 3 * r;
}
int Sudoku::row(int k) const
{
return k / 9;
}
int Sudoku::column(int k) const
{
return k % 9;
}
int Sudoku::posBySquare(int ou, int in) const
{
int r = (ou / 3) * 3;
int c = (ou % 3) * 3;
r += in / 3;
c += in % 3;
return posByColRow(c, r);
}
int Sudoku::posByColRow(int col, int row) const
{
return 9 * row + col;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.