c++ Sudoku puzzle solver

[Lord Method Man]

void Solve(int **puzzle, int row, int col)
{
	if(row == 9 && col == 9)
	{
		DisplaySolution(puzzle);

		return;
	}

	for(i = 0; i < 10; i++)
	{
		if(CanInsert(i, puzzle, row, col))
		{
			puzzle[row][col] = i;

			if(col < 9)
				Solve(puzzle, row, col + 1);
			else
				Solve(puzzle, row + 1, 0);

			puzzle[row][col] = -1;
		}
	}
}

I put this together quick as I was trying to recall a project I did years ago in college to solve Sudoku puzzles. Thought I would share it and see if problems jump out at anyone.

 

The puzzle is a 10x10 grid. CanInsert() doesn't exist but pretend it does and indicates if the value can be placed in the current cell. DisplaySolution() outputs the completed puzzle. A cell value of -1 indicates a 'blank' cell.

 

This isn't an assignment or anything, just a bit bored here.

[Hardcore Til I Die]

Just to say that you're only iterating through each row and column once. You might not have enough information for CanInsert() to know if it can insert something on the first pass, so it seems like you should do something like this:

if(row == 9 && col == 9)
{
       if (PuzzleIsCompleted(puzzle))
       {

            DisplaySolution(puzzle);
       }
       else
       {
           Solve(puzzle, 1, 1);
       }

}

Also, it doesn't look like your code will ever reach "puzzle[row][col] = -1;"

 

I think it should be after the bracket like this:

        if(CanInsert(i, puzzle, row, col))
        {

            puzzle[row][col] = i;



            if(col < 9)

                Solve(puzzle, row, col + 1);

            else

                Solve(puzzle, row + 1, 0);



           
        }
        puzzle[row][col] = -1;

[Lord Method Man]

 

Also, it doesn't look like your code will ever reach "puzzle[row][col] = -1;"

 

I think it should be after the bracket like this:

        if(CanInsert(i, puzzle, row, col))
        {

            puzzle[row][col] = i;



            if(col < 9)

                Solve(puzzle, row, col + 1);

            else

                Solve(puzzle, row + 1, 0);



           
        }
        puzzle[row][col] = -1;

 

It should, once the recursive call finishes the cell is marked as blank again in case, even though it was a valid move at the time, it renders the puzzle not solvable in a later cell. I don't see why it should be outside the if(caninsert) block since at that point the cell should be empty anyway.

[Hardcore Til I Die]

It should, once the recursive call finishes the cell is marked as blank again in case, even though it was a valid move at the time, it renders the puzzle not solvable in a later cell. I don't see why it should be outside the if(caninsert) block since at that point the cell should be empty anyway.

 

Skills are rusty - I thought that it would never reach it because it recurses uses Solve() each time, and I forgot that it will still process what's after the Solve(). 

 

The first thing I said still seems valid though. 

[Andre S. Veteran]

Looks like it should solve the problem if CanInsert returns true if and only if the addition of the specified value at the specified position does not violate any of the constraints. CanInsert will also have to deal with existing values (returning true only if the square is unassigned).

 

EDIT: I originally wrote that this was brute force but it's not brute force at all. Must get some sleep. Btw, try solving Project Euler #96 with it.

[Lord Method Man]

Looks like it should solve the problem if CanInsert returns true if and only if the addition of the specified value at the specified position does not violate any of the constraints. CanInsert will also have to deal with existing values (returning true only if the square is unassigned).

 

EDIT: I originally wrote that this was brute force but it's not brute force at all. Must get some sleep. Btw, try solving Project Euler #96 with it.

 

Yeah, I was going to add a check to see if the cell was already filled in but I decided to just assume CanInsert would do that.

 

Also noticed a big error I made: This is for a 10x10 grid when it should be 9x9.

[Lord Method Man]

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;
}

?