any help would be appreciated.

Here is the problem: https://erich-friedman.github.io/puzzle/latin/

Now, I write some code to solve the problem and want to find the time complexity of the problem, I use a backtracking method where I will try to find the next location through using functions to check whether the next location violate the rules, if it does and there is no other steps to go to, backtrack to the previous location.

Now, the obvious part in here is that in a blank board of n x n, the solution are numerous that is you can find n^n solution, but we only need one solution which mean that this scenario will be the best case scenario where the run time is O(n) assuming that we only need to find one solution.

The problem that I have is identify which scenario will cause the backtracking algorithm to take the most time, I also don’t know if the complexity need to be calculated also involve case where there are no solution, because this is essentially what I try to do the whole time, I make up a case where the solution is unsolvable with a n x n matrix, then calculate the T(n) of this scenario, and the run time is way to big.

So here my question, What is the possible time complexity of this type of problem, How do you approach this?

Thank you!