C++

Forum

 
sudoku solver

Apr 16, 2009 at 1:18am
fatllama (10)
Hi all
I'm making a sudoku solver, but there's one problem that is absolutely impossible to track down. I designed my program to run through all the cells, skipping the cells input by the user, and trying out all possible values. When it reached a cell where no values worked, it would go back and add one to a cell before it, then continue on.

However, somehow it is doing things such as recording that a 1 is in a row while it is not there, or saying that the one is not there while it clearly is. I have been unable to track down this bug, but maybe you guys can? :X
Here is the code for my calculate_solution function:
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
 
void calculate_solution( data &board_data ) {
	int positionInCells = 0;
	bool cellPassed;
	while ( positionInCells <= 80 )	{
				
		cout << "\n" << positionInCells;
		cellPassed = false;
		// Skip if user input cell
		// the value has been input by user and is fixed
		if ( board_data.board_input[positionInCells/9][positionInCells%9] )	{
			positionInCells++;
			continue;
		}
		int currentCellValue = board_data.singleDimensionBoard[positionInCells];
		resetCellValue( positionInCells, board_data );
			
		cout << " - ";
		// Cycle through the different cells until
		for ( int test_value = (currentCellValue + 1); test_value <= 9; test_value++ )	{
			cout << test_value;
			if ( cell_value_passes( positionInCells, test_value, board_data ) )	{
				saveCellValue( positionInCells, test_value, board_data );
				
				cellPassed = true;
				positionInCells++;
				break;
			}
		}
		if ( cellPassed )	
			continue;
		positionInCells--;
		
		while ( board_data.board_input[positionInCells/9][positionInCells%9] ) 
			positionInCells--;
							
		
	}
}


And here is the code for checking whether or not a value works:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
bool cell_value_passes ( int cellPosition, int value, data &board_data ) {
	int y, x;
	y = cellPosition/9;
	x = cellPosition%9;
	
	
	// fail if value is in this column
	if ( board_data.column[x][value-1] == true )
		return 0;
	
	// fail if value is in this row
	if ( board_data.row[y][value-1] == true )
		return 0;
		
	// fail if value in this square
	if ( board_data.square[y/3][x/3][value-1] == true )
		return 0;

	// passes all conditions; current value is good.
	return 1;

}





Last edited on Apr 16, 2009 at 1:19am
Apr 16, 2009 at 1:18am
fatllama (10)
And finally here is the entire program:
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
 
#include <iostream>
#include <string>
using namespace std;

struct data	{
		bool column[9][9];
		bool row[9][9];
		bool square[3][3][9];
		int board_main[9][9];
		bool board_input[9][9];
		int singleDimensionBoard[81];
	};


void get_info( data &board_data );
void calculate_solution( data &board_data );
void output_board( data &board_data );
bool cell_value_passes( int cellPosition, int value, data &board_data );
void initialize_arrays( data &board_data );
void saveCellValue( int positionInCells, int test_value, data &board_data );
void resetCellValue( int positionInCells, data &board_data );
int main()	{
	data board_data;
	

	//------------
	//start program
	//------------		
	initialize_arrays( board_data );				
	get_info( board_data );
	calculate_solution( board_data );
	output_board( board_data );
	
	//-----------
	//end program
	//-----------
	
	//testing
	return 0;
}


void get_info( data &board_data )	{
	
	string input_string;
	int x, y, value;
	value = 1;
	
	cout << "Sudoku solver! Enter the coordinates of every number you know of in a 9x9 sudoku board.\n";
	cout << "Input the numbers like this: [number],[y coordinate],[x coordinate]. Type 0 to exit.\n";
	
	//gets all the set values.
	while ( value > 0 )	{
		cout << "Enter: ";
		getline( cin, input_string );
		value = input_string[0]-48;
		x = input_string[4]-48;
		y = input_string[2]-48;
							
		if (!value)
			break;

		//places the values in the board
		cout << value << " (" << y << ", " << x << ")\n";
		board_data.board_main [ y-1 ][ x-1 ] = value;
		
		//-----------
		//creating book-keeping arrays
		//-----------
		board_data.column[x-1][value-1] = true;
		board_data.row[y-1][value-1] = true;
		board_data.square[(y-1)/3][(x-1)/3][value-1] = true;
		board_data.board_input[y-1][x-1] = true;	
	}
	
	for ( int loop1 = 0; loop1<9; loop1++ )	{
		for ( int loop2 = 0; loop2<9; loop2++ )	{
			board_data.singleDimensionBoard[9*loop1 + loop2] = board_data.board_main[loop1][loop2];
		}
	}
}



void calculate_solution( data &board_data ) {
	int positionInCells = 0;
	bool cellPassed;
	while ( positionInCells <= 80 )	{
				
		cout << "\n" << positionInCells;
		cellPassed = false;
		// Skip if user input cell
		// the value has been input by user and is fixed
		if ( board_data.board_input[positionInCells/9][positionInCells%9] )	{
			positionInCells++;
			continue;
		}
		int currentCellValue = board_data.singleDimensionBoard[positionInCells];
		resetCellValue( positionInCells, board_data );
			
		cout << " - ";
		// Cycle through the different cells until
		for ( int test_value = (currentCellValue + 1); test_value <= 9; test_value++ )	{
			cout << test_value;
			if ( cell_value_passes( positionInCells, test_value, board_data ) )	{
				saveCellValue( positionInCells, test_value, board_data );
				
				cellPassed = true;
				positionInCells++;
				break;
			}
		}
		if ( cellPassed )	
			continue;
		positionInCells--;
		
		while ( board_data.board_input[positionInCells/9][positionInCells%9] ) 
			positionInCells--;
							
		// By the way:
		// y = val/9
		// x = val%9
	}
}



