4x4 complexity - estimating max solving time

radek

Hi all,

I'm quite new to writing sudoku solvers. However, I wrote nice-working 9x9 solver in C++ with STL library. It isn't something well distinguished, but works for all tested cases.

My method in 9x9 is quite simple: I declare 27 tables, each for a row, each for a column, and each for a 3x3 square. Those are containing informations about all possible digits in adequate cols, rows & squares. Besides for each cell I create a list of already tested digits. Now when I put a digit into cell, I remove it from three tables and put it into proper tested list. After all combinations are tested and wrong, I make a fallback, make some clean-up and try with a new digit.

Now I found somewhere 16x16 sudoku grids, decided to convert my program into new grid size and all tested grids are solved within 10 seconds. But one breaks the rule. It isn't to be solved within 2 days of continous work of PIV processor (and still computing).
My question is: is there something wrong in my algorithm (maybe I overlooked something) or sudoku complexity with this case and my algorithm are combining in some long-time counting?

Here's the grid:

jaap