The first thing that should be decided on in the methodology of problem solving is the question of actually understanding what we achieve and can achieve in matters of problem solving. Understanding is usually taken for granted, and we lose sight of the point that understanding has a certain starting point of understanding, only in relation to which we can say that understanding actually takes place from a specific moment we have determined. Sudoku here, in our consideration, is convenient in that it allows us to model, to some extent, issues of understanding and problem solving. However, we will start with slightly different and no less important examples than Sudoku.
Physicist studying special theory relativity, can speak of 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-story mathematical structures 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 particular way and not otherwise.
First of all, the overwhelming majority of those discussing this doctrine do not understand what exactly is in the postulate of the constancy of the speed of light when translated 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 objects at rest and moving at the same time. The speed of a 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 indirectly related to the speed of light, interpreted as its constancy.
Newton's laws are so familiar to a physicist and even to those simply studying physics that they seem so understandable, as something self-evident and it cannot be otherwise. But, say, the application of the law of universal gravitation begins with its mathematical notation, from which even the trajectories of space objects and the characteristics of orbits can be calculated. But we don’t have such an understanding of why these laws work this way and not otherwise.
Same with Sudoku. On the Internet you can find repeated descriptions of “basic” ways to solve Sudoku problems. If you remember these rules, 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 this way and not otherwise.
So we move on to the next one key position in problem solving methodology. Understanding is possible only on the basis of some kind of model that provides the basis for this understanding and the opportunity to carry out some natural or mental experiment. Without this, we can only have rules for applying memorized starting points: the postulates of SRT, Newton's laws or "basic" methods in Sudoku.
We do not have and, in principle, cannot have models that satisfy the postulate of the unlimited constancy of the speed of light. We do not have, but unprovable models that are consistent with Newton's laws can be invented. And there are such “Newtonian” models, but they somehow do not impress with their productive capabilities for conducting a full-scale or thought experiment. But Sudoku provides us with opportunities that we can use both to understand Sudoku problems themselves and to illustrate modeling as a general approach to problem solving.
One possible model for Sudoku problems is a worksheet. It is created by simply filling all the empty cells (cells) of the table specified in the problem with the numbers 123456789. Next, the task is reduced to sequentially removing all extra digits from the cells until all the cells of the table are filled with single (exclusive) digits that satisfy the conditions of the problem.
I create such a worksheet in Excel. First, I select all the empty cells (cells) of the table. I press F5 - "Select" - "Blank cells" - "OK". More general method selecting the required cells: hold Ctrl and click the mouse to select these cells. Then for the selected cells I set blue, size 10 (original 12) and Arial Narrow font. This is all so that subsequent changes in the table are clearly visible. Next, I enter the numbers 123456789 into the empty cells. I do this as follows: I write down and save this number in a separate cell. Then I press F2, select and copy this number using Ctrl+C. Next, I go to the table cells and, sequentially going through all the empty cells, enter the number 123456789 into them using the Ctrl+V operation, and the worksheet is ready.
I remove extra numbers, which will be discussed later, as follows. Using the Ctrl+click operation, 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. Next, just click on the “Replace All” option and the extra digit will be deleted.
Based on the fact that I can usually do more advanced table processing in the usual "basic" ways than in the examples given online, the worksheet is the most simple tool in solving Sudoku problems. Moreover, many situations concerning 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 you can conduct experiments with the subsequent identification of all the “basic” rules and various nuances of their application arising from the experiments.
So, here is a fragment of a worksheet with nine blocks, numbered from left to right and top to bottom. IN in this case We have the fourth block filled with numbers 123456789. This is our model. Outside the block, we have highlighted in red the “activated” (finally determined) numbers, in this case the fours, which we intend to insert into the table being drawn up. Blue fives are numbers that have not yet been determined regarding their future role, which we will talk about later. The activated numbers we have assigned are, as it were, crossed out, pushed out, deleted - in general, they displace the numbers of the same name in the block, so they are represented there in a pale color, symbolizing the fact that these pale numbers are deleted. I wanted to make this color even paler, but then they might 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 it, in turn, can also remove unnecessary digits if any appear in its path, and “hidden” because it is located among other digits. If cell E5 is attacked by the remaining, except for 4, activated numbers 12356789, then a “naked” singleton will appear in E5 - 4.
Now let's remove one activated four, for example from F7. Then the four in the filled block may end up narrower and only in cell E5 or F5, while remaining activated in line 5. If activated fives are brought into this situation, without F7=4 and F8=5, then a bare or hidden activated pair 45.
After you have sufficiently practiced and comprehended different options with naked and hidden singles, doubles, triples, 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 was done before, and then connect the activated F7=4 and F8=5. As a result, the situation E5=45 will arise. Situations like this very often arise during the processing of a worksheet. This situation means that one of these digits, in this case 4 or 5, must be in the block, row and column that includes cell E5, because in all these cases there must be two digits, not just 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 three digits appear in one cell, etc. And when we bring the degree of understanding 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 the situations: we will then 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, triplets, etc. If you limit yourself only 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 become apparent, and the models on which the experiments were carried out will have to be rethought and refined. This is the inevitable path of hypotheses and clarifications in solving any problems.
It must be said that hidden and open singles, as well as open pairs, triplets and even fours, are common situations that arise when solving Sudoku problems with a worksheet. Hidden pairings were rare. But here are the hidden threes, fours, etc. I somehow didn’t come across when processing worksheets, just like the “x-wing” and “swordfish” methods for bypassing contours, which were repeatedly described on the Internet, in which “candidates” for deletion arise in any of the two alternative methods 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 candidates x1 and x2 for now. In more in general terms, 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. I have encountered situations in this more general sense, but not in the “x-wing” and “swordfish” variants, and not when solving Sudoku problems, for which knowledge of only “basic” approaches is sufficient.
Features of using the worksheet can be shown in the following non-trivial example. On one of the forums of Sudoku solvers http://zforum.net/index.php?topic=3955.25;wap2 I came across a problem presented as one of the most difficult Sudoku problems, which cannot be solved by conventional methods, without using brute force with assumptions regarding the numbers inserted into the cells . We will show that with a worksheet you can solve this problem without such an exhaustive search:
On the right is the original task, on the left is the worksheet after “crossing out”, 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. So, B56=24 means that cells B5 and B6 contain the numbers 2 and 4. The ">" sign is a sign of a conditioned action. 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 must be revealed. The impact of a message can be sequential (transmitted indirectly) along the chain or parallel (impact 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 transmits its influence to A3 along the chain and 4 should be written in A3; simultaneously D3=2 acts directly on G9, resulting in the result G9-3. (D8=1)+(G9=3)>G8-7 – the combined influence of factors (D8=1) and (G9=3) leads to the result G8-7. Etc.
The records may also contain combinations like 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, let's start working with the table and first apply the well-developed, noticeable condition ABC4=689. This means that in all other (except A4, B4 and C4) cells of block 4 (middle, left) and 4th row the numbers 6, 8 and 9 must be removed:
We use B56=24 in the same way. In total 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 the worksheet:
In I89=68hidden>I56/68>H56-68: i.e. in cells I8 and I9 there is a hidden pair of digits 5 and 6, which prohibits the presence of these digits in I56, which leads to the result H56-68. We can consider this fragment differently, just as we did in the 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. Next (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 in this example looks redundant, but if we were working without a worksheet, then the impact factor (ABC4=689) would be hidden, and it would be appropriate to pay special attention to it.
Next action: I5=2>G1-2,G6-9,B6-4,B5-2.
I hope it is already clear without comments: substitute the numbers that appear after the dash, you won’t be mistaken:
H7=9>I7-4; D6=8>D1-4,H6-6>H5-8:
The following 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” - removing extra digits - an open, “naked” pair 89 appears in cells F8 and F9, which, together with other results indicated in the entry, is applied 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:
Then follow 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- 8;
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 to the problem:
One way or another, we will assume that we have figured out the “basic” methods in Sudoku or other areas of intellectual application on the basis of a suitable model for this and even learned how to use them. But this is only part of our progress in problem-solving methodology. Next, I repeat, follows the not always taken into account, but indispensable stage of bringing the previously learned methods to a state of ease of use. Solving examples, comprehending the results and methods of this solution, rethinking this material on the basis of the adopted model, again thinking through all the options, bringing the degree of their understanding to automaticity, when the solution using “basic” provisions becomes routine and disappears as a problem. What this gives: everyone should experience this. But the point is that when a problem situation becomes routine, the search mechanism of the intellect is directed towards mastering increasingly complex provisions in the area of the problems being solved.
What are “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 by Vasilenko S.L. "Number Harmony Sudoku" I find an example problem with 18 symmetrical keys:
Regarding this problem, it is argued that it can be solved using “basic” techniques only up to a certain state, after reaching which all that remains is to apply a simple search with a trial substitution of some supposed exclusive (single, single) digits into the cells. This state (advanced a little further than in Vasilenko’s example) has the form:
There is such a model. This is a kind of rotation mechanism for identified and not identified exclusive (single) numbers. In the simplest case, a certain trio of exclusive digits rotates in the right or left direction, moving this group from row to row or from column to column. In general, three groups of triples of numbers rotate in one direction. In more difficult cases, three pairs of exclusive numbers rotate in one direction, and three pairs 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 what is most important here is that this kind of rotation can be noticed by looking at the arrangement of numbers in the processed worksheet. This information is sufficient for now, and we will understand other nuances of the rotation model in the process of solving the problem.
So, in the first (top) three lines (1, 2 and 3) we can notice the rotation of pairs (3+8) and (7+9), as well as (2+x1) with an unknown x1 and a triple of singles (x2+4+ 1) with unknown x2. In doing so, we can 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 third unknown pair and a triple of singles, of which only one number, 5, is known.
Similarly, we look at rows 789, then the triples of columns ABC, DEF and GHI. We will write down the collected information in a symbolic and, I hope, quite understandable form:
For now, we only need this information to understand the general situation. Think it over carefully and then we can move forward to the following table specially prepared for this purpose:
I have highlighted alternative options with colors. Blue means "allowed" and yellow means "prohibited". If, say, A2=79 is allowed in A2=7, then C2=7 is prohibited. Or vice versa – A2=9 is allowed, C2=9 is forbidden. And then permissions and prohibitions are transmitted along a logical chain. This coloring is made to make it easier to view different alternative options. In general, this is some analogy to the previously mentioned “x-wing” and “swordfish” methods when processing tables.
Looking at option B6=7 and, accordingly, B7=9, we can immediately detect two points that are incompatible with this option. If B7=9, then in lines 789 a synchronously rotating triple appears, which is unacceptable, since either only three pairs (and three singles asynchronously with 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 an incompatibility: B7=D7=9. So we substitute the only acceptable of the two alternative options B6 = 9, and then the problem is solved by simple means normal processing without any blind search:
Next, I have ready-made example using the rotation model to solve a problem from the World Sudoku Championship, but I am omitting this example so as not to make this article too long. In addition, as it turned out, this problem has three possible solutions, which is not suitable for the initial development of the digit rotation model. I also spent a fair amount of time poring over Gary McGuire’s problem, pulled from the Internet, with 17 keys to solve his puzzle, until, with even more considerable irritation, I found out that this “puzzle” has more than 9 thousand possible solutions.
So, willy-nilly, we have to move on to the “world’s most difficult” Sudoku problem, developed by Arto Incala, which, as we know, has a unique solution.
After entering two very obvious exclusive numbers and processing the worksheet, the problem looks like this:
The keys assigned to the original task are highlighted in black and larger font. 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 through and worked out in detail. About the same 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 show persistence, 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 at first very difficult gradually becomes not so difficult, and with further continuous elaboration, everything that is most obvious and does not require mental effort falls into its proper place, after which you can free up your mental potential for further progress on the given problem being solved or regarding other problems.
Upon careful analysis of the structure of the Arto Incal problem, one can notice that it is all built on the principle of three synchronously rotating pairs and three singles rotating asynchronously to pairs: (x1+x2)+(x3+x4)+(x5+x6)+(x7+x8+ x9). The rotation order could, for example, be as follows: in the first three lines 123, the first pair (x1+x2) moves 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 line of the first block jumps into the first line of the second block and then in the same direction of rotation goes into the second line of the third block. The triple of singles moves in a similar rotation mode, but in the opposite direction to the rotation of the pairs. The situation with columns looks similar: if the table is mentally (or actually) rotated by 90 degrees, then the rows will become columns, with the same pattern of movement of singles and pairs as before for rows.
By performing these rotations in our minds in relation to the Arto Incala problem, we gradually come to an understanding of the obvious restrictions on the choice of options for this rotation for the selected triple of rows or columns:
There should not be synchronously (in the same direction) rotating triplets and pairs - such triplets, in contrast to the triplet of singles, will be called triplets in the future;
There should be no asynchronous pairs or asynchronous singles;
There should not be pairs or singles rotating in the same (for example, right) direction - this is a repetition of the previous restrictions, but maybe it will seem more understandable.
In addition, there are other restrictions:
There should not be a single pair in 9 rows that matches a pair in any of the columns, and the same applies to columns and rows. This should be obvious: because the very fact that two numbers are located on the same line indicates that they are in different columns.
We can also say that there are very rarely coincidences of pairs in different triplets of rows or a similar coincidence in triplets of columns, and also rarely coincidences of triplets of singles in rows and/or columns, but these are, so to speak, probabilistic patterns.
Study of blocks 4,5,6.
In blocks 4-6 pairs (3+7) and (3+9) are possible. If we accept (3+9), we get an unacceptable 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 using conventional means, we obtain:
At the same time, we can say that 5 in B6=5 can only be a singleton, asynchronous (7+3), and 6 in I5=6 is paragenerative, since it is in the same line H5=5 in the sixth block and, therefore, she cannot be alone and can only move synchronously with (7+3.
and arranged the candidates for singles according to the number of times they appeared in this role in this table:
If we accept that the most frequent 2, 4 and 5 are singles, then according to the rotation rules only pairs can be combined with them: (7+3), (9+6) and (1+8) - pair (1+9) discarded because it negates the pair (9+6). Further, after substituting these pairs and singles and further processing the table using conventional methods, we obtain:
This is how the table turned out to be unruly: it doesn’t want to be processed to the end.
You will have to strain yourself and notice that in the ABC columns there is a pair (7+4) and that 6 moves synchronously with 7 in these columns, therefore 6 is a paragenerator, so in column “C” of the 4th block only combinations (6+3) are possible +8 or (6+8)+3. The first of these combinations does not work, since 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 arrive at the successful completion of the task.
Second option: let's return to the table obtained after identifying the combination (7+3)+5 in rows 456 and move on to examining the ABC columns.
Here we can notice that the pair (2+9) cannot occur in ABC. Other combinations (2+4), (2+7), (9+4) and (9+7) give a synchronous 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 paragenerating, 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 triplet will be 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 probable of all the combinations given is: (6+8)+3, i.e. (C4=6 + C5=8) + C6=3, which gives:
Next, the most likely candidate for solo is either 2 or 9 (6 points each), however, in any of these cases, candidate 1 (4 points) remains valid. Let's start with (5+29)+1, where 1 is asynchronous with 5, i.e. Let's put 1 of B5=1 as an asynchronous singleton in all ABC columns:
In block 7, column A, the only possible options are (5+9)+3 and (5+2)+3. But we’d better pay attention to the fact that in lines 1-3 the pairs (4+5) and (8+9) now appear. Their substitution leads to a quick result, i.e. to complete the task after processing the table using normal means.
Well, now, having practiced on the previous options, we can try to solve the Arto Incal problem without using 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), we get an unacceptable synchronous rotation of the triplet (3+7+9), so for substitution into the table we have only the option (7+3):
5 here, as we see, is single, 6 is paraforming. 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 (7+3), so what remains is (8+1)+9, (8+1)+2, (9+1)+8, (9+1)+2. In any case, 1 is synchronous (7+3) and, therefore, paragenerative. Let's substitute 1 in this capacity into the table:
The number 6 here is a paragenerator in the block. 4-6, but the conspicuous pair (6+4) is not in the list of valid pairs. Therefore, the four in A4=4 is asynchronous 6:
Since D4+E4=(8+1) and according to rotation analysis forms this pair, we get:
If cells C456=(6+3)+8, then B789=683, i.e. we get a synchronous triplet, so we are left with the option (6+8)+3 and the result of its substitution:
B2=3 is a singleton here, C1=5 (asynchronous 3) is a paragenerator, A2=8 is also a paragenerator. B3=7 can be both synchronous and asynchronous. Now we can prove ourselves in more complex techniques. 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, using more ordinary simple means, complete our, or rather Arto Incala’s, task:
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 speculative or blindly declared one, but a real moment, starting from which we can talk about understanding the problem), choose a model that allows us to realize the understanding through a natural or thought experiment and - this is third - to bring the degree of understanding and perception of the results achieved to a state of self-evidence and simplicity. There is also a fourth approach, which I personally use.
Every person experiences states when the intellectual tasks and problems facing him are solved more easily than is usually the case. These conditions can be completely reproduced. To do this, you need to master the technique of turning off thoughts. First, at least for a fraction of a second, then, increasingly stretching this shutdown moment. I can’t talk further, or rather recommend, anything in this regard, because the duration of using this method is a purely personal matter. But I sometimes resort to this method for a long time, when I am faced with a problem that I do not see options on how to approach it and solve it. As a result, sooner or later a suitable prototype of a model emerges from the storehouses of memory, which clarifies the essence of what needs to be resolved.
I solved the Incala problem in several ways, including those described in previous articles. And I always, to one degree or another, used this fourth approach with switching off and subsequent concentration of mental efforts. I got the fastest solution to the problem by simple search - 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 me more time, because most of the time was spent on at least rough development of the technology for using these options.
A good option is also in the spirit of the fourth approach: tune in to solving Sudoku problems, substituting only a single number into a cell in the process of solving the problem. That is, most of the task and its data are “scrolled” in the mind. This is how most of the intellectual problem solving process occurs, and it is a skill that should be trained to increase your problem solving abilities. For example, I am not a professional Sudoku solver. I have other tasks. But, nevertheless, I want to set myself the following goal: to gain 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 method of solving Sudoku is allowed, including a simple enumeration of options.
It is not by chance that I recall the enumeration of options here. Any approach to solving Sudoku problems involves in its arsenal a set of certain methods, including one or another type of search. Moreover, any of the methods used in Sudoku in particular or when solving any other problems has its own area of effective application. So, when deciding regarding simple tasks Sudoku is most effective with 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 move simple solution and at the same time some new information, which manifests itself in the course of solving the problem, does not provide. 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 ones that are 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 now I chose Sudoku in order to clearly enough show my young fellow citizens the possible paths and stages of progress towards the final goal of the problems being solved.
That's all for today.
Sudoku is a very interesting puzzle. It is necessary to arrange the numbers from 1 to 9 in the field so that each row, column and block of 3 x 3 cells contains all the numbers, and at the same time they should not be repeated. Let's consider step by step instructions, how to play Sudoku, basic methods and strategy for solving.
Solution algorithm: from simple to complex
The algorithm for solving the Sudoku mind game is quite simple: you need to repeat the following steps until the problem is completely solved. Gradually move from the simplest steps to more complex ones, when the first ones no longer allow you to open a cell or exclude a candidate.
Single candidates
First of all, for a more clear explanation of how to play Sudoku, we will introduce a system for numbering blocks and cells of the field. Both cells and blocks are numbered from top to bottom and left to right.
Let's start looking at our field. First, you need to find single candidates for a place in the cell. They can be hidden or obvious. Let's consider the possible candidates for the sixth block: we see that only one of the five free cells contains a unique number, therefore, the four can be safely entered into the fourth cell. Considering this block further, we can conclude: the second cell must contain the number 8, since after eliminating the four, the eight does not appear anywhere else in the block. With the same justification we put the number 5.
Review everything carefully possible options. Looking at the central cell of the fifth block, we find that besides the number 9 there cannot be any more options - this is a clear single candidate for this cell. Nine can be crossed out from the remaining cells of this block, after which the remaining numbers can be easily entered. Using the same method, we go through the cells of other blocks.
How to detect hidden and obvious “naked pairs”
Having entered the necessary numbers in the fourth block, we return to the unfilled cells of the sixth block: it is obvious that the number 6 should be in the third cell, and 9 in the ninth.
The concept of "naked couple" is present only in the game Sudoku. The rules for their detection are as follows: if two cells of the same block, row or column contain an identical pair of candidates (and only this pair!), then the remaining cells of the group cannot have them. Let's explain this using the eighth block as an example. Having placed possible candidates in each cell, we find a clear “naked pair”. The numbers 1 and 3 are present in the second and fifth cells of this block, and in each there are only 2 candidates, therefore, they can be safely excluded from the remaining cells.
Completing the puzzle
If you have learned the lesson on how to play Sudoku and followed the instructions above step by step, then you should end up with a picture similar to this board:
Here you can find single candidates: a one in the seventh cell of the ninth block and a two in the fourth cell of the third block. Try to solve the puzzle to the end. Now compare the result with the correct solution.
Did it work? Congratulations, because this means that you have successfully learned the lessons of how to play Sudoku and learned how to solve simple puzzles. There are many varieties of this game: Sudoku different sizes, Sudoku with additional areas and additional conditions. The playing field can vary from 4 x 4 to 25 x 25 cells. You may come across a puzzle in which the numbers cannot be repeated in an additional area, for example, diagonally.
Start with simple options and gradually move on to more complex ones, because with training comes experience.
In this article we will look in detail at how to solve complex Sudoku using the example of diagonal Sudoku.
We get condition number 437, which is shown in Figure 1. And the first square immediately catches your eye, it is the most saturated with open numbers. The numbers 1, 3,4,9 are missing. But since the horizontal line a already contains three, the number three is placed on c1. We cannot accurately place the rest. So let’s look at what else we have. For example, the vertical is 4 and here the number four can only be on b4, due to the presence of a four in the fifth square and on the horizontal c. We will not put the remaining numbers for now.
All the techniques and methods that we will use further apply to solving both simple and complex Sudoku.
What do we have on horizontal b? There is not enough three here and it can only stand on b8. (In the second square it is already there and on vertical 9). And if we carefully examine the horizontal line b further, we will find that we have a hidden single - the number 9 on cell b9. Because the other candidates (these are 1 and 5) cannot stand on this cell!
What can we do next? If we consider square five. Here the numbers 3 and 5 can be either on d5 or e6. This means that we do not consider these cells for the remaining numbers. Based on this, there is only one place left for the one - cell d6.
The result of our actions is shown in Figure 2. Thanks to our analysis, row b is filled in completely. One on b5, five on b6. What gives us the right to place 3 and 5 in the fifth square!
Let's continue the analysis of the fifth square. It lacks the number 7, it is not on the main diagonals, and what is most interesting is on the vertical 4. Thanks to this very vertical, we can say for sure that the number seven in the fifth square can be either on f4 or e4. Since the horizontal lines c and d already contain seven. And she cannot stand on e5 because of vertical 4. Next, let’s turn to the main horizontals. And then the sevens are immediately placed! On i9 and f4.
What we got can be seen in Figure 3. Next, we will continue the analysis of the main diagonals. If we look at the one coming from square a1, then it lacks a two, which is placed only on h8. This diagonal also lacks 1, 8 and 9. The 1 can only be placed on a1, put it quickly! But the eight cannot stand on d4, since it is already on the horizontal d. We arrange - d4 -9, e5 -8.
But now we can completely fill the fifth and first squares! What we got is shown in Figure 4.
Pay attention to vertical 3. Here you need to place 1, 6, 7. The unit is placed only on f3, and based on this the rest are placed - e3 -7, h3-6. Next in line we have vertical 9, as its placement is simply fabulous. d9-2, g9-6, h9-8.
What if we check for open singles?! For example, the number three is safely placed on cells d2 and h5. Although further analysis of singletons does not yield anything. Then let's turn to the remaining diagonal. She is missing 6, 2, 4. The number six can only be on c7. The rest is easy to fill out.
Why is vertical 4 not set to the end? Let's fix it. s4 -8.
The result of our research is shown in Figure 5. Now let's fill the horizontal line c. s8-1, s5-9, s6-2. And this is all based on the presence of these numbers in other verticals. Based on the horizontal c, it is easy to fill the horizontal d. d1-6, d7 -4. Then the third square is quite simply filled in. But the second square has not yet been filled, although there are also only two candidates - six and seven. But they do not occur along verticals five and six, and therefore we will put them aside for now.
Having analyzed all the verticals and horizontals, we come to the conclusion that it is impossible to put a single number unambiguously. Therefore, let's move on to considering squares. Let's turn to the sixth square. 5,6,8,9 are missing here. But we can definitely put numbers 6 and 8 on cells f7 and f8. Thanks to our analysis, the entire f horizontal line is marked! f1 -9, f2 -5. And what we see here is that the fourth square is completely filled! e1-4, e2 -2.
What we got can be seen in Figure 6. Now let’s turn to square nine. Here we have one open single - number one on i7. Thanks to which we can put a one in the seventh square on g2. Eight on i2.
So today I will teach you solve sudoku.
For clarity, let's take concrete example and consider the basic rules:
Rules for solving Sudoku:
I highlighted the row and column in yellow. First rule each row and each column can contain numbers from 1 to 9, and they cannot be repeated. In short - 9 cells, 9 numbers - therefore there cannot be 2 fives, eights, etc. in the same column. Likewise for strings.
Now I have selected the squares - this is second rule. Each square can contain numbers from 1 to 9 and they are not repeated. (Same as in rows and columns). The squares are highlighted with bold lines.
From here we have general rule to solve sudoku: neither in lines, neither in columns neither in squares numbers should not be repeated.
Well, let's now try to solve it:
I've highlighted the units in green and shown the direction we're looking. Namely, we are interested in the last upper square. You can notice that there cannot be units in the 2nd and 3rd rows of this square, otherwise there will be a repetition. This means the unit is at the top:
Two is easy to find:
Now let's use the two we just found:
I hope the search algorithm has become clear, so from now on I will draw faster.
We look at the 1st square of the 3rd line (below):
Because We have 2 free cells left there, then each of them can contain one of two numbers: (1 or 6):
This means that in the column that I highlighted there can no longer be either 1 or 6 - so we put 6 in the top square.
Due to lack of time, I’ll stop here. I really hope you understand the logic. By the way, I didn’t take the simplest example, in which most likely all the solutions will not be clearly visible at once, and therefore it is better to use a pencil. We don’t know about 1 and 6 in the lower square yet, so we draw them with a pencil - similarly, 3 and 4 will be drawn in pencil in the upper square.
If we think a little more, using the rules, we will get rid of the question of where is 3 and where is 4:
Yes, by the way, if at some point you find it incomprehensible, write, I will explain in more detail. Good luck with solving Sudoku.
VKontakte Facebook Odnoklassniki
For those who like to solve Sudoku puzzles on their own and slowly, a formula that allows you to quickly calculate the answers may seem like an admission of weakness or cheating.
But for those who find solving Sudoku too much effort, this could literally be the perfect solution.
Two researchers developed mathematical algorithm, which allows you to solve Sudoku very quickly, without guessing and backtracking.
Complex network researchers Zoltan Torozkay 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? It was created by mathematician Arto Incala and is claimed to be the hardest Sudoku in the world. Photo from nature.com
Torozkay and Erksi-Ravaz began analyzing 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 guessing techniques to solve these problems. Thus, Sudoku fans 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 labor-intensive and time-consuming.
Instead, Torozkay and Erksi-Ravaz proposed a universal analog algorithm that is completely deterministic (does not use guesswork or brute force) and always finds the right decision tasks, and quite quickly.
The researchers used a "deterministic analog solver" to complete this sudoku puzzle. Photo from nature.com
The researchers also found that the time it took to solve a puzzle using their analog algorithm correlated with the difficulty level of the task as judged by humans. 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 “moderately difficult,” 3 is “difficult,” and 4 is “very difficult.” A puzzle rated 2 takes on average 10 times longer to solve than a puzzle rated 1. According to this system, the hardest puzzle known so far has a rating of 3.6; more complex tasks Sudoku is still unknown.
The theory begins by mapping the probabilities for each individual square. Photo from nature.com
"I wasn't interested in Sudoku until we started working on more general class feasibility of Boolean problems, says Torozkay. - Since Sudoku is part of this class, the 9th order Latin square turned out to be a good test field for us, which is how 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 brute force, which is a choice at random, and if the guess is wrong, we need to go back a step or several steps back and start over. Our analogue decision model is deterministic: there is no random selection or return."
Chaos Theory: The degree of difficulty of the puzzles is shown here as chaotic dynamics. Photo from nature.com
Torozkay and Erksi-Ravaz believe that their analog algorithm has the potential to be applied to the solution large quantity various tasks and problems in industry, computer science and computational biology.
The research experience also made Torozkai a big fan of Sudoku.
“My wife and I have several Sudoku apps on our iPhones, and we must have played them thousands of times by now, competing for the fastest time on each level,” he says. “She often intuitively sees combinations of patterns that I don’t notice.” I have to get them out. It becomes impossible for me to solve many of the puzzles that our scale categorizes as difficult or very difficult without writing down the probabilities in pencil.”
Torozkai and Erksi-Ravaz's methodology was first published in Nature Physics and later in Nature Scientific Reports.