Update:

Having CanInsert() check if the value is a pre-filled value and then returning false doesn't work - the program will never get past that cell because it can't insert any value and falls back to the previous cell.

I changed it to include a second matrix, one that simply checks if the current cell has a pre-filled value or not. If it hits a pre-filled cell it continues on to the next one without changing it and doesn't reset it to zero once the recursive call finishes. At least that is the idea. So far I can't get past row 1, col 6 of the Euler 96 problem. Here is my complete program so far, its sloppy since Ive been trying a lot of stuff with it.

When I debug it, I can see that it is falling back to previous cells recursively, all the way back to row 0 at least, but I also let it run for quite a while (with cout commented out since output slows down programs considerably) and it never hit my conditional breakpoint indicating it finally got past row 1 col 6.

#include <iostream>
using namespace std;
void Solve(bool initialValues[][9], int puzzle[][9], int row, int col);
bool CanInsert(int val, int puzzle[][9], int row, int col);
void DisplaySolution(int puzzle[][9]);
int main()
{
int puzzle[9][9] = {{0, 0, 3, 0, 2, 0, 6, 0, 0,},
{9, 0, 0, 3, 0, 5, 0, 0, 1},
{0, 0, 1, 8, 0, 6, 4, 0, 0},
{0, 0, 8, 1, 0, 2, 9, 0, 0},
{7, 0, 0, 0, 0, 0, 0, 0, 8},
{0, 0, 6, 7, 0, 8, 2, 0, 0},
{0, 0, 2, 6, 0, 9, 5, 0, 0},
{8, 0, 0, 2, 0, 3, 0, 0, 9},
{0, 0, 5, 0, 1, 0, 3, 0, 0}};
bool initialValues[9][9];
for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9; j++)
{
if(puzzle[i][j] > 0)
initialValues[i][j] = true;
else
initialValues[i][j] = false;
}
}
Solve(initialValues, puzzle, 0, 0);
return 0;
}
void Solve(bool initialValues[][9], int puzzle[][9], int row, int col)
{
if(row == 8 && col == 8)
{
DisplaySolution(puzzle);
return;
}
for(int i = 1; i < 10; i++)
{
// If cell is pre-filled, continue on
if(initialValues[row][col] || CanInsert(i, puzzle, row, col))
{
// if its pre-filled, we can't change it. Continue recursion with original value
if(initialValues[row][col] == false)
puzzle[row][col] = i;
if(col < 8)
{
Solve(initialValues, puzzle, row, col + 1);
}
else
{
Solve(initialValues, puzzle, row + 1, 0);
}
// cell was pre-filled, we can't reset it
if(initialValues[row][col] == false)
puzzle[row][col] = 0;
}
}
}
bool CanInsert(int val, int puzzle[][9], int row, int col)
{
cout << "Checking if " << val << " can go in row " << row << ", column " << col << endl;
for(int i = 0; i < 9; i++)
{
// Check row for value
if(puzzle[row][i] == val)
return false;
// Check column for value
if(puzzle[i][col] == val)
return false;
}
// integer division will result in either 0, 3, or 6
int rowRoot = row / 3 * 3;
int colRoot = col / 3 * 3;
// Check grid square for value
for(int i = rowRoot; i <= (rowRoot + 2); i++)
{
for(int j = colRoot; j <= (colRoot + 2); j++)
{
if(puzzle[i][j] == val)
return false;
}
}
return true;
}
void DisplaySolution(int puzzle[][9])
{
for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9; j++)
{
cout << puzzle[i][j];
}
cout << endl;
}
cout << endl;
}