OiO.lk Community platform!

Oio.lk is an excellent forum for developers, providing a wide range of resources, discussions, and support for those in the developer community. Join oio.lk today to connect with like-minded professionals, share insights, and stay updated on the latest trends and technologies in the development field.
  You need to log in or register to access the solved answers to this problem.
  • You have reached the maximum number of guest views allowed
  • Please register below to remove this limitation

Determining the run time of an algorithm solving Latin Square

  • Thread starter Thread starter cong le
  • Start date Start date
C

cong le

Guest
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!
<p>any help would be appreciated.</p>
<p>Here is the problem: <a href="https://erich-friedman.github.io/puzzle/latin/" rel="nofollow noreferrer">https://erich-friedman.github.io/puzzle/latin/</a></p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>So here my question, What is the possible time complexity of this type of problem, How do you approach this?</p>
<p>Thank you!</p>
 

Latest posts

J
Replies
0
Views
1
jbowerbir
J
Top