How to solve hard sudoku. Mathematicians came up with a formula for solving Sudoku

The Sudoku field is a table of 9x9 cells. A number from 1 to 9 is entered in each cell. The goal of the game is to arrange the numbers in such a way that there are no repetitions in each row, column and each 3x3 block. In other words, each column, row, and block must contain all the numbers from 1 to 9.

To solve the problem, candidates can be written in empty cells. For example, consider a cell in the 2nd column of the 4th row: in the column in which it is located, there are already numbers 7 and 8, in the row - numbers 1, 6, 9 and 4, in the block - 1, 2, 8 and 9 Therefore, we cross out 1, 2, 4, 6, 7, 8, 9 from the candidates in this cell, and we are left with only two possible candidates - 3 and 5.

Similarly, we consider possible candidates for other cells and get the following table:

Candidates are more interesting to deal with and different logical methods can be applied. Next, we will look at some of them.

Loners

The method consists in finding singles in the table, i.e. cells in which only one digit is possible and no other. We write this number in this cell and exclude it from other cells of this row, column and block. For example: in this table there are three "loners" (they are highlighted in yellow).

hidden loners

If there are several candidates in a cell, but one of them is not found in any other cell of a given row (column or block), then such a candidate is called a “hidden loner”. In the following example, candidate "4" in the green block is only found in the center cell. So, in this cell there will definitely be “4”. We enter "4" in this cell and cross it out from other cells of the 2nd column and 5th row. Similarly, in the yellow column, the candidate "2" occurs once, therefore, we enter "2" in this cell and exclude "2" from the cells of the 7th row and the corresponding block.

The previous two methods are the only methods that uniquely determine the contents of a cell. The following methods only allow you to reduce the number of candidates in the cells, which will sooner or later lead to loners or hidden loners.

Locked Candidate

There are times when a candidate within a block is in only one row (or one column). Due to the fact that one of these cells will necessarily contain this candidate, this candidate can be excluded from all other cells of this row (column).

In the example below, the center block contains candidate "2" only in the center column (yellow cells). So one of those two cells must definitely be "2", and no other cells in that row outside of this block can be "2". Therefore, "2" can be excluded as a candidate from other cells in this column (cells in green).

Open Pairs

If two cells in a group (row, column, block) contain an identical pair of candidates and nothing else, then no other cells in this group can have the value of this pair. These 2 candidates can be excluded from other cells in the group. In the example below, candidates "1" and "5" in columns eight and nine form an Open Pair within the block (yellow cells). Therefore, since one of these cells must be "1" and the other must be "5", candidates "1" and "5" are excluded from all other cells of this block (green cells).

The same can be formulated for 3 and 4 candidates, only 3 and 4 cells are already participating, respectively. Open triples: from the green cells, we exclude the values ​​of the yellow cells.

Open fours: from the green cells, we exclude the values ​​of the yellow cells.

hidden couples

If two cells in a group (row, column, block) contain candidates, among which there is an identical pair that does not occur in any other cell of this block, then no other cells of this group can have the value of this pair. Therefore, all other candidates of these two cells can be excluded. In the example below, candidates "7" and "5" in the central column are only in yellow cells, which means that all other candidates from these cells can be excluded.

Similarly, you can look for hidden triples and fours.

x-wing

If a value has only two possible locations in a row (column), then it must be assigned to one of those cells. If there is one more row (column), where the same candidate can also be in only two cells and the columns (rows) of these cells are the same, then no other cell of these columns (rows) can contain this number. Consider an example:

In the 4th and 5th lines, the number "2" can only be in two yellow cells, and these cells are in the same columns. Therefore, the number "2" can be written in only two ways: 1) if "2" is written in the 5th column of the 4th row, then "2" must be excluded from the yellow cells and then in the 5th row the position "2" is uniquely determined by the 7th column.

2) if “2” is written in the 7th column of the 4th row, then “2” must be excluded from the yellow cells and then in the 5th row the position “2” is uniquely determined by the 5th column.

Therefore, the 5th and 7th columns will necessarily have the number "2" either in the 4th row or in the 5th. Then the number "2" can be excluded from other cells of these columns (green cells).

"Swordfish" (Swordfish)

This method is a variation of the .

It follows from the rules of the puzzle that if a candidate is in three rows and only in three columns, then in other rows this candidate in these columns can be excluded.

Algorithm:

• We are looking for lines in which the candidate occurs no more than three times, but at the same time it belongs to exactly three columns.
• We exclude the candidate from these three columns from other rows.

The same logic applies in the case of three columns, where the candidate is limited to three rows.

Consider an example. In three lines (3rd, 5th and 7th) candidate "5" occurs no more than three times (cells are highlighted in yellow). However, they belong to only three columns: 3rd, 4th and 7th. According to the “Swordfish” method, candidate “5” can be excluded from other cells of these columns (green cells).

In the example below, the Swordfish method is also applied, but for the case of three columns. We exclude the candidate "1" from the green cells.

"X-wing" and "Swordfish" can be generalized to four rows and four columns. This method will be called "Medusa".

Colors

There are situations when a candidate occurs only twice in a group (in a row, column or block). Then the desired number will definitely be in one of them. The strategy for the Colors method is to view this relationship using two colors, such as yellow and green. In this case, the solution can be in the cells of only one color.

We select all interconnected chains and make a decision:

• If some unshaded candidate has two differently colored neighbors in a group (row, column, or block), then it can be excluded.
• If there are two identical colors in a group (row, column or block), then this color is false. A candidate from all cells of this color can be excluded.

