C++

Forum

 
How to make sudoku16x16 as fast as possible

UnkownUser (2)
Good day , I need assistance in making my sudoku as fast as possible currently it completes it in 1163 seconds

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
 
#include <iostream>

#include <algorithm>

#define N 16

using namespace std;

class Sudoku
{
	public:
		int matrix[N][N];
		bool solve(int matrix[N][N]);
		bool find_zero(int matrix[N][N], int &row, int &col);
		bool valid_positions(int matrix[N][N], int row, int col, int num);
		void print_matrix(int matrix[N][N]);
};

bool Sudoku::find_zero(int matrix[N][N], int &row, int &col){
	for (row = 0; row < N; row++){
		for (col = 0; col < N; col++){
			if (matrix[row][col] == 0){
				return true;
			}
		}
	}
	return false;
}

bool Sudoku::valid_positions(int matrix[N][N], int row, int col, int num){
	for (int i = 0; i < N; i++){
		if (matrix[row][i] == num){
			return true;
		}
	}
	for (int i = 0; i < N; i++){
		if (matrix[i][col] == num){
			return true;
		}
	}
	int box_row = (row / 4) * 4;

	int box_col = (col / 4) * 4;

	for (int i = 0; i < 4; i++){
		for (int j = 0; j < 4; j++){
			if (matrix[box_row + i][box_col + j] == num){
				return true;
			}
		}
	}
	return false;
}

bool Sudoku::find_zero(int matrix[N][N], int &row, int &col);

bool Sudoku::valid_positions(int matrix[N][N], int row, int col, int num);

bool Sudoku::solve(int matrix[N][N]){
	Sudoku grid;
	int row;
	int col;
	if (!grid.find_zero(matrix, row, col)){
		return true;
	}

	for (int num = 1; num <= N; num++){
		if (!grid.valid_positions(matrix, row, col, num)){
			matrix[row][col] = num;
			if (grid.solve(matrix)) {
				return true; //if value fits its true....
			}
			matrix[row][col] = 0; //otherwise backtrack amd replace it with a 0 if false
		}
	}
	return false;
}

void Sudoku::print_matrix(int matrix[N][N]){
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			if (matrix[i][j] >= 10){
				cout << char(matrix[i][j] + 55) << " ";
			}
			else{
				cout << matrix[i][j];
				if (j != N - 1){
				cout << " ";
			}
			}
		}
		cout << endl;
	}
}

int main(){
	int matrix[N][N];
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			char x;
			cin >> x;
			if (int(x) < 58){
				matrix[i][j] = x - 48;
			}
			else{
				matrix[i][j] = x - 55;
			}
		}
	}
	Sudoku grid;

	if (grid.solve(matrix) == true){
		cout << endl;
		grid.print_matrix(matrix);
	}
	else{
		cout << "No Solution" << endl;
	}
	return 0;
}
Last edited on
salem c (3700)
Maybe post your real code, not code full of errors?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
$ g++ foo.cpp
foo.cpp: In function ‘int main()’:
foo.cpp:99:26: error: ‘k’ was not declared in this scope
   99 |   for (int j = 0; j < N; k++){
      |                          ^
foo.cpp:103:5: error: ‘grid’ was not declared in this scope
  103 |     grid[i][j] = x - 48;
      |     ^~~~
foo.cpp:106:5: error: ‘grid’ was not declared in this scope
  106 |     grid[i][j] = x - 55;
      |     ^~~~
foo.cpp:114:8: error: ‘class Sudoku’ has no member named ‘display_grid’
  114 |   grid.display_grid(matrix);
      |        ^~~~~~~~~~~~


You're not using your class member array AT ALL.
jonnin (11437)
right off the bat, you want it as fast as possible, you need to see how many CPU you have and thread it out so that it can do blocks in parallel. This means that instead of back-tracking, it forward tracks all the paths and keeps the winner.

Also, IIRC, you don't need to guess (and maybe that means backtrack?). I think suduko is defined to be perfectly solvable, that is, no guessing needed, all cells can be resolved via logic.
seeplus (6589)
You can solve a solvable Suduko iteratively without any recursion/backtracking. My version (sorry, no you can't have the source) solves even the hardest solvable versions in less than a second.
jonnin (11437)
curious, did you thread it? Given cpu speed, I don't think its required, and if you did it right it may even slow it down, but I am nosey :)
seeplus (6589)
No. I use a 3d-array for the board...
dhayden (5798)
Please ask more descriptive questions. Without actually reading your code, there's no way to know if you're talking about generating sudoku puzzles or solving them. Looking at the code, I see that you're solving.

Your code is solving by brute force. Try using a better algorithm (or several) read some sudoku forums to learn about techniques to solve puzzles and then code them up.

I have a program that solves puzzles in about 1/4 second on a hand-held calculator. Good algorithms can make that big a difference.

Once trick that will really help: you do lots of operations on a "group" of N cells. The group is a row, column or a box. valid_positions() is an example. Convert the code so you pass a collection of pointers to the N cells in a group. This will save you a ton of repeated code.

It's been many years and I don't have the code in front of me, but I think I stored two values for each cell. The first was the value of the cell when the value was known. The second was a bitset of the values that were possible in that cell. At the beginning, a cell either contains a known value, or all N bits in the bitset are set, meaning that all N values are possible. Then you go through your algorithms, clearing bits from the possibilities bitset as you determine that a specific value can't be in a specific cell. When only 1 bit is left in a cell, you know the value of that cell.

Hope this helps a little.
seeplus (6589)
Yes - I used a variation of that algorithm. Rather than using a bitset I just used a 3rd dimension for the possible values for that cell. This uses more memory but has slightly easier processing.
Topic archived. No new replies allowed.