i need help with my sudoko solve function void Sudoku::solve() //backtrack.h #if

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

* C++ Program to Solve Sudoku Problem using BackTracking

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

using namespace std;

#define UNASSIGNED 0

#define N 9

bool FindUnassignedLocation(int grid[N][N], int &row, int &col);

bool isSafe(int grid[N][N], int row, int col, int num);

/* assign values to all unassigned locations for Sudoku solution  

*/

bool SolveSudoku(int grid[N][N])

{

int row, col;

if (!FindUnassignedLocation(grid, row, col))

return true;

for (int num = 1; num <= 9; num++)

{

if (isSafe(grid, row, col, num))

{

grid[row][col] = num;

if (SolveSudoku(grid))

return true;

grid[row][col] = UNASSIGNED;

}

}

return false;

}

/* Searches the grid to find an entry that is still unassigned. */

bool FindUnassignedLocation(int grid[N][N], int &row, int &col)

{

for (row = 0; row < N; row++)

for (col = 0; col < N; col++)

if (grid[row][col] == UNASSIGNED)

return true;

return false;

}

/* Returns whether any assigned entry n the specified row matches

the given number. */

bool UsedInRow(int grid[N][N], int row, int num)

{

for (int col = 0; col < N; col++)

if (grid[row][col] == num)

return true;

return false;

}

/* Returns whether any assigned entry in the specified column matches

the given number. */

bool UsedInCol(int grid[N][N], int col, int num)

{

for (int row = 0; row < N; row++)

if (grid[row][col] == num)

return true;

return false;

}

/* Returns whether any assigned entry within the specified 3x3 box matches

the given number. */

bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num)

{

for (int row = 0; row < 3; row++)

for (int col = 0; col < 3; col++)

if (grid[row+boxStartRow][col+boxStartCol] == num)

return true;

return false;

}

/* Returns whether it will be legal to assign num to the given row,col location.

*/

bool isSafe(int grid[N][N], int row, int col, int num)

{

return !UsedInRow(grid, row, num) && !UsedInCol(grid, col, num) &&

!UsedInBox(grid, row - row % 3 , col - col % 3, num);

}

/* print grid */

void printGrid(int grid[N][N])

{

for (int row = 0; row < N; row++)

{

for (int col = 0; col < N; col++)

cout<<grid[row][col]<<" ";

cout<<endl;

}

}

/* Main */

int main()

{

int grid[N][N] = {{3, 0, 6, 5, 0, 8, 4, 0, 0},

{5, 2, 0, 0, 0, 0, 0, 0, 0},

{0, 8, 7, 0, 0, 0, 0, 3, 1},

{0, 0, 3, 0, 1, 0, 0, 8, 0},

{9, 0, 0, 8, 6, 3, 0, 0, 5},

{0, 5, 0, 0, 9, 0, 6, 0, 0},

{1, 3, 0, 0, 0, 0, 2, 5, 0},

{0, 0, 0, 0, 0, 0, 0, 7, 4},

{0, 0, 5, 2, 0, 6, 3, 0, 0}};

if (SolveSudoku(grid) == true)

printGrid(grid);

else

cout<<"No solution exists"<<endl;

return 0;

}

$ g++ sudoku.cpp

$ a.out

3 1 6 5 7 8 4 9 2

5 2 9 1 3 4 7 6 8

4 8 7 6 2 9 5 3 1

2 6 3 4 1 5 9 8 7

9 7 4 8 6 3 1 2 5

8 5 1 7 9 2 6 4 3

1 3 8 9 4 7 2 5 6

6 9 2 3 5 1 8 7 4

7 4 5 2 8 6 3 1 9

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.