Hey guys I need help on reducing this code time complexity, may someone please update the code below!

Question

#include <iostream>

using namespace std;

#define N 16

void print(int arr[N][N]) {
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
cout << arr[i][j]<< " ";
if (j < N - 1){
cout << " ";
}
}
cout << endl;
}
}

bool isSafe(int grid[N][N], int row, int col, int num){
for (int x = 0; x < N; x++){
if (grid[row][x] == num || grid[x][col] == num){
return false;
}
}

int boxSize = 4; // Since it's a 16x16 Sudoku, each box size is 4x4
int startRow = row - row % boxSize;
int startCol = col - col % boxSize;

for (int i = 0; i < boxSize; i++){
for (int j = 0; j < boxSize; j++){
if (grid[i + startRow][j + startCol] == num){
return false;
}
}
}

return true;
}

bool solveSudoku(int grid[N][N], int row, int col){
if (row == N - 1 && col == N){
return true;
}

if (col == N){
row++;
col = 0;
}

if (grid[row][col] > 0){
return solveSudoku(grid, row, col + 1);
}

for (int num = 1; num <= N; num++){
if (isSafe(grid, row, col, num)){
grid[row][col] = num;

if (solveSudoku(grid, row, col + 1)){
return true;
}

grid[row][col] = 0;
}
}

return false;
}

int main(){
int grid[N][N];

for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
cin >> grid[i][j];
}
}

if (solveSudoku(grid, 0, 0)){
print(grid);
}
else{
cout << "No Solution" << endl;
}
return 0;
}

Answer 1

Gomolemo this won't reduce time complexity, but there is potential to make isSafe run faster if you are willing to make a concession on flexibility.

Since boxSize is hard-coded as 4, which is a binary bit value, the loop limit calculations can be replaced with much faster bitwise operations. Also, we can displace some addition operations so that they are done outside the loops by adjusting the loop limits, and again replacing them with faster bitwise operations. These changes could make an improvement on timing, since isSafe is the most frequently called function.

int boxMask = 3; // 4 - 1, since it's a 4x4 box
int startRow = row & ~boxMask;
int startCol = col & ~boxMask;
int endRow = startRow | boxMask;
int endCol = startcol | boxMask;
for (int i = startRow; i <= endRow; i++)
for (int j = startCol; j <= endCol; j++)
if (grid[i][j] == num) return false;

Answer 2

i don't know c++ well enough to help with that. BUT, you might have better luck getting help if you:
1 - save this code in the code playground and post the link here.
2 - show us how you've tried to accomplish what you are needing help on
3 - include some more info, like what is this code supposed output/do, etc...

Answer 3

Do you expect everyone to read your whole code and figure out what it does?
You need to save it in solo learn playground and then share. And use comments in that

Answer 4

Brian thanks a lot for the tips, really saved me some muscle!