The New Sudoku Players' Forum

[Maq777]

It is about How does the degree of complexity grow as the Problem grows?

Let's use the Sudoku puzzle as an example and limit the study to the square Sudoku family, so as not to get too confused.

We have an n that indicates the base of the sudoku puzzle and that can vary from one to one, so for the first problem we will use n = 1.

TRIVIAL CASE (n = 1)
To determine the sudoku grid we will do
n * n = 1 * 1 = 1
In such a way that the first sudoku problem that I can pose is the one that uses:
1 row, 1 column, 1 region and only 1 digit
The only problem I can ask you is to give you an empty box and the only solution is to fill it with a 1
In summary for the case of n = 1 we have
n = 1, Solution space = 1, Problem space = 1


Now let's go one step further and take n = 2

SHI-DOKU CASE (n = 2)
To determine the sudoku grid we will do
n * n = 2 * 2 = 4
In such a way that for this case the sudoku problem that I can pose is the one that uses:
4 rows, 4 columns, 4 regions and 4 digits
Now the number of possible solutions are 288 and the number of problems you can pose are 13,579,680

Now let's go one step further and take n = 3

TYPICAL SUDOKU CASE (n = 3)
To determine the sudoku grid we will do
n * n = 3 * 3 = 9
In such a way that for this case the sudoku problem that I can pose is the one that uses:
9 rows, 9 columns, 9 regions and 9 digits (This is the game that appears in all newspapers)
Now the number of possible solutions is 6,670,903,752,021,072,936,960 and the number of problems you can pose has not yet been calculated for sure.


But let's go one step further and take n = 4

EXTENDED CASE (n = 4)
To determine the sudoku grid we will do
n * n = 4 * 4 = 16
In such a way that for this case the sudoku problem that I can pose is the one that uses:
16 rows, 16 columns, 16 regions and 16 digits
Now the number of possible solutions is estimated at 5.9584 × 10 ^ 98 and the number of possible problems is simply not known

Clarifying then some concepts:

.- Brute force is the "Algorithm for Excellence" to solve problems in which the space of solutions is known, this is because, you can always find the solution to the problem by going through the space of solutions until you find the right one.

.- In Sudoku questions for example for n = 10, we would already be dealing with a grid or matrix of 100x100 numbers, in such a way that I cannot even think of calculating the space of solutions that a problem of this degree will have, so that a "brute force" algorithm will be quite useless in practice. However, if I give you a possible solution, an algorithm will only have to check a list of 10,000 numbers, to see if taken from 100 to 100 they are never repeated in rows, columns or regions.

.- And although it seems a waste of time to dedicate so much reasoning and mathematical study, along with quite a few hours of computational calculation to something as trivial as a Sudoku puzzle, all NP Complete problems can be reduce to only ONE, and therefore the algorithm that solves correctly and in a time equal to or less than the simple verification of a Sudoku problem can then be adapted to solve more relevant problems.

.- To finish how it is about How does the degree of complexity grow as the Problem grows?
In the sudoku example, the problems grow polynomially in “n squared”, however the solution space goes from 1 to 288 and then to 6,670,903,752,021,072,936,960 and then it is estimated to be 5.9584 × 10 ^ 98, which It seems to me that it is an increase rather than an exponential one, so a brute force algorithm becomes obsolete and inoperative very quickly, for very low values ​​of n.

As you can see, it is not trying to start from scratch with an already impossible plane problem in terms of time or total atoms in the universe in order to store results, but to study all problems together and try to understand not only a particular problem but to the whole family of problems of the same kind.

[Faina]