In the following example, apply the "Colors" method to cells with candidate "9". We start coloring from the cell in the upper left block (2nd row, 2nd column), paint it yellow. In its block, it has only one neighbor with "9", let's paint it green. She also has only one neighbor in the column, we paint over it in green.

Similarly, we work with the rest of the cells containing the number "9". We get:

Candidate "9" can be either only in all yellow cells, or in all green. In the right middle block, two cells of the same color met, therefore, the green color is incorrect, since this block produces two "9s", which is unacceptable. We exclude, "9" from all green cells.

Another example of the "Colors" method. Let's mark paired cells for the candidate "6".

The cell with "6" in the upper central block (highlighted in lilac) has two multi-colored candidates:

"6" will necessarily be in either a yellow or green cell, therefore, "6" can be excluded from this lilac cell.

The first thing that should be determined in the methodology of problem solving is the question of actually understanding what we achieve and can achieve in terms of problem solving. Understanding is usually thought of as something that goes without saying, and we lose sight of the fact that understanding has a definite starting point of understanding, only in relation to which we can say that understanding really takes place from a specific moment we have determined. Sudoku here, in our consideration, is convenient in that it allows, using its example, to some extent to model the issues of understanding and solving problems. However, we will start with several other and no less important examples than Sudoku.

A physicist studying special relativity might talk about Einstein's "crystal clear" propositions. I came across this phrase on one of the sites on the Internet. But where does this understanding of "crystal clarity" begin? It begins with the assimilation of the mathematical notation of postulates, from which all multi-level mathematical constructions of SRT can be built according to known and understandable rules. But what the physicist, like me, does not understand is why the postulates of SRT work in this way and not otherwise.

First of all, the vast majority of those discussing this doctrine do not understand what exactly lies in the postulate of the constancy of the speed of light in the translation from its mathematical application to reality. And this postulate implies the constancy of the speed of light in all conceivable and inconceivable senses. The speed of light is constant relative to any resting and moving objects at the same time. The speed of the light beam, according to the postulate, is constant even with respect to the oncoming, transverse and receding light beam. And, at the same time, in reality we only have measurements that are indirectly related to the speed of light, interpreted as its constancy.

Newton's laws for a physicist and even for those who simply study physics are so familiar that they seem so understandable as something taken for granted and it cannot be otherwise. But, say, the application of the law of universal gravitation begins with its mathematical notation, according to which even the trajectories of space objects and the characteristics of orbits can be calculated. But why these laws work in this way and not otherwise - we do not have such an understanding.

Likewise with Sudoku. On the Internet, you can find repeatedly repeated descriptions of "basic" ways to solve Sudoku problems. If you remember these rules, then you can understand how this or that Sudoku problem is solved by applying the "basic" rules. But I have a question: do we understand why these "basic" methods work in this way and not otherwise.

So we move on to the next key point in problem solving methodology. Understanding is possible only on the basis of some model that provides a basis for this understanding and the ability to perform some natural or thought experiment. Without this, we can only have rules for applying the learned starting points: the postulates of SRT, Newton's laws, or "basic" ways in Sudoku.

We do not and in principle cannot have models that satisfy the postulate of the unrestricted constancy of the speed of light. We do not, but unprovable models consistent with Newton's laws can be invented. And there are such "Newtonian" models, but they somehow do not impress with productive possibilities for conducting a full-scale or thought experiment. But Sudoku provides us with opportunities that we can use both to understand the actual problems of Sudoku, and to illustrate modeling as a general approach to solving problems.

One possible model for Sudoku problems is the worksheet. It is created by simply filling in all the empty cells (cells) of the table specified in the task with the numbers 123456789. Then the task is reduced to the sequential removal of all extra digits from the cells until all the cells of the table are filled with single (exclusive) digits that satisfy the condition of the problem.

I'm creating such a worksheet in Excel. First, I select all the empty cells (cells) of the table. I press F5-"Select"-"Empty cells"-"OK". A more general way to select the desired cells: hold Ctrl and click the mouse to select these cells. Then for the selected cells I set the color to blue, size 10 (original - 12) and font Arial Narrow. This is all so that subsequent changes in the table are clearly visible. Next, I enter the numbers 123456789 into empty cells. I do it as follows: I write down and save this number in a separate cell. Then I press F2, select and copy this number with the Ctrl + C operation. Next, I go to the table cells and, sequentially bypassing all the empty cells, enter the number 123456789 into them using the Ctrl + V operation, and the worksheet is ready.

Extra numbers, which will be discussed later, I delete as follows. With the operation Ctrl + mouse click - I select cells with an extra number. Then I press Ctrl + H and enter the number to be deleted in the upper field of the window that opens, and the lower field should be completely empty. Then it remains to click on the "Replace All" option and the extra number is removed.

Judging by the fact that I usually manage to do more advanced table processing in the usual "basic" ways than in the examples given on the Internet, the worksheet is the most simple tool in solving Sudoku problems. Moreover, many situations regarding the application of the most complex of the so-called "basic" rules simply did not arise in my worksheet.

At the same time, the worksheet is also a model on which experiments can be carried out with the subsequent identification of all the "basic" rules and various nuances of their application arising from the experiments.

So, before you is a fragment of a worksheet with nine blocks, numbered from left to right and top to bottom. In this case, we have the fourth block filled with numbers 123456789. This is our model. Outside the block, we highlighted in red the "activated" (finally defined) numbers, in this case, fours, which we intend to substitute in the table being drawn up. The blue fives are figures that have not yet been determined regarding their future role, which we will talk about later. The activated numbers assigned by us, as it were, cross out, push out, delete - in general, they displace the same numbers in the block, so they are represented there in a pale color, symbolizing the fact that these pale numbers have been deleted. I wanted to make this color even paler, but then they could become completely invisible when viewed on the Internet.