void output_board( data &board_data ) {
	for ( int cycleThroughRows = 0; cycleThroughRows <= 8; cycleThroughRows++ ) {
		for ( int cycleThroughColumns = 0; cycleThroughColumns <=8; cycleThroughColumns++ ) {
			board_data.board_main[cycleThroughRows][cycleThroughColumns] = board_data.singleDimensionBoard[9*cycleThroughRows+cycleThroughColumns];
		}
	}
	int loop1, loop2;
	for ( loop1 = 0; loop1 < 9; loop1 ++ )	{
		cout << "\n";
		for ( loop2 = 0; loop2 < 9; loop2 ++ )	{
			cout << board_data.board_main[loop1][loop2];
		}
	}
}


// --------
// Checks the value of a cell for conflicts within the board
// Returns 0: fails-conflict
// Returns 1: passes-no conflict
// ---------
bool cell_value_passes ( int cellPosition, int value, data &board_data ) {
	int y, x;
	y = cellPosition/9;
	x = cellPosition%9;
	
	
	// fail if value is in this column
	if ( board_data.column[x][value-1] == true )
		return 0;
	
	// fail if value is in this row
	if ( board_data.row[y][value-1] == true )
		return 0;
		
	// fail if value in this square
	if ( board_data.square[y/3][x/3][value-1] == true )
		return 0;

	// passes all conditions; current value is good.
	return 1;

}


void initialize_arrays( data &board_data )	{
	//------------
	//initialize the array
	//------------
	int loop1, loop2, loop3;
	
	
	for ( loop1 = 0; loop1<9; loop1++ )	{
		for ( loop2 = 0; loop2 < 9; loop2++ )	{
			board_data.board_main[loop1][loop2] = 0;
		}
	}	
	
	for ( loop1 = 0; loop1<9; loop1++ )	{
		for ( loop2 = 0; loop2 < 9; loop2++ )	{
			board_data.board_input[loop1][loop2] = false;
		}
	}	
	
	for ( loop1 = 0; loop1<9; loop1++ )	{
		for ( loop2 = 0; loop2 < 9; loop2++ )	{
			board_data.row[loop1][loop2] = false;
		}
	}	
	
	for ( loop1 = 0; loop1<9; loop1++ )	{
		for ( loop2 = 0; loop2 < 9; loop2++ )	{
			board_data.column[loop1][loop2] = false;
		}
	}	
	
	for ( loop1 = 0; loop1<2; loop1++ )	{
		for ( loop2 = 0; loop2 < 2; loop2++ )	{
			for ( loop3 = 0; loop3 < 9; loop3 ++ )	{
				board_data.square[loop1][loop2][loop3] = false;
			}
		}
	}
}	

void saveCellValue( int positionInCells, int temp_value, data &board_data )	{
	
	board_data.singleDimensionBoard[positionInCells] = temp_value;
	board_data.row[positionInCells/9][temp_value-1] = true;
	board_data.column[positionInCells%9][temp_value-1] = true;
	board_data.square[positionInCells/27][(positionInCells%9)/3][temp_value-1] = true;
	
}

void resetCellValue( int positionInCells, data &board_data )	{
	if ( !board_data.singleDimensionBoard[positionInCells] )
		return;
	int badCellValue = board_data.singleDimensionBoard[positionInCells];
	board_data.row[positionInCells/9][badCellValue-1] = false;
	board_data.column[positionInCells%9][badCellValue-1] = false;
	board_data.square[positionInCells/27][(positionInCells%9)/3][badCellValue-1] = false;
	
	board_data.singleDimensionBoard[positionInCells] = 0;
	
}
Edit & run on cpp.sh


Thank you all so much for your help.

If I didn't make something clear enough, I apologize in advance.
Last edited on Apr 16, 2009 at 1:20am
Apr 16, 2009 at 12:36pm
jsmith (5804)
In your cell_passes_value function why are you comparing cell values (integers) to boolean true/false
values, and why are you returning 0 or 1 instead of false or true, since the function is declared to
return bool?
Apr 16, 2009 at 8:54pm
fatllama (10)
I have 3 arrays that I use to check whether or not a number can be used:
board_data.row[9][9]
board_data.column[9][9]
board_data.square[3][3][9]

For row and column, the first array denotes which row or column we are looking at, while the second number is the value of the number we are looking at. When a number is saved, its row, column, and square location are recorded here, and the second array at that value-1 is set to true. It's the same with the square array, except that the location is recorded by y and x values.
Apr 16, 2009 at 9:31pm
arcadiu (82)
Im sorry if this sounds rude (youve done good code and I am a newbie) but I was always told that when ever you make a program make sure there are no gaps in the code that people can exploit. What I am getting at is that at the start if you entered something like 'fhdhghdhghdhgjcjg', a non numeric value, it outputs the number, y and x co-ordinate so if some1 entered something wrong by mistake, they would have to restart the program.

Use something like if the variable is not == to a numeric value, then repeat the last step and output a message saying thats an incorrect value.

I am sorry if that offended you and that I can not assist in solving this problem.

Thanks

Apr 16, 2009 at 9:59pm
fatllama (10)
except that I'm not making a commercial program where nutjobs will input random strings of characters into the input :D.

anyways, I figured it out...my algorithm's been fine all along, it's just that I didn't initalize the board_data.square array properly >.>. Spent about 4 hours debugging it and never bothered to check that one array...
Oh well, it's all fixed now, sorry for bothering you all.
Topic archived. No new replies allowed.