0

Of late, I have solved a few problems using backtracking(Sudoku solver, N Queens problem). While I can intuitively understand that backtracking is better than brute force, I am unable to reason it out mathematically/asymptotically. For instance, say we are implementing a sudoku solver for a N * N grid, where there are K empty slots to be filled. Here:

  1. There are NK end states of the N * N grid.
  2. At the end of filling each slot, we check if it's still valid and this validation takes O(N) time.

[A brute force approach would be to fill out all K slots using any of the N digits and then checking that the final state is a valid grid.]

In all, we reason that it takes O(NK*NK) = O(KNK+1)

Well, that is a fair enough bound for the brute force algorithm, but in a backtracking algorithm, we prune out a lot of the invalid states much, much earlier in the filling process. Clearly, the backtracking algorithm is very fast in practise, compared to the brute force implementation. I searched for similar questions and found this one, but it uses the same bounds as the brute force. How can we asymptotically prove that this backtracking algorithm is better than the brute force algorithm?

EDIT: Since people are voting to close this question as "Too-Broad", I am iterating that I am looking for the specific case of the aforementioned Sudoku solver only. You can however, share any ideas that you usually use to reason out asymptotically that a given backtracking problem is faster than a brute force approach.

Community
  • 1
  • 1
Aravind
  • 3,169
  • 3
  • 23
  • 37
  • You could talk a bit about the backtracking algorithm applied to the sudoku problem. – Selçuk Cihan Jan 19 '16 at 09:22
  • @SelçukCihan: The backtracking algorithm is just filling up a empty slot with a number from 1 to 9, and then try to continue filling the other empty slots and see if it works. If it does not work, we roll back the entries we did, and try a different number in that empty slot and try again. – Aravind Jan 19 '16 at 14:42

1 Answers1

1

Asymptotically the backtracking is usually the same as the brute force.

The reason for this is that it's hard to argue about the optimizations you're going to see in practice for the worst case. For the sudoku you might argue that in the worst case (empty board) your performance is going to be O(N! * N-1! * N-2! ...) (as you don't try obviously wrong options). However this is far from the average case, where likely a lot of the spots have only one eligible value and you only need to try few eligible values in a few slots (less than the number of empty slots). So for a 20*20 puzzle where you only have 10 slots with 3 eligible values each your performance is going to look more like 3^10 than 20!*19!*18!... There's no guarantee, but in practice it's faster for most cases.

This is similar to other algorithms where the worst case can be really bad, but the average one is very good. For example QSort is O(N^2) given that you could always pick the worst possible pivot. However that is very unlikely so the average is performance is more like NlogN.

Sorin
  • 11,863
  • 22
  • 26
  • In Quick sort we are able to come up with the average performance bound of O(NlogN). I do understand when you say "There's no guarantee, but in practice it's faster for most cases". Like we do for quick sort, is there *anything* we can mathematically do(without assuming too much about the input sudoku grid) to come up with some tighter bound? Say, I am participating in a programming contest, how can I convince myself that this program will run in time before coding it? – Aravind Jan 19 '16 at 14:39
  • 1
    There's nothing in complexity analysis that tells you if it will run in time. QSort and HeapSort are both O(NlogN) for most cases, but in practice, for int, QSort is going to be much faster than HeapSort. Also some implementation of sort do insertion sort when the range is sufficiently small (O(N^2)) because in practice it's faster than the QSort for that little data. If you are participating in a programming context and you've convinced yourself that the problem is NP, just make sure that you are eliminating bad partial solutions as early as possible. – Sorin Jan 19 '16 at 16:13
  • Sure, that makes sense. Thanks. – Aravind Jan 20 '16 at 13:15