Question
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
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 "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
public: Sudoku(std::vector
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
class BackTrack { public: typedef std::vector
private: bool m_Done; std::vector
template
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 "sudoku.h"
int main(int argc, char** argv) { std::vector
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
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started