Sudoku program troubles

Hey guys. I need help with a Sudoku homework problem.
The problem is... Create a Sudoku program in which the user enters a sudoku puzzle. The program will then solve the puzzle and display the result. If the puzzle has multiple solutions display the total number. If muliple solutions exist, display three of them.

My code is as follows...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>
using namespace std;

void readAPuzzle (int grid[][9]);
bool search(int grid [][9]);
int getFreeCellList (const int grid [][9], int freeCellList[][2]);
void printGrid(const int grid[][9]);
bool isValid(int i, int j, const int grid [][9]);
bool isValid (const int grid[][9]);

int main()
{
	//Read a Sodoku puzzle

	int grid[9][9];
	readAPuzzle(grid);

	if  (!isValid(grid))
		cout << "Invalid input" << endl;

	else if (search(grid))
	{
		cout << "The solution is found:" << endl;
		printGrid(grid);
	}
	else
		cout << "No solution" << endl;
	system ("pause");
	return 0;
	
}



/** Read a Sodoku puzzle from the keyboard */
void readAPuzzle (int grid[][9])
{
	// Creat a Scanner
	cout << "Enter a Sudoku puzzle: \n(Remember to put a space inbetween each of the numbers of your sudoku puzzle.)" << endl;
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++)
			cin >> grid[i][j];
}

	/** Obtain a list of free cells from the puzzle */
	int getFreeCellList(const int grid[][9], int freeCellList[][2])
	{
		//81 is the maximum number of free cells
		int numberOfFreeCells = 0;

		for (int i = 0; i < 9; i++)
			for (int j = 0; j < 9; j++)
				if (grid[i][j] == 0)
				{
					freeCellList[numberOfFreeCells][0] = i;
					freeCellList[numberOfFreeCells][1] = j;
					numberOfFreeCells++;
				}
				
				return numberOfFreeCells;
		

	}

	/** Display the values in the grid */
	void printGrid(const int grid[][9])
	{
		for (int i = 0; i < 9; i ++)
		{
			for (int j = 0; j < 9; j++)
				cout << grid[i][j] << " ";
			cout << endl;
		}
	}

	/** Search for a solution */
	bool search (int grid[][9])
	{
		int freeCellList[81][2]; // Declare freeCellList
		int numberOfFreeCells = getFreeCellList(grid, freeCellList);

		if (numberOfFreeCells == 0)
			return true; // No free cells

		int k = 0; // Start from the first free cell
		while (true)
		{
			int i = freeCellList[k][0];
			int j = freeCellList[k][1];
			if (grid[i][j] == 0)
				grid[i][j] = 1; // Fill the free cell with number 1
			
			if (isValid(i, j, grid))
			{
				if (k+1 == numberOfFreeCells)
				{ // No more free cells
					return true; // a solution is found
				}
				else
				{ // Move to the next free cell
					k++;
				}
			}
			else if (grid[i][j] < 9)
			{
				//Fill the free cell with the next possible value
				grid[i][j] = grid[i][j] + 1;
			}
			else
			{ // grid[i][j] is 9, backtrack
				while (grid[i][j] == 0)
				{
					return false; //No possble value
				}
				grid[i][j] = grid[i][j] + 1;
			}
		}
		return true; // A solution is found
	}

	/** Check whether grid[i][j] is valid in the grid */
	bool isValid(int i, int j, const int grid[][9])
	{
		// Check whether grid[i][j] is valid at the i's row
		for (int column = 0; column < 9; column++)
			if (column != j && grid [i][column] == grid [i][j])
				return false;

		// Check whether grid[i][j] is valid at the j's column
		for (int row = 0; row < 9; row++)
			if (row != i && grid[row][j] == grid[i][j])
				return false;

		//check whether grid[i][j] is valid in the 3-by-3 box
		for (int row = (i / 3) * 3; row < (i /3) * 3 + 3; row++)
			for (int col = (j / 3) * 3; col <(j / 3) * 3 + 3; col++)
				if (row != i && col != j && grid[row][col] == grid[i][j])
					

		return true; // the current value at grid[i][j] is valid
	}
	/** Check whether the vided cells are valid in the grid */
	bool isValid(const int grid[][9])
	{
		for (int i = 0; i < 9; i++)
			for (int j=0; j < 9; j++)
				if (grid[i][j] < 0 || grid [i][j] > 9 || (grid[i][j] != 0 && !isValid(i, j, grid)))
					return false;
		return true; // The fixed cells are valid
		}


I just don't know what to do in order for the program to display the multiple solutions.
Thanks again
Last edited on
Topic archived. No new replies allowed.