As a result, in the fourth block, in cell E5, there was one, also activated, but hidden four. "Activated" because she, in turn, can also remove extra digits if they are on her way, and "hidden" because she is among other digits. If the cell E5 is attacked by the rest, except for 4, activated numbers 12356789, then a "naked" loner will appear in E5 - 4.

Now let's remove one activated four, for example from F7. Then the four in the filled block can be already and only in cell E5 or F5, while remaining activated in row 5. If activated fives are involved in this situation, without F7=4 and F8=5, then in cells E5 and F5 there will be a naked or hidden activated pair 45.

After you have sufficiently worked out and comprehended different options with naked and hidden singles, twos, threes, etc. not only in blocks, but also in rows and columns, we can move on to another experiment. Let's create a bare pair 45, as we did before, and then connect the activated F7=4 and F8=5. As a result, the situation E5=45 will occur. Similar situations very often arise in the process of processing a worksheet. This situation means that one of these digits, in this case 4 or 5, must necessarily be in the block, row and column that includes cell E5, because in all these cases there must be two digits, not one of them.

And most importantly, we now already know how frequently occurring situations like E5=45 arise. In a similar way, we will define situations when a triple of digits appears in one cell, etc. And when we bring the degree of comprehension and perception of these situations to a state of self-evidence and simplicity, then the next step is, so to speak, a scientific understanding of situations: then we will be able to do a statistical analysis of Sudoku tables, identify patterns and use the accumulated material to solve the most complex problems .

Thus, by experimenting on the model, we get a visual and even "scientific" representation of hidden or open singles, pairs, triples, etc. If you limit yourself to operations with the described simple model, then some of your ideas will turn out to be inaccurate or even erroneous. However, as soon as you move on to solving specific problems, the inaccuracies of the initial ideas will quickly come to light, but the models on which the experiments were carried out will have to be rethought and refined. This is the inevitable path of hypotheses and refinements in solving any problems.

I must say that hidden and open singles, as well as open pairs, triples and even fours, are common situations that arise when solving Sudoku problems with a worksheet. Hidden couples were rare. And here are the hidden triples, fours, etc. I somehow didn’t come across when processing worksheets, just like the methods for bypassing the “x-wing” and “swordfish” contours that have been repeatedly described on the Internet, in which there are “candidates” for deletion with any of the two alternative ways of bypassing contours. The meaning of these methods: if we destroy the "candidate" x1, then the exclusive candidate x2 remains and at the same time the candidate x3 is deleted, and if we destroy x2, then the exclusive x1 remains, but in this case the candidate x3 is also deleted, so in any case, x3 should be deleted , without affecting the candidates x1 and x2 for the time being. More generally, this is a special case of the situation: if two alternative ways lead to the same result, then this result can be used to solve a Sudoku problem. In this, more general, situation, I met situations, but not in the "x-wing" and "swordfish" variants, and not when solving Sudoku problems, for which knowledge of only "basic" approaches is sufficient.

The features of using a worksheet can be shown in the following non-trivial example. On one of the sudoku solver forums http://zforum.net/index.php?topic=3955.25;wap2 I came across a problem presented as one of the most difficult sudoku problems, not solvable in the usual ways, without using enumeration with assumptions about the numbers substituted in the cells . Let's show that with a working table it is possible to solve this problem without such enumeration:

On the right is the original task, on the left is the working table after the "deletion", i.e. routine operation of removing extra digits.

First, let's agree on notation. ABC4=689 means that cells A4, B4 and C4 contain the numbers 6, 8 and 9 - one or more digits per cell. It's the same with strings. Thus, B56=24 means that cells B5 and B6 contain the numbers 2 and 4. The ">" sign is a conditional action sign. Thus, D4=5>I4-37 means that due to the message D4=5, the number 37 should be placed in cell I4. The message can be explicit - "naked" - and hidden, which should be revealed. The impact of the message can be sequential (transmitted indirectly) along the chain and parallel (act directly on other cells). For example:

D3=2; D8=1>A9-1>A2-2>A3-4,G9-3; (D8=1)+(G9=3)>G8-7>G7-1>G5-5

This entry means that D3=2, but this fact needs to be revealed. D8=1 passes its action on the chain to A3 and 4 should be written to A3; at the same time, D3=2 acts directly on G9, resulting in G9-3. (D8=1)+(G9=3)>G8-7 – combined influence of factors (D8=1) and (G9=3) leads to the result G8-7. Etc.

The records may also contain a combination of type H56/68. It means that the numbers 6 and 8 are prohibited in cells H5 and H6, i.e. they should be removed from these cells.

So, we start working with the table and for a start we apply the well-manifested, noticeable condition ABC4=689. This means that in all other (except A4, B4 and C4) cells of block 4 (middle, left) and the 4th row, the numbers 6, 8 and 9 should be deleted:

Apply B56=24 in the same way. Together we have D4=5 and (after D4=5>I4-37) HI4=37, and also (after B56=24>C6-1) C6=1. Let's apply this to a worksheet:

In I89=68hidden>I56/68>H56-68: i.e. cells I8 and I9 contain a hidden pair of digits 5 and 6, which forbids these digits from being in I56, resulting in the result H56-68. We can consider this fragment in a different way, just as we did in experiments on the worksheet model: (G23=68)+(AD7=68)>I89-68; (I89=68)+(ABC4=689)>H56-68. That is, a two-way "attack" (G23=68) and (AD7=68) leads to the fact that only the numbers 6 and 8 can be in I8 and I9. Further (I89=68) is connected to the "attack" on H56 together with previous conditions, which leads to H56-68. In addition to this "attack" is connected (ABC4=689), which in this example looks redundant, however, if we worked without a working table, then the impact factor (ABC4=689) would be hidden, and it would be quite appropriate to pay attention to it specially.

Next action: I5=2>G1-2,G6-9,B6-4,B5-2.

I hope it is already clear without comments: substitute the numbers that come after the dash, you can't go wrong:

H7=9>I7-4; D6=8>D1-4,H6-6>H5-8:

Next series of actions:

D3=2; D8=1>A9-1>A2-2>A3-4,G9-3;

(D8=1)+(G9=3)>G8-7>G7-1>G5-5;

D5=9>E5-6>F5-4:

I=4>C9-4>C7-2>E9-2>EF7-35>B7-7,F89-89,

that is, as a result of "crossing out" - deleting extra digits - an open, "naked" pair 89 appears in cells F8 and F9, which, together with other results indicated in the record, we apply to the table:

H2=4>H3-1>F2-1>F1-6>A1-3>B8-3,C8-5,H1-7>I2-5>I3-3>I4-7>H4-3

Their result:

This is followed by fairly routine, obvious actions:

H1=7>C1-8>E1-5>F3-7>E2-9>E3-8,C3-9>B3-5>B2-6>C2-7>C4-6>A4-9>B4- eight;

B2=6>B9-9>A8-6>I8-8>F8-9>F9-8>I9-6;

E7=3>F7-5,E6-7>F6-3

Their result: the final solution of the problem:

One way or another, we will assume that we figured out the "basic" methods in Sudoku or in other areas of intellectual application on the basis of a model suitable for this and even learned how to apply them. But this is only part of our progress in problem solving methodology. Further, I repeat, follows not always taken into account, but an indispensable stage of bringing the previously learned methods to a state of ease of their application. Solving examples, comprehending the results and methods of this solution, rethinking this material on the basis of the accepted model, again thinking through all the options, bringing the degree of their understanding to automaticity, when the solution using the "basic" provisions becomes routine and disappears as a problem. What it gives: everyone should feel it on their own experience. And the bottom line is that when the problem situation becomes routine, the search mechanism of the intellect is directed to the development of more and more complex provisions in the field of the problems being solved.

And what is "more complex provisions"? These are just new "basic" provisions in solving the problem, the understanding of which, in turn, can also be brought to a state of simplicity if a suitable model is found for this purpose.

In the article Vasilenko S.L. "Numeric Harmony Sudoku" I find an example of a problem with 18 symmetric keys:

Regarding this task, it is stated that it can be solved using "basic" methods only up to a certain state, after reaching which it remains only to apply a simple enumeration with a trial substitution into the cells of some supposed exclusive (single, single) digits. This state (advanced a little further than in Vasilenko's example) looks like:

There is such a model. This is a kind of rotation mechanism for identified and unidentified exclusive (single) digits. In the simplest case, some triple of exclusive digits rotates in the right or left direction, passing by this group from row to row or from column to column. In general, at the same time, three groups of triples of numbers rotate in one direction. In more complex cases, three pairs of exclusive digits rotate in one direction, and a triple of singles rotate in the opposite direction. So, for example, the exclusive digits in the first three lines of the problem under consideration are rotated. And, most importantly, this kind of rotation can be seen by considering the location of the numbers in the processed worksheet. This information is enough for now, and we will understand other nuances of the rotation model in the process of solving the problem.

So, in the first (upper) three lines (1, 2 and 3) we can notice the rotation of the pairs (3+8) and (7+9), as well as (2+x1) with unknown x1 and the triple of singles (x2+4+ 1) with unknown x2. In doing so, we may find that each of x1 and x2 can be either 5 or 6.

Lines 4, 5 and 6 look at the pairs (2+4) and (1+3). There should also be a 3rd unknown pair and a triple of singles of which only one digit 5 ​​is known.

Similarly, we look at rows 789, then the triplets of columns ABC, DEF and GHI. We will write down the collected information in a symbolic and, I hope, quite understandable form:

So far, we need this information only to understand the general situation. Think it through carefully and then we can move forward further to the following table specially prepared for this:

I highlighted the alternatives with colors. Blue means "allowed" and yellow means "prohibited". If, say, allowed in A2=79 allowed A2=7, then C2=7 is forbidden. Or vice versa – allowed A2=9, forbidden C2=9. And then permissions and prohibitions are transmitted along a logical chain. This coloring is done in order to make it easier to view different alternatives. In general, this is some analogy to the "x-wing" and "swordfish" methods mentioned earlier when processing tables.

Looking at the B6=7 and, respectively, B7=9 options, we can immediately find two points that are incompatible with this option. If B7=9, then in lines 789 a synchronously rotating triple occurs, which is unacceptable, since either only three pairs (and three singles asynchronously to them) or three triples (without singles) can rotate synchronously (in one direction). In addition, if B7=9, then after several steps of processing the worksheet in the 7th line we will find incompatibility: B7=D7=9. So we substitute the only acceptable of the two alternatives B6=9, and then the problem is solved by simple means of conventional processing without any blind enumeration:

Next, I have a ready-made example using the rotation model to solve a problem from the World Sudoku Championship, but I omit this example so as not to stretch this article too much. In addition, as it turned out, this problem has three solutions, which is poorly suited for the initial development of the digit rotation model. I also puffed a lot on Gary McGuire's 17-key problem pulled from the Internet to solve his puzzle, until, with even more annoyance, I found out that this "puzzle" has more than 9 thousand solutions.

So, willy-nilly, we have to move on to the "most difficult in the world" Sudoku problem developed by Arto Inkala, which, as you know, has a unique solution.

After entering two quite obvious exclusive numbers and processing the worksheet, the task looks like this:

The keys assigned to the original problem are highlighted in black and larger font. In order to move forward in solving this problem, we must again rely on an adequate model suitable for this purpose. This model is a kind of mechanism for rotating numbers. It has already been discussed more than once in this and previous articles, but in order to understand the further material of the article, this mechanism should be thought out and worked out in detail. Approximately as if you had worked with such a mechanism for ten years. But you will still be able to understand this material, if not from the first reading, then from the second or third, etc. Moreover, if you persist, then you will bring this "difficult to understand" material to the state of its routine and simplicity. There is nothing new in this regard: what is very difficult at first, gradually becomes not so difficult, and with further incessant elaboration, everything becomes the most obvious and does not require mental effort in its proper place, after which you can free your mental potential for further progress on the problem being solved or on other problems.

A careful analysis of the structure of Arto Incal's problem shows that the whole problem is built on the principle of three synchronously rotating pairs and a triple of asynchronously rotating pairs of singles: (x1+x2)+(x3+x4)+(x5+x6)+(x7+x8+ x9). The order of rotation can be, for example, as follows: in the first three lines 123, the first pair (x1+x2) goes from the first line of the first block to the second line of the second block, then to the third line of the third block. The second pair jumps from the second row of the first block to the third row of the second block, then, in this rotation, jumps to the first row of the third block. The third pair from the third row of the first block jumps to the first row of the second block and then, in the same direction of rotation, jumps to the second row of the third block. A trio of singles moves in a similar rotation pattern, but in the opposite direction to that of pairs. The situation with columns looks similar: if the table is mentally (or actually) rotated 90 degrees, then the rows will become columns, with the same character of movement of singles and pairs as before for rows.

Turning these rotations in our minds in relation to the Arto Incal problem, we gradually come to understand the obvious restrictions on the choice of variants of this rotation for the selected triple of rows or columns:

There should not be synchronously (in one direction) rotating triples and pairs - such triples, in contrast to the triple of singles, will be called triplets in the future;

There should not be pairs asynchronous with each other or singles asynchronous with each other;

There should not be both pairs and singles rotating in the same (for example, right) direction - this is a repetition of the previous restrictions, but it may seem more understandable.

In addition, there are other restrictions:

There must not be a single pair in the 9 rows that matches a pair in any of the columns and the same for columns and rows. This should be obvious: because the very fact that two numbers are on the same line indicates that they are in different columns.

You can also say that very rarely there are matches of pairs in different triples of rows or a similar match in triples of columns, and also there are rarely matches of triples of singles in rows and / or columns, but these are, so to speak, probabilistic patterns.

Research blocks 4,5,6.

In blocks 4-6, pairs (3+7) and (3+9) are possible. If we accept (3+9), then we get an invalid synchronous rotation of the triplet (3+7+9), so we have a pair (7+3). After substituting this pair and subsequent processing of the table by conventional means, we get:

At the same time, we can say that 5 in B6=5 can only be a loner, asynchronous (7+3), and 6 in I5=6 is a paragenerator, since it is in the same line H5=5 in the sixth block and, therefore, it cannot be alone and can only move in sync with (7+3.

and arranged the candidates for singles by the number of their appearance in this role in this table:

If we accept that the most frequent 2, 4 and 5 are singles, then according to the rules of rotation, only pairs can be combined with them: (7 + 3), (9 + 6) and (1 + 8) - a pair (1 + 9) discarded since it negates the pair (9+6). Further, after substituting these pairs and singles and further processing the table using conventional methods, we get:

Such a recalcitrant table turned out to be - it does not want to be processed to the end.

You will have to strain yourself and notice that there is a pair (7 + 4) in columns ABC and that 6 moves synchronously with 7 in these columns, therefore 6 is a pairing, so only combinations (6 + 3) are possible in column "C" of the 4th block +8 or (6+8)+3. The first of these combinations does not work, because then in the 7th block in column "B" an invalid synchronous triple will appear - a triplet (6 + 3 + 8). Well, then, after substituting the option (6 + 8) + 3 and processing the table in the usual way, we come to the successful completion of the task.

The second option: let's return to the table obtained after identifying the combination (7 + 3) + 5 in rows 456 and proceed to the study of columns ABC.

Here we can notice that the pair (2+9) cannot take place in ABC. Other combinations (2+4), (2+7), (9+4) and (9+7) give a synchronous triple - a triplet in A4+A5+A6 and B1+B2+B3, which is unacceptable. There remains one acceptable pair (7+4). Moreover, 6 and 5 move synchronously 7, which means they are steam-forming, i.e. form some pairs, but not 5 + 6.

Let's make a list of possible pairs and their combinations with singles:

The combination (6+3)+8 does not work, because otherwise, an invalid triple-triplet is formed in one column (6 + 3 + 8), which has already been discussed and which we can verify once again by checking all the options. Of the candidates for singles, the number 3 scores the most points, and the most likely of all the above combinations: (6 + 8) + 3, i.e. (C4=6 + C5=8) + C6=3, which gives:

Further, the most likely candidate for singles is either 2 or 9 (6 points each), but in any of these cases, candidate 1 (4 points) remains valid. Let's start with (5+29)+1, where 1 is asynchronous to 5, i.e. put 1 from B5=1 as an asynchronous singleton in all columns of ABC:

In block 7, column A, only options (5+9)+3 and (5+2)+3 are possible. But we better pay attention to the fact that in lines 1-3 the pairs (4 + 5) and (8 + 9) have now appeared. Their substitution leads to a quick result, i.e. to the completion of the task after the table has been processed by normal means.

Well, now, having practiced on the previous options, we can try to solve the Arto Incal problem without involving statistical estimates.

We return to the starting position again:

In blocks 4-6, pairs (3+7) and (3+9) are possible. If we accept (3 + 9), then we get an invalid synchronous rotation of the triplet (3 + 7 + 9), so for substitution in the table we have only the option (7 + 3):

5 here, as we see, is a loner, 6 is a paraformer. Valid options in ABC5: (2+1)+8, (2+1)+9, (8+1)+9, (8+1)+2, (9+1)+8, (9+1) +2. But (2+1) is asynchronous to (7+3), so there are (8+1)+9, (8+1)+2, (9+1)+8, (9+1)+2. In any case, 1 is synchronous (7 + 3) and, therefore, paragenerating. Let's substitute 1 in this capacity in the table:

The number 6 here is a paragenerator in bl. 4-6, but the conspicuous pair (6+4) is not on the list of valid pairs. Hence the quad in A4=4 is asynchronous 6:

Since D4+E4=(8+1) and according to the rotation analysis forms this pair, we get:

If cells C456=(6+3)+8, then B789=683, i.e. we get a synchronous triple-triplet, so we are left with the option (6+8)+3 and the result of its substitution:

B2=3 is single here, C1=5 (asynchronous 3) is a pairing, A2=8 is also a pairing. B3=7 can be both synchronous and asynchronous. Now we can prove ourselves in more complex tricks. With a trained eye (or at least when checking on a computer), we see that for any status B3=7 - synchronous or asynchronous - we get the same result A1=1. Therefore, we can substitute this value into A1 and then complete our, or rather Arto Incala, task by more usual simple means:

One way or another, we were able to consider and even illustrate three general approaches to solving problems: determine the point of understanding the problem (not a hypothetical or blindly declared, but a real moment, starting from which we can talk about understanding the problem), choose a model that allows us to realize understanding through a natural or mental experiment and - thirdly - to bring the degree of understanding and perception of the results achieved in this case to a state of self-evidence and simplicity. There is also a fourth approach, which I personally use.

Each person has states when the intellectual tasks and problems facing him are solved more easily than is usually the case. These states are quite reproducible. To do this, you need to master the technique of turning off thoughts. At first, at least for a fraction of a second, then, more and more stretching this disconnecting moment. I can’t tell further, or rather recommend, something in this regard, because the duration of the application of this method is a purely personal matter. But I resort to this method sometimes for a long time, when a problem arises in front of me, to which I do not see options for how it can be approached and solved. As a result, sooner or later, a suitable prototype of the model emerges from the storerooms of memory, which clarifies the essence of what needs to be resolved.

I solved the Incal problem in several ways, including those described in previous articles. And always in one way or another I used this fourth approach with switching off and subsequent concentration of mental efforts. I got the fastest solution to the problem by simple enumeration - what is called the "poke method" - however, using only "long" options: those that could quickly lead to a positive or negative result. Other options took more time from me, because most of the time was spent on at least a rough development of the technology for applying these options.

A good option is also in the spirit of the fourth approach: tune in to solving Sudoku problems, substituting only a single digit per cell in the process of solving the problem. That is, most of the task and its data are "scrolled" in the mind. This is the main part of the process of intellectual problem solving, and this skill should be trained in order to increase your ability to solve problems. For example, I am not a professional Sudoku solver. I have other tasks. But, nevertheless, I want to set myself the following goal: to acquire the ability to solve Sudoku problems of increased complexity, without a worksheet and without resorting to substituting more than one number into one empty cell. In this case, any way to solve Sudoku is allowed, including a simple enumeration of options.

It is no coincidence that I recall the enumeration of options here. Any approach to solving Sudoku problems involves a set of certain methods in its arsenal, including one or another type of enumeration. Moreover, any of the methods used in Sudoku in particular or in solving any other problems has its own area of ​​​​its effective application. So, when solving relatively simple Sudoku problems, the most effective are the simple "basic" methods described in numerous articles on this topic on the Internet, and the more complex "rotation method" is often useless here, because it only complicates the course of a simple solution and at the same time what -does not provide new information that appears in the course of solving the problem. But in the most difficult cases, like Arto Incal's problem, the "rotation method" can play a key role.

Sudoku in my articles is just an illustrative example of approaches to problem solving. Among the problems I have solved, there are also an order of magnitude more difficult than Sudoku. For example, computer models of boilers and turbines located on our website. I wouldn't mind talking about them either. But for the time being, I have chosen Sudoku in order to show my young fellow citizens in a rather visual way the possible ways and stages of moving towards the ultimate goal of the problems being solved.

That's all for today.

VKontakte Facebook Odnoklassniki

For those who like to solve Sudoku puzzles on their own and slowly, a formula that allows you to quickly calculate answers may seem like an admission of weakness or cheating.

But for those who find Sudoku too hard to solve, this can be literally the perfect solution.

Two researchers have developed a mathematical algorithm that allows you to solve Sudoku very quickly, without guesswork or backtracking.

Complex network researchers Zoltan Torozhkai and Maria Erksi-Ravaz of the University of Notre Dame were also able to explain why some Sudoku puzzles are more difficult than others. The only downside is that you need a PhD in Mathematics to understand what they offer.

Can you solve this puzzle? Created by mathematician Arto Incala, it is claimed to be the hardest Sudoku in the world. Photo from nature.com

Torozhkay and Erksi-Rawaz began to analyze Sudoku as part of their research into optimization theory and computational complexity. They say that most sudoku enthusiasts use a brute-force approach based on the guessing technique to solve these problems. Thus, Sudoku lovers arm themselves with a pencil and try all possible combinations of numbers until the correct answer is found. This method will inevitably lead to success, but it is laborious and time consuming.

Instead, Torozhkai and Erksi-Ravaz proposed a universal analog algorithm that is absolutely deterministic (does not use guessing or enumeration) and always finds the correct solution to the problem, and quite quickly.

The researchers used a "deterministic analog solver" to complete this sudoku. Photo from nature.com

The researchers also found that the time it takes to solve a puzzle using their analog algorithm correlates with the degree of difficulty of the task, as judged by the person. This inspired them to develop a ranking scale for the difficulty of a puzzle or problem.

They created a scale from 1 to 4, where 1 is "easy", 2 is "average", 3 is "difficult", 4 is "very difficult". A puzzle with a rating of 2 takes on average 10 times longer to solve than a puzzle with a rating of 1. According to this system, the hardest puzzle known so far has a rating of 3.6; more complex Sudoku puzzles are not yet known.

The theory starts with a probability mapping for each individual square. Photo from nature.com

“I wasn't interested in Sudoku until we started working on a more general satisfiability class of Boolean problems,” says Torozhkay. - Since sudoku is part of this class, the Latin square of the 9th order turned out to be a good field for us to test, so I got to know them. I and many researchers who study such problems are fascinated by the question of how far we humans can go in solving Sudoku, deterministically, without busting, which is a choice at random, and if the guess is not correct, you need to go back a step or several steps. and start over. Our analog decision model is deterministic: there is no random choice or recurrence in dynamics.”

Chaos Theory: The degree of complexity of puzzles is shown here as chaotic dynamics. Photo from nature.com

Torozhkai and Erksi-Ravaz believe that their analog algorithm has the potential to be applied to a wide variety of problems in industry, computer science, and computational biology.

The research experience also made Torozhkay a big fan of Sudoku.

“My wife and I have several Sudoku apps on our iPhones and we must have played thousands of times by now, competing in less time on each level,” he says. - She often intuitively sees combinations of patterns that I do not notice. I have to take them out. It becomes impossible for me to solve many of the puzzles that our scale categorizes as difficult or very difficult without writing the probabilities in pencil.”

The Torozhkay and Erksi-Ravaz methodology was first published in Nature Physics and later in Nature Scientific Reports.

Use numbers from 1 to 9

Sudoku is played on a 9 by 9 grid, with a total of 81 grids. Inside the playing field are 9 "squares" (consisting of 3 x 3 cells). Each horizontal row, vertical column and square (9 cells each) must be filled with the numbers 1-9, without repeating any numbers in the row, column or square. Does it sound complicated? As you can see from the image below, each Sudoku playing field has several cells that are already filled. The more cells are initially filled, the easier the game. The fewer cells are initially filled, the more difficult the game.

Don't repeat any numbers

As you can see, the top left square (circled in blue) has already filled 7 of the 9 cells. The only numbers that are missing from this square are the numbers 5 and 6. By seeing which numbers are missing from each square, row, or column, we can use the process of elimination and deductive reasoning to decide which numbers should be in each cell.

For example, in the upper left square, we know that to complete the square we need to add the numbers 5 and 6, but looking at the adjacent rows and squares, we still cannot clearly determine which number to add to which cell. This means that we should now skip the top left square for now and instead try to fill in the gaps in some other places on the playing field.

No need to guess

Sudoku is a logic game, so there is no need to guess. If you don't know what number to put in a certain cell, keep scanning other areas of the playing field until you see the option to insert the desired number. But don't try to "force" anything - Sudoku rewards patience, understanding and solving different combinations, not blind luck or guesswork.

Use the elimination method

What do we do when we use the "elimination method" in a Sudoku game? Here is an example. In this Sudoku grid (shown below), only a few numbers are missing in the left vertical column (circled in blue): 1, 5, and 6.

One way to figure out what numbers can fit in each cell is to use the "elimination method" by checking what other numbers are already in each square, since the numbers 1-9 are not allowed to be duplicated in each square, row, or column.

In this case, we can quickly notice that there is already a number 1 in the top left and center left squares (the number 1s are circled in red). This means that there is only one place in the leftmost column where the number 1 can be inserted (circled in green). This is how the elimination method works in Sudoku - you find out which cells are free, which numbers are missing, and then eliminate the numbers that are already present in the square, columns and rows. Accordingly, fill in the empty cells with the missing numbers.

The rules of Sudoku are relatively simple - but the game is extraordinarily varied, with millions of possible number combinations and a wide range of difficulty levels. But it's all based on the simple principles of using the numbers 1-9, filling in the gaps based on deductive thinking, and never repeating numbers in every square, row, or column.

• tutorial

1. Basics

Most of us hackers know what sudoku is. I will not talk about the rules, but immediately move on to the methods.
To solve a puzzle, no matter how complex or simple, cells that are obvious to fill are initially searched for.

1.1 "The Last Hero"

Consider the seventh square. Only four free cells, so something can be quickly filled.
"8 " on the D3 blocks padding H3 and J3; similar " 8 " on the G5 closes G1 and G2
With a clear conscience we put " 8 " on the H1

1.2 "Last Hero" in a row

After viewing the squares for obvious solutions, move on to the columns and rows.
Consider " 4 " on the field. It is clear that it will be somewhere in the line A .
We have " 4 " on the G3 that covers A3, there is " 4 " on the F7, cleaning A7. And one more " 4 " in the second square prohibits its repetition on A4 and A6.
"The Last Hero" for our " 4 " This A2

1.3 "No Choice"

Sometimes there are multiple reasons for a particular location. " 4 " in J8 would be a great example.
Blue the arrows indicate that this is the last possible number squared. Red and blue the arrows give us the last number in the column 8 . Greens the arrows give the last possible number in the line J.
As you can see, we have no choice but to put this " 4 "in place.

1.4 "And who, if not me?"

Filling in numbers is easier to do using the methods described above. However, checking the number as the last possible value also yields results. The method should be used when it seems that all the numbers are there, but something is missing.
"5 " in B1 is set based on the fact that all numbers from " 1 " before " 9 ", Besides " 5 " is in the row, column and square (marked in green).

In jargon it is " naked loner". If you fill in the field with possible values ​​​​(candidates), then in the cell such a number will be the only possible one. Developing this technique, you can search for " hidden loners" - numbers unique for a particular row, column or square.

2. "Naked Mile"

2.1 Naked couples

""Naked" couple" - a set of two candidates located in two cells belonging to one common block: row, column, square.
It is clear that the correct solutions of the puzzle will be only in these cells and only with these values, while all other candidates from the general block can be removed.


In this example, there are several "naked pairs".
red in line BUT cells are highlighted A2 and A3, both containing " 1 " and " 6 ". I don't know exactly how they are located here yet, but I can safely remove all the others " 1 " and " 6 " from string A(marked in yellow). Also A2 and A3 belong to a common square, so we remove " 1 " from C1.

2.2 "Threesome"

"Naked Threes"- a complicated version of "naked couples".
Any group of three cells in one block containing all in all three candidates is "naked trio". When such a group is found, these three candidates can be removed from other cells of the block.

Candidate combinations for "naked trio" may be like this:

// three numbers in three cells.
// any combinations.
// any combinations.

In this example, everything is pretty obvious. In the fifth square of the cell E4, E5, E6 contain [ 5,8,9 ], [5,8 ], [5,9 ] respectively. It turns out that in general these three cells have [ 5,8,9 ], and only these numbers can be there. This allows us to remove them from other block candidates. This trick gives us the solution " 3 " for cell E7.

2.3 "Fab Four"

"Naked Four" a very rare occurrence, especially in its full form, and yet produces results when detected. The solution logic is the same as "naked triplets".

In the above example, in the first square of the cell A1, B1, B2 and C1 generally contain [ 1,5,6,8 ], so these numbers will occupy only those cells and no others. We remove the candidates highlighted in yellow.

3. "Everything hidden becomes clear"

3.1 Hidden pairs

A great way to open the field is to search hidden pairs. This method allows you to remove unnecessary candidates from the cell and give rise to more interesting strategies.

In this puzzle we see that 6 and 7 is in the first and second squares. Besides 6 and 7 is in the column 7 . Combining these conditions, we can assert that in the cells A8 and A9 there will be only these values ​​and we remove all other candidates.


More interesting and complex example hidden pairs. The pair [ 2,4 ] in D3 and E3, cleaning 3 , 5 , 6 , 7 from these cells. Highlighted in red are two hidden pairs consisting of [ 3,7 ]. On the one hand, they are unique for two cells in 7 column, on the other hand - for a row E. Candidates highlighted in yellow are removed.

3.1 Hidden triplets

We can develop hidden couples before hidden triplets or even hidden fours. The Hidden Three consists of three pairs of numbers located in one block. Such as, and. However, as in the case with "naked triplets", each of the three cells does not have to contain three numbers. will work Total three numbers in three cells. For example , , . Hidden triplets will be masked by other candidates in the cells, so first you need to make sure that troika applicable to a specific block.


In this complex example, there are two hidden triplets. The first, marked in red, in the column BUT. Cell A4 contains [ 2,5,6 ], A7 - [2,6 ] and cell A9 -[2,5 ]. These three cells are the only ones where there can be 2 , 5 or 6, so they will be the only ones there. Therefore, we remove unnecessary candidates.

Second, in a column 9 . [4,7,8 ] are unique to cells B9, C9 and F9. Using the same logic, we remove candidates.

3.1 Hidden fours

Perfect example hidden fours. [1,4,6,9 ] in the fifth square can only be in four cells D4, D6, F4, F6. Following our logic, we remove all other candidates (marked in yellow).

4. "Non-rubber"

If any of the numbers appear twice or thrice in the same block (row, column, square), then we can remove that number from the conjugate block. There are four types of pairing:

1. Pair or Three in a square - if they are located in one line, then you can remove all other similar values ​​​​from the corresponding line.
2. Pair or Three in a square - if they are located in one column, then you can remove all other similar values ​​​​from the corresponding column.
3. Pair or Three in a row - if they are located in the same square, then you can remove all other similar values ​​​​from the corresponding square.
4. Pair or Three in a column - if they are located in the same square, then you can remove all other similar values ​​\u200b\u200bfrom the corresponding square.

4.1 Pointing pairs, triplets

Let me show you this puzzle as an example. In the third square 3 "is only in B7 and B9. Following the statement №1 , we remove candidates from B1, B2, B3. Likewise, " 2 " from the eighth square removes a possible value from G2.


Special puzzle. Very difficult to solve, but if you look closely, you can see a few pointing pairs. It is clear that it is not always necessary to find them all in order to advance in the solution, but each such find makes our task easier.

4.2 Reducing the irreducible

This strategy involves carefully parsing and comparing rows and columns with the contents of the squares (rules №3 , №4 ).
Consider the line BUT. "2 "are possible only in A4 and A5. following the rule №3 , remove " 2 " them B5, C4, C5.


Let's continue to solve the puzzle. We have a single location 4 "within one square in 8 column. According to the rule №4 , we remove unnecessary candidates and, in addition, we obtain the solution " 2 " for C7.