Help to optimize the sudoku code (J1)

1

Problem: https://www.codechef.com/problems/J1

Hello everyone, I’m having trouble completing the “J1” problem.

The time limit for executing the problem is 0.10 but my code is ending at 0.11.

I used the backtracking technique to solve the problem, it worked, but not in a timely manner.

Could someone help me on how I can optimize this code?

My code:

#pragma GCC optimize("O2")
#include <iostream>

using namespace std;

char a[9][9];

struct SudokuReturn {
	int line;
	int column;
	bool found;

	SudokuReturn(int l, int c, bool f) {
		line = l;
		column = c;
		found = f;
	}
};

SudokuReturn getNextPosition() {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (a[i][j] == '.') {
				return SudokuReturn(i, j, true);
			}
		}
	}

	return SudokuReturn(0, 0, false);
}

bool existsInLine(int line, int number, char a[9][9]) {
	for (int i = 0; i < 9; i++) {
		if (a[line][i] == '0' + number)
			return true;
	}

	return false;
}

bool existsInColumn(int column, char number, char a[9][9]) {
	for (int i = 0; i < 9; i++) {
		if (a[i][column] == number)
			return true;
	}

	return false;
}

bool existsInSubGrid(int line, int column, char number, char a[9][9]) {
	int lineX = line - (line % 3);
	int columnX = column - (column % 3);

	for (int i = lineX; i < lineX + 3; i++) {
		for (int j = columnX; j < columnX + 3; j++) {
			if (a[i][j] == number)
				return true;
		}
	}

	return false;
}

bool isValid(int line, int column, int number, char a[9][9]) {
	char cNumber = '0' + number;

	if (!existsInColumn(column, cNumber, a) &&
		!existsInLine(line, cNumber, a) &&
		!existsInSubGrid(line, column, cNumber, a)) {
		return true;
	}

	return false;
}

bool solveSudoku() {
	SudokuReturn p = getNextPosition();

	if (p.found) {
		for (int i = 1; i <= 9; i++) {
			if (isValid(p.line, p.column, i, a)) {
				a[p.line][p.column] = '0' + i;

				if (solveSudoku()) return true;
			}

			a[p.line][p.column] = '.';
		}
	}
	else {
		return true;
	}

	return false;
}

void readCell(char(&a)[9][9]) {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> a[i][j];
		}
	}
}

int main() {
	int t;
	cin >> t;

	while (t--) {
		readCell(a);
		solveSudoku();

		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << a[i][j];
			}

			cout << endl;
		}
	}
}