Sunday, November 22, 2015

Brute Force

This is a declaration of war against time. We will reach 24 posts in this year no matter what! If you think why is that a big deal, you obviously haven’t spent much time here on our blog. Check the right sidebar and you will notice the total number of posts in any given year is a multiple of 12… (ignoring the issue of time zones, which makes some odd numbers appear), get it now? Another issue which tells us you have NOT spent much time here is the fact that you have not yet voted on the poll sitting right at your eye-level slightly to the right!

Now that we have gotten past that, let me get on to the agenda of this post: Brute Force Algorithm (BFA) to solve a Sudoku. Actually, Smart Brute Force Algorithm (SBFA). In fact, so smart that it is slightly better than this ‘official’ one here. But also so damn smart that it makes me look stupid by making me ask why didn’t I come up with it in the first place! OK, that’s all the smartass comments from me… let’s have some concrete discussions.

As you know, the ‘SuDoKu Solver’ tab exists above but till about a few weeks ago, the v6.9 that you could get from there had a BFA that took nearly 11 minutes to solve one of the “world’s hardest” Sudokus on my SP1:

Hard (655s)

This was because I was wading through all the possible values of a particular cell starting with the first empty cell in row 1 and then stepping through subsequent cells row-wise linearly. Now that I have updated SS to v7.0 with SBFA, it gets solved in about 1.5 minutes!

Hard (91s)

This is because now I (still) wade through all the possible values of a particular cell but starting with the one that has the least number of those values and then stepping through similar least-possible-values-possessing-cells. So the difference with previous algorithm is non-linearity! This is still the same effort as the ‘official’ one linked above… difference is that I figure out the possible values only once… then keep updating this 3d (cell) array at each recursive level whereas in the other code, this 3d array is constructed at each level. Sadly, the overhead of constructing it every time doesn’t quite catch up to keeping up-to-date a single array till very large number of recursions. I will give examples of both cases below.

So now, we basically forget the GUI and measure the time that only the bare-bones SBFA code takes. First, let’s take the “world’s hardest” Sudoku and compare against the ‘official’ solver:

Hardest

See… Just 3.5s! Doubly faster than the other one… Yo Yoo Yooo!

But, and there’s always a but, SBFA is not all that great for Sudokus that can be solved logically! This is the second example:

Solving with Logic

Solving with SBFA and GUI onscreen

Solving with SBFA and GUI minimized

Logic needs 4.5s to solve this Sudoku but SBFA takes a whopping 2.5 minutes (with GUI onscreen) or 32s (with GUI minimized). Of course, you are more interested in running the bare-bones code and mine takes only 2.5s compared to just 1.5s by the ‘official’ solver. Sad smile

Solving with bare SBFA

But why would you run the bare-bones code and miss all this fun:

Brute Force vs. Logic

So go get the new, improved and smart solver! Smile

SS v7.0

No comments:

Post a Comment