C++

Forum

 
Generate Multiple solutions for sudoku game

panconcafe (31)
Hello! I need to program a recursive method to find all the possible solutions of a Sudoku puzzle of 16x16. the characters go from 0 to 9 and from a to f. So far, I can only output one solution, but I'm not sure what to do to generate multiple solutions for one puzzle.
Here is my code trying to output more than one solution. Is there anything I have to change?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
  #include "Sudoku.h"
#include <fstream>
#include <iostream>

using namespace std;

int main(){
	ifstream fin("input.txt");
	if (!fin) {
		cout << "Error: Input file does not exists" << endl;
		system("pause");
		return -1;
	}
	ofstream fout("solution.txt");
	Sudoku sudoku;
	sudoku.load_data(fin);
	sudoku.solve(fout);
	//sudoku.print_solution(fout);
	fin.close();
	fout.close();
	system("pause");
	return 0;
}


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
 
  #ifndef SUDOKU_H
#define SUDOKU_H
#include <iostream>
using std::istream;
using std::ostream;

class Sudoku {

public:
	
	Sudoku(); 
	Sudoku(const Sudoku&); 
	~Sudoku(); 

	const Sudoku& operator = (const Sudoku&); 
	void load_data(istream&);
	void solve(ostream&); //Wrapper function
	void print_solution(ostream&) const; 

private: 
	//Data Fields
	char** board; //2D Array 
	static const int SIZE;
	static const char BLANK; //Means dot
	unsigned int solutions;
	bool solved; //Solved or not

	
	int next_row_index(int, int)const; //Row index of the next cell (row major order).
	int next_col_index(int, int)const; //Column index of the next cell (row major order).
	bool in_same_row(int, char) const; //test if a digit already exists in the row
	bool in_same_col (int, char) const; //test if a digit already exists in the column
	bool in_same_grid(int, int, char)const; //test if a grid already exists in a 4 by 4 grid
	void solve(int, int, ostream&); //Solve the puzzle starting from a cell recurisve solution
	bool is_safe(int, int, char);


};
#endif  


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
 
  #include "Sudoku.h"

#include <string>

using namespace std;

const int Sudoku::SIZE = 16;
const char Sudoku::BLANK = '.';

Sudoku::Sudoku(): solved(false), solutions(0) {
	board = new char* [SIZE]; 
	for (int row = 0; row < SIZE; row++) { 
		board[row] = new char[SIZE];
	}
}
const Sudoku& Sudoku::operator=(const Sudoku& rhs) {
	
	if (this != &rhs) {
		
		if (board) {
			for (int row = 0; row < SIZE; row++) {
				delete[] board[row]; 
			}
			delete[] board;
			board = NULL;
		}
		
		solved = rhs.solved;
	
		board = new char* [SIZE];
		for (int row = 0; row < SIZE; row++) {
			board[row] = new char[SIZE];

			for (int col = 0; col < SIZE; col++) {
				board[row][col] = rhs.board[row][col];
			}
		}
	}
	return *this;
}
Sudoku::Sudoku(const Sudoku& other) {
	board = NULL;
	*this = other;
}

Sudoku::~Sudoku() {
	for (int row = 0; row < SIZE; row++) { delete[] board[row]; }
	delete[] board;
}


void Sudoku::load_data(istream& in) {
	string current_line;
	for (int row = 0; row < SIZE; row++) {
		getline(in, current_line);
		for (int col = 0; col < SIZE; col++) {
			board[row][col] = current_line[col];
		}
	}

}

int Sudoku::next_row_index(int row, int col)const {
	if ((row == SIZE - 1) && (col == SIZE - 1)) { return -1; } 

	if (col == SIZE - 1) { return row + 1; } 
	else { return row; } //
}


int Sudoku::next_col_index(int row, int col)const {
	if ((row == SIZE - 1) && (col == SIZE - 1)) { return -1; } 
	if (col == SIZE - 1) { return 0; }
	else { return col + 1; } 
}

bool Sudoku::in_same_row(int row, char digit) const {

	for (int col = 0; col < SIZE; col++) {
		if (board[row][col] == digit) {
			return true;
		}
	}
	return false;
}

bool Sudoku::in_same_col(int col, char digit)const {

	for (int row = 0; row < SIZE; row++) {
		if (board[row][col] == digit) {
			return true;
		}
	}
	return false;
}

bool Sudoku::in_same_grid(int row, int col, char digit)const {
	int grid_start_row = row / 4*4, grid_start_col = col /4*4;

	for (int i = grid_start_row; i < grid_start_row + 4; i++) {

		for (int j = grid_start_col; j < grid_start_col + 4; j++) {

			if ((board)[i][j] == digit) {
				return true;
			}

		}
	}
	return false; 
}

bool Sudoku::is_safe(int row, int col, char character){
		if (!in_same_row(row, character) && !in_same_col(col, character) && !in_same_grid(row - row % 4, col - col % 4, character)){
			return true;
	}

}
void Sudoku::solve(int row, int col, ostream& out) {
	
	if ((row == -1) || col == -1) {
		out << "Solution " << ++solutions << std::endl << std::endl;
		print_solution(out);
		out << std::endl;
	}
	/*if (board[row][col] != BLANK) { //goes to the next cell
		solve(next_row_index(row, col), next_col_index(row, col), out);
	}*/
	else {
		for (char digit = '0'; digit <= '9'; digit++) {
				// Check if it is safe to place
			if (in_same_row(row, digit)) { continue; }
			if (in_same_col(col, digit)) { continue; }
			if (in_same_grid(row, col, digit)) { continue; }

			if (is_safe(row, col, digit)) {

					//Assigning the character in position of the grid
				board[row][col] = digit;

					//  Checking for next possibility 
				solve(row, col + 1, out);

					// Removing the assigned character to the next column
				board[row][col] = 0;
			}

		}
		for (char letter = 'a'; letter <= 'f'; letter++) {//I repeated it here but the letters to attempt the same idea
			if (in_same_row(row, letter)) { continue; }
			if (in_same_col(col, letter)) { continue; }
			if (in_same_grid(row, col, letter)) { continue; }
			if (is_safe(row, col, letter)) {
				board[row][col] = letter;
				solve(row, col + 1, out);
				board[row][col] = 0;
				}

			}
		}
	}


void Sudoku::solve(ostream & out) {
	solve(0,0,out);
}



void Sudoku::print_solution(ostream& out)const {
	if (!solved) {out << "Attempt to output solution for unsolved puzzle." << endl;}
	else {
		for (int row = 0; row < SIZE; row++) {
			for (int col = 0; col < SIZE; col++) {out << board[row][col];}
			out << endl;
		}
	}
}

Input
b2574a9f6e01c38d
e409b82cd53af176
1af.............
d86.............
07e......6a.....
359......4df806b
cfad2136.be07459
6b840f5d.c93e2a1
2e1f37b4.a690dc8
76c892a50d1b4ef3
4935e0d8f2c76b1a
adb0f6c.....9725
912e740baf5638dc
837ad962c1b45f0e
f04bc58ae32d1697
5cd613fe90782ab4

This one generates 2 solutions
Last edited on
lastchance (6980)
I haven't tried it - does your code produce ONE solution?

If so then don't mark the solution as found but display the board, increment the tally of successes and let the backtracking continue to find another solution.
panconcafe (31)
This code does not produce one solution. I already got that in my first attempt. But now I'm editing the code to output multiple solutions.
Do you mean here?
1
2
3
4
5
 

	if ((row == -1) || col == -1) {
		solved = true;
		return;
	}
lastchance (6980)
Yes, if you get to that point your code is presumably telling you that you have one solution.

What you need to do is (after outputting the solution) let the backtracking continue as if you HADN'T found a solution. Then it will automatically go on to find subsequent ones.


I did a similar one here:
http://www.cplusplus.com/forum/beginner/277629/#msg1198376
It's a different problem (N-Queens problem), but if findAllCases is true, then the "completion" point will actually return false, so that the backtracking continues to find the next solution.
1
2
3
4
5
 
   if ( i == N )                                           // *** COMPLETION
   {
      tcount++;
      return !findAllCases;
   }
Last edited on
panconcafe (31)
I just fixed that part and I was editing the function a bit (I updated my code up there) but I still missing something. I got this error: 'function' : recursive on all control paths, function will cause runtime stack overflow
Any idea on how to fix it? Based on my code

I will take a look on your code :D
Last edited on
lastchance (6980)
@panconcafe,
Can you show your successful one-solution code? It is that one that should be easily amended.

Show it BELOW this post, please. It confuses things if you go back and edit earlier posts.
Last edited on
panconcafe (31)
Sure!
here it is the code that outputs only one solution. This was the code I was trying to edit to output more than one solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#include "Sudoku.h"
#include <fstream>
#include <iostream>

using namespace std;

int main(){
	ifstream fin("input.txt");
	if (!fin) {
		cout << "Error: Input file does not exists" << endl;
		system("pause");
		return -1;
	}
	ofstream fout("solution.txt");
	Sudoku sudoku;
	sudoku.load_data(fin);
	sudoku.solve();
	sudoku.print_solution(fout);
	fin.close();
	fout.close();
	system("pause");
	return 0;
}


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
 
#ifndef SUDOKU_H
#define SUDOKU_H
#include <iostream>
using std::istream;
using std::ostream;

class Sudoku {

public:
	
	Sudoku(); 
	Sudoku(const Sudoku&); 
	~Sudoku(); 

	const Sudoku& operator = (const Sudoku&); 
	void load_data(istream&);
	void solve(); //Wrapper function
	void print_solution(ostream&) const; 

private: 
	//Data Fields
	char** board; //2D Array 
	static const int SIZE;
	static const char BLANK; //Means dot
	unsigned int solutions;
	bool solved; //Solved or not

	
	int next_row_index(int, int)const; //Row index of the next cell (row major order).
	int next_col_index(int, int)const; //Column index of the next cell (row major order).
	bool in_same_row(int, char) const; //test if a digit already exists in the row
	bool in_same_col (int, char) const; //test if a digit already exists in the column
	bool in_same_grid(int, int, char)const; //test if a grid already exists in a 4 by 4 grid
	void solve(int, int); //Solve the puzzle starting from a cell recursive solution


};
#endif  


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
 
#include "Sudoku.h"

#include <string>

using namespace std;

const int Sudoku::SIZE = 16;
const char Sudoku::BLANK = '.';

Sudoku::Sudoku(): solved(false), solutions(0) {
	board = new char* [SIZE]; 
	for (int row = 0; row < SIZE; row++) { 
		board[row] = new char[SIZE];
	}
}
const Sudoku& Sudoku::operator=(const Sudoku& rhs) {
	
	if (this != &rhs) {
		
		if (board) {
			for (int row = 0; row < SIZE; row++) {
				delete[] board[row]; 
			}
			delete[] board;
			board = NULL;
		}
		
		solved = rhs.solved;
	
		board = new char* [SIZE];
		for (int row = 0; row < SIZE; row++) {
			board[row] = new char[SIZE];

			for (int col = 0; col < SIZE; col++) {
				board[row][col] = rhs.board[row][col];
			}
		}
	}
	return *this;
}
Sudoku::Sudoku(const Sudoku& other) {
	board = NULL;
	*this = other;
}

Sudoku::~Sudoku() {
	for (int row = 0; row < SIZE; row++) { delete[] board[row]; }
	delete[] board;
}


void Sudoku::load_data(istream& in) {
	string current_line;
	for (int row = 0; row < SIZE; row++) {
		getline(in, current_line);
		for (int col = 0; col < SIZE; col++) {
			board[row][col] = current_line[col];
		}
	}

}

int Sudoku::next_row_index(int row, int col)const {
	if ((row == SIZE - 1) && (col == SIZE - 1)) { return -1; } 

	if (col == SIZE - 1) { return row + 1; } 
	else { return row; } //
}


int Sudoku::next_col_index(int row, int col)const {
	if ((row == SIZE - 1) && (col == SIZE - 1)) { return -1; } 
	if (col == SIZE - 1) { return 0; }
	else { return col + 1; } 
}

bool Sudoku::in_same_row(int row, char digit) const {

	for (int col = 0; col < SIZE; col++) {
		if (board[row][col] == digit) {
			return true;
		}
	}
	return false;
}

bool Sudoku::in_same_col(int col, char digit)const {

	for (int row = 0; row < SIZE; row++) {
		if (board[row][col] == digit) {
			return true;
		}
	}
	return false;
}

bool Sudoku::in_same_grid(int row, int col, char digit)const {

	int grid_start_row = row / 4*4, grid_start_col = col /4*4;

	for (int i = grid_start_row; i < grid_start_row + 4; i++) {

		for (int j = grid_start_col; j < grid_start_col + 4; j++) {

			if ((board)[i][j] == digit) {
				return true;
			}

		}
	}
	return false; 
}


void Sudoku::solve(int row, int col) {
	//Base 1: Means a solution was found 
	if ((row == -1) || col == -1) {
		solved = true;
		return;
	}
	//If the current cell is not a Blank cell
	if (board[row][col] != BLANK) {
		solve(next_row_index(row, col), next_col_index(row, col)); //Goes to the necxt cell
	}
	else { //We are at a blank cell

		for (char digit = '0'; digit <= '9'; digit++) {
			if (in_same_row(row, digit)) { continue; } //If the number already appears
			if (in_same_col(col, digit)) { continue; }
			if (in_same_grid(row, col, digit)) { continue; }

			//Fill the cell int he digit
			board[row][col] = digit;
			//Solve the puzzle from the next cell
			solve(next_row_index(row, col), next_col_index(row, col));

			//If not solutuion found, change the cell back to blank and try next digit
			if (!solved) {
				board[row][col] = BLANK;
			}

		}
		for (char letter = 'a'; letter <= 'f'; letter++) {
			if (in_same_row(row, letter)) { continue; } //If the number already appears
			if (in_same_col(col, letter)) { continue; }
			if (in_same_grid(row, col, letter)) { continue; }
			//Fill the cell int he digit
			board[row][col] = letter;
			//Solve the puzzle from the next cell
			solve(next_row_index(row, col), next_col_index(row, col));

			//If not solutuion found, change the cell back to blank and try next digit
			if (!solved) {
				board[row][col] = BLANK;
			}

		}


	}
}


void Sudoku::solve() {
	solve(0, 0);
}

void Sudoku::print_solution(ostream& out)const {

	if (!solved) {//Cant output solution for unsolved puzzle
		out << "Attempt to output solution for unsolved puzzle." << endl;
	}
	out << "Found Solution" << endl;
	for (int row = 0; row < SIZE; row++) {
		for (int col = 0; col < SIZE; col++) {
			out << board[row][col];
		}
		out << endl;
	}
}

Last edited on
lastchance (6980)
I'n not in a position to download and try your code, but what happens if, in your completion if - block, you output the solution, set solved to false and return. It should continue to the next solution.

Note that it would be convenient to have a member function just to display the board.
panconcafe (31)
Do you mean this?
1
2
3
4
5
 
if (!solved) {
				board[row][col] = BLANK;
				solved = false;
				return;
			}


And the print function like this?
1
2
3
4
5
6
7
8
9
 
void Sudoku::print_solution(ostream& out)const {

	for (int row = 0; row < SIZE; row++) {
		for (int col = 0; col < SIZE; col++) {
			out << board[row][col];
		}
		out << endl;
	}
}
Last edited on
lastchance (6980)
Your print function is fine.

You are using something quite odd at completion. What does this do (once your print output is available)?

1
2
3
4
5
 
if ((row == -1) || col == -1) {
                print_solution( cout );
		solved = false;           // signals to the calling routine to blank the cell and try the next one
		return;
	}
panconcafe (31)
I tried it but I got a "Bug Assertion Failed" warning and it didn't produced any output
Last edited on
lastchance (6980)
I can't reproduce your problem.

I ran it with the changes I suggested above, removing the output from main and writing to screen (actually redirected outside to file) when it found a solution.

It actually appears to have found 4 solutions. The differences between them are extremely small - you have to look VERY closely at them below.
Attempt to output solution for unsolved puzzle.
Found Solution
b2574a9f6e01c38d
e409b82cd53af176
1af36d70498cb5e2
d86c5e13b7f2a940
07e18b4926a5dc3f
3592ace714df806b
cfad21368be07459
6b840f5d7c93e2a1
2e1f37b45a690dc8
76c892a50d1b4ef3
4935e0d8f2c76b1a
adb0f6c1384e9725
912e740baf5638dc
837ad962c1b45f0e
f04bc58ae32d1697
5cd613fe90782ab4
Attempt to output solution for unsolved puzzle.
Found Solution
b2574a9f6e01c38d
e409b82cd53af176
1af36d70498cb5e2
d86c5e13b7f2a940
07e28b4916a5dc3f
3591ace724df806b
cfad21368be07459
6b840f5d7c93e2a1
2e1f37b45a690dc8
76c892a50d1b4ef3
4935e0d8f2c76b1a
adb0f6c1384e9725
912e740baf5638dc
837ad962c1b45f0e
f04bc58ae32d1697
5cd613fe90782ab4
Attempt to output solution for unsolved puzzle.
Found Solution
b2574a9f6e01c38d
e409b82cd53af176
1afc6d734982b5e0
d8635e10b7fca942
07e18b4926a5dc3f
3592ace714df806b
cfad21368be07459
6b840f5d7c93e2a1
2e1f37b45a690dc8
76c892a50d1b4ef3
4935e0d8f2c76b1a
adb0f6c1384e9725
912e740baf5638dc
837ad962c1b45f0e
f04bc58ae32d1697
5cd613fe90782ab4
Attempt to output solution for unsolved puzzle.
Found Solution
b2574a9f6e01c38d
e409b82cd53af176
1afc6d734982b5e0
d8635e10b7fca942
07e28b4916a5dc3f
3591ace724df806b
cfad21368be07459
6b840f5d7c93e2a1
2e1f37b45a690dc8
76c892a50d1b4ef3
4935e0d8f2c76b1a
adb0f6c1384e9725
912e740baf5638dc
837ad962c1b45f0e
f04bc58ae32d1697
5cd613fe90782ab4
Press any key to continue . . .
panconcafe (31)
Hello! Thank you so much! The error I got was because I did not inserted the correct input file LOL but now I got the code!
My output now is correct! and yes the differences are small. Thank you so much!
Topic archived. No new replies allowed.