Solve Sudoku Puzzle Using Backtracking

[KB93]

Hello everyone, like the title says I'm trying to finish implementing a solve function to solve a Sudoku Puzzle. So far I think I've figured out how to check the board to check for empty cells. What I can't figure out is how to test a value 1-9 against the column and row to make sure it is an acceptable value, and if not, backtrack to test another value. This problem would be a lot easier using a 2d array but of course the specifications require me to implement this using code that is already given. Below is the files used, along with the sudoku.cpp file which contains the code I have implemented so far, and pseudocode for what I am trying to accomplish. Any help pointing me in the right direction will be much appreciated. Thank you in advance.

MAIN.cpp
#include <fstream>
#include <iostream>
#include <vector>

#include "sudoku.h"

int main(int argc, char** argv)
{
std::vector<int> 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;
}

BACKTRACK.h
#pragma once
#ifndef __BACKTRACK_H__
#define __BACKTRACK_H__

#include <vector>
#include <algorithm>

class BackTrack
{
public:
typedef std::vector<unsigned int>::const_iterator const_iterator;
typedef std::vector<unsigned int>::const_iterator iterator;

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


template<class Iterator>
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__

SUDOKU.h
#pragma once
#ifndef __SUDOKU_H__
#define __SUDOKU_H__

#include <iostream>
#include <vector>

#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<int> m_Initial;
bool m_IsSolved;
BackTrack m_Problem;

public:
Sudoku(std::vector<int> 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__

SUDOKU.cpp (MY CODE)
#include "sudoku.h"

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())
{
for (int i = 0; i <81; i++)
{
for(int j=m_Initial[i]; j > 0 ;j--)
{
if(m_Initial[i] != 0)
{
m_Problem.prune(i+1);
}

else
{ // try a number
//check rows/columns to see if valid move
//if valid move m_Problem++
//if move not valid
//m_Problem.prune(i);
}
}
}
}
}

One final note is that I am only allowed edit the code in the SUDOKU.cpp file under the while loop.

[dhayden]

Use bits in an integer to gather the values currently in the row or column, something like:

int values {0};
for (int i=0; i<0; ++i) {
    values |= (1 << row[i]);
}

Now to see if a number n can go in that row:

if (values & (1<<n)) {
    // n is already in the row
}

You could also use an array or vector of ints, which might be faster but would use more space.