I need finishing a sudoku c++ programming assignment. I need to finish utlizing the BackTracking class to implement the Sudoku::solve() function. A sudoku puzzle is a 9 by 9 grid o numbers, sub-divided into 9x3 block. The game requires each row, column, and block, to have the numbers 1-9 only once. The program will read the sudoku puzzle from the standard input. Zeros are usedto denote blank spaces in the initial problem. If the problem is solvable, the program will print the solution. If not, it prints a message indicating the problem has no solution.

sudoku.cpp:

#include "sudoku.h" using namespace std;

void Sudoku::solve() { // NOTE: Backtrack is 0-based, so you need to add 1 for the puzzle

m_IsSolved = false; int count = 0; while ((!m_IsSolved) && m_Problem.more()) {

//THIS is the only thing to finish. Insert the code using Backtracking

}

}

sudoku.h:

#pragma once #ifndef __SUDOKU_H__ #define __SUDOKU_H__

#include #include

#include "backtrack.h"

class Sudoku { public: const static unsigned int GRID_SIZE = 81; const static unsigned int ROW_SIZE = 9; const static unsigned int COL_SIZE = 9; const static unsigned int MAX_VALUE = 9; const static unsigned int BOX_SIZE = 3;

private: std::vector m_Initial; bool m_IsSolved; BackTrack m_Problem;

public: Sudoku(std::vector initial) : m_Initial(initial), m_IsSolved(false), m_Problem(GRID_SIZE, MAX_VALUE) { }

void solve();

bool isSolved() const { return m_IsSolved; }

void print(std::ostream& os) const { int k = 0; for (int i = 0; i < ROW_SIZE; ++i) { for (int j = 0; j < COL_SIZE; ++j) { os << m_Problem[k] + 1 << ' '; if (j % BOX_SIZE == BOX_SIZE - 1) os << ' '; ++k; } os << std::endl; if (i % BOX_SIZE == BOX_SIZE - 1) os << std::endl; } } private: int square(int k) const { int r = row(k) / BOX_SIZE; int c = column(k) / BOX_SIZE; return c + BOX_SIZE * r; }

int innerSquare(int k) const { int r = row(k) % BOX_SIZE; int c = column(k) % BOX_SIZE; return c + BOX_SIZE * r; }

int row(int k) const { return k / ROW_SIZE; }

int column(int k) const { return k % ROW_SIZE; }

int posBySquare(int ou, int in) const { int r = (ou / BOX_SIZE) * BOX_SIZE; int c = (ou % BOX_SIZE) * BOX_SIZE; r += in / BOX_SIZE; c += in % BOX_SIZE; return posByColRow(c, r); }

int posByColRow(int col, int row) const { return ROW_SIZE * row + col; }

};

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

#endif // __SUDOKU_H__

backtrack.h:

#pragma once #ifndef __BACKTRACK_H__ #define __BACKTRACK_H__

#include #include

class BackTrack { public: typedef std::vector::const_iterator const_iterator; typedef std::vector::const_iterator iterator;

private: bool m_Done; std::vector m_Arities; std::vector m_Values; public: BackTrack(unsigned int nVariables, unsigned int arity = 9) : m_Done(false), m_Arities(nVariables, arity), m_Values(nVariables, 0) {}

template BackTrack(Iterator start, Iterator end) : m_Done(false), m_Arities(start, end) { std::fill_n(std::back_inserter(m_Values), m_Arities.size(), 0); }

unsigned int operator[](unsigned int i) const { return m_Values[i]; }

unsigned int size() const { return m_Values.size(); }

unsigned int arity(unsigned int i) const { return m_Arities[i]; }

bool more() const { return !m_Done; }

void prune(unsigned int level) { level = (level > size()) ? size() : level; std::fill(m_Values.begin() + level, m_Values.end(), 0); int k = level - 1; bool carry = true; while (k >= 0 && carry) { m_Values[k] += 1; if (m_Values[k] >= m_Arities[k]) m_Values[k] = 0; else carry = false; --k; } m_Done = carry; }

BackTrack& operator++() { prune(size()); return *this; }

BackTrack operator++(int) { BackTrack oldValue = *this; prune(size()); return oldValue; }

const_iterator begin() const { return m_Values.begin(); }

iterator begin() { return m_Values.begin(); }

const_iterator end() const { return m_Values.end(); }

iterator end() { return m_Values.end(); } };

#endif // __BACKTRACK_H__

main.cpp:

#include #include #include

#include "sudoku.h"

int main(int argc, char** argv) { std::vector squares; for (unsigned int i = 0; i < Sudoku::GRID_SIZE; ++i) { int k; std::cin >> k; squares.push_back(k); }

Sudoku puzzle(squares); puzzle.solve();

if (puzzle.isSolved()) { std::cout << puzzle << std::endl; } else { std::cout << "Unable to solve this puzzle" << std::endl; } return 0; }

test input:

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