Resolution of a sudoku

This article proposes to present, according to a synthetic and logical prospect (thus by justifying them), the whole of the techniques regularly used in the resolution of a traditional Sudoku (of dimensions 9 X 9), whatever is the level of difficultés.
Concretely, these techniques will not be presented " flat " but by order of increasing complexity, and by bringing closer these techniques between them according to their possible filiation, their common points and their differences; in addition, each one exposed in a way as visual as possible and with examples (at least one) always complete (whole grids), illustrated and will be commented on.

In practice, one can estimate that at least 99% of the sudokus proposed in the periodicals and the specialized magazines can be solved using the only techniques presented here, at least at condition of not making neither error nor omission…

Nota: according to the opinion of the majority of the " puristes" , the approach by assumption (or " backtracking" in English) is not a purely logical step (because of the need for a choice makes randomly between several assumptions); this is why this method, in spite of its undeniable effectiveness (one can rightly qualify it d'" heuristique"), is not treated here!

Example of grid of sudoku

The grid below is an example of sudoku of a rather large level of difficulty…

Initial state: to notice that the 29 initial data are written on a pale blue bottom…

… what makes it possible, in the final solution, to distinguish them from the 52 values deduced by reasoning, written on a pale yellow bottom.

Final solution of the grid presented:
on checks on the one hand that each line, each column and each paving stone of 3 X 3 boxes contains well 9 boxes in which figure one of the nine digits from 1 to 9, on the other hand that each figure appears once and only one in each line, each column and each paving stone!

L' clarification of the resolution of this sudoku is given here!

Vocabulary and general notations used

To facilitate the comprehension of the techniques of resolution of the sudokus, it is necessary to specify the vocabulary which it is advisable to use to describe the structure and the contents of a grid of sudoku.

• The lignes are called A, B, C, D, E, F, G, H and J (the " I" is avoided because, with certain font faces and in particular the standard police force used by wikipédia, one is likely to confuse it - in the explanations - with the small letter " l" ): A is the first line, J the last.

• The colonnes are called has, B, C, D, E, F, G, H, and J, from left to right.

• To indicate a box, one gives initially the line then the column: for example F (in the grid-example presented in the introduction the Fa box contained one 3) • Nine large " pavés" of a grid of sudoku 3 times 3 boxes contain; they are indicated by Xx, Xy, Xz (first line), then Yx, Yy, Yz (second line) and finally Zx, Zy and ZZ (last line). " is called; bloc" a whole of 3 contiguous and aligned paving stones. For example, block X joins together paving stones Xx, Xy and Xz, and block Z joins together the paving stones Xz, Yz and Zz.

• A figure which one can undoubtedly register in a box calls the " valeur" of this box (it can be either an initial value, or a value discovered later on, by logical deduction).

• The figures likely to occupy a box are called the " candidats" of this box; in theory, there are always several candidates, because an one applicant can (and must) be immediately transformed into " valeur" !

• When a grid contains n initial values, the solution of the grid consists in finding the value of the 81-n unknown values. The resolution of a grid thus consists in discovering the 81-n stages which lead logically to the final solution.

The particular vocabulary which is used to name the various types of reasoning will be explained below, as the techniques correspondantes.
are exposed One will also find, at the end of the document, a glossary taking again the whole of the vocabulary and the notions necessary to comprehension of the various techniques of resolution, as well as small a lexicon Anglo-French containing the English equivalent of a certain number of expressions.

Suggestions for the chronological notation of the solution of the sudokus

It is advised, when one wants to solve a sudoku, to note (in shortened but sufficiently explicit form) the various stages of the resolution and, for most delicate of them, the reasoning which was used for the solution. Indeed, if one would make an error (reasoning or of thoughtlessness), error which results (generally some stages later) in a logical impossibility, this precaution makes it possible to retrogress, to include/understand the made error and to correct it!

To note in a concise way and without ambiguity the reasoning used in unfolding, stage after stage, of the process of resolution of a sudoku, it is thus convenient to use certain conventions of which here the principal ones (of other conventions of notation, corresponding to the most worked out techniques, will be indicated further):

to say that a certain box contains a known value, one makes follow the designation of the box by the figure of this value: for example Fa3
to say that a box is not filled yet but that it still can, at a given time, being likely to contain certain values, one makes follow the designation of the box by the figures corresponding to these candidates (written in theory in the order ascending): for example Fa124
the shortened notation " ? F: Fa3" must be read as follows: " Qu' is there on the Fa box? Answer: the examination of all the current possibilities shows that it can be only one 3! "
the shortened notation " 4F?: Fa4" must be read as follows: " Où can one place one 4 on the line F? Answer: the examination of all the current possibilities shows that it can be only on the Fa box! "
In the same way the shortened notation " 4a?: Fa4" must be read as follows: " Où can one place one 4 on the column has? Answer: the examination of all the current possibilities shows that it can be only on the Fa box! "
the shortened notation " 4Yx?: /a" must be read as follows: " Où can one place one 4 in the Yx paving stone? Answer: the examination of all the possible boxes of this paving stone shows that they all are located on the column has! "
the shortened notation " 4A?: /Yx" must be read as follows: " Où can one place one 4 on the line has? Answer: the examination of all the possible boxes of this line shows that they all are located in the Yx paving stone! "

Here, as example, the solution (written in condensed notation) of the first grid presented in this document (each indent " - " preceded and followed by a space the beginning of a new stage indicates):

Fd1 - Eh7 - Fc8 - Ej5 - Dg3 - Jc1 - Ha7 - 4c?: Bc4 - 3c?: Ac3 - 7c?: Cc7 - Ag7 - Be7 - naked pair 26 in Fg-Gg from where 2 excluded in Cg, remains Cg9 - Ca5 - Ce2 - Ba9 - 6Yy?: /f from where 6 excluded out of Hf; camouflaged pair 48 out of Hg-Jg from where 6 excluded out of Hg; camouflaged pair 59 in Hh-Jh from where 6 excluded in Hh; 3rd?: /Zy from where 3 excluded out of Hd-Hf; naked pair 68 in Ab-Bb from where 6 excluded in Hb; camouflaged pair 36 out of He-Hj from where 15 excluded out of He; naked trio (incomplete) 356 out of Ge-He I from where 5 excluded in Ae, remains Ae1 !!! - Aj6 - Bb6 - Ab8 - Bj1 - Bh2 - Af9 - Ad5 - Fh6 - Fg2 - Gg6 - Gc5 - Dc6 - Df2 - Db5 - Ea4 - Eb2 - Hb4 - Ja6 - Ed3 - Ef6 - Bd8 - Bf3 - Ge3 - Gj2 - Hj3 - Hf1 - Jf8 - Jd2 - Hd9 - Jg4 - Hg8 - He6 - Je5 - Jh9 - Hh5!

The expressions " even camouflaged " , " even naked " and " naked trio " which appears above in the part colorée in brun will be explained…
further It will be noticed that l'étape which resulted in finding Ae1 est particularly long and delicate!

Principles of resolution

• In theory the only rule which it is advisable to always keep with the spirit is the following one: all the boxes must be filled by a figure from 1 to 9; the nine boxes of each of the 9 lines must contain, in an unspecified order, each figure from 1 to 9 and it is the same for the 9 columns, like for the 9 paving stones.

• All the other rules (and they are rather numerous) result from this…

The resolution of a sudoku is generally done in 2 phases:

- in the première phase, one makes " visuellement" a certain number of observations and very simple reasoning (" techniques simples") who allow to fill directly certain boxes; if the sudoku proposed is not particularly difficult, one will be able to completely solve it without having to pass to the following phase…
- in the seconde phase, one is constrained, to go further in the resolution of the problem, to reason, at least for some of the remaining stages of the resolution, on the candidates of the still unsolved boxes.

Classification of the sudokus and levels of difficulty

Contrary to a largely widespread opinion, the difficulty of a sudoku is not necessarily related to the low number of initial values (however this connection is statistically rather frequent).

• Les sudokus more faciles can be solved, as one has just said it, without having to pass by the second phase; on the other hand, most difficult cannot do without the examination of the possible candidates. However, it very often arrives that during the second phase, only some stages (seldom more than three) really require to attentively examine the candidates of the unsolved boxes, the majority of the other stages generally being able to be realized by calling only upon the " techniques simples".

• Les sudokus more ardus is those for which the most difficult stages of the second phase require plusieurs raisonnements before discovering a news " valeur" with which one can fill an additional box, the difficulty of these stages all the more large as this reasoning is, either more (see the example given above), or being based on more complex techniques!

It is also advisable to mention following classification:

- standard 1: the sudokus of this type do not comprise any solution
- standard 2: the sudokus of this type comprise of it several
- standard 3: the sudokus of this type (fortunately extremely rare) are those whose solution is single but can be discovered using none the known techniques of rigorous reasoning until now: they require for their resolution the use of computer programs which traverse the whole of the possibilities (the meeting of an impossibility - " bottom-of-sac" - obliges to retrogress to the last " choice; arbitraire" carried out)
- standard 4: this type includes/understands all the others sudokus! Let us announce while passing that there exists among the sudokus of this type a sub-type particular (and rather frequent), that of the sudokus which one can say " redondants" because their data contain at least a box whose knowledge of the value is not necessary to the resolution of the problem (because it can be deduced from the value of the other boxes).

It is generally agreed that the sudokus of the type 1 and 2 are invalid and that the sudokus of the type 3 are without interest (except for the amateurs of the extreme which would like to be inspired some to try to develop a new type of method of resolution…).

In the continuation of this article, it will be thus question only of the sudokus of the type 4 (redondants or not).

In the talk of the various techniques, we will start with three techniques " simples" , then we will approach three techniques " élaborées" to finish by two techniques " extrêmes" (the last of them being declined in five alternatives…).

Three simple techniques

The simple techniques are the techniques which can be implemented without needing to resort to the exhaustive examination of all the candidates of all the boxes not filled.
There are three main categories:

- l' direct elimination

- the research of the single values

- l' indirect elimination

Direct elimination

(or seeks of a candidate " recluse camouflé")

One proceeded in four times:

- a: for a given value v (for example the value 4 in the first example - 01a example - presented below), one locates (in clear green in the three examples which will follow) all the boxes which contains this value;
- b: one " barre" mentally all empty boxes of all the areas (line, column or paving stone) which contain this value v (boxes coloured in dark green in the three examples which will follow);
- c: one seeks if there exists an area which contains an empty and not barred box (box coloured in yellow in the three examples below);
- d: if it is the case and if this box is single, the value v is registered (that in the jargon of the sudoku one calls a " recluse camouflé") in the found box.

Let us distinguish some types of case:
• In the most current cases, one works " by bloc" and the area which intervenes at the stage c is a paving stone including two lines (ou two colonnes) of the block was barred; it remains, on the boxes of the paving stone pertaining to the line (colonne) not barred, only one empty box which can be accompanied:

- is of a box already filled and a barred box because pertaining to a barred column (ligne), as in the 01a example;

- is of two boxes occupied, which corresponds, as in the 01b example, with the one of the most obvious cases (thus easy to locate).

• Cases where, as in the example 01c, the area of the stage c is a line or a column is less easy with repérer.
• Lastly, the cases where one lays out, for a given value, of 8 boxes containing the value v already are simplest because one is sure to find without sorrow the ninth box which misses!

Here thus three examples of elimination directe.

Initially an example running (magazine by three successive images, corresponding respectively at the stages - a, then - b and - c, and finally - d explained above) :


exemple 01a: ici one works in the lines A and B of the block X, and with the column g

… then, a particularly easy example:

exemple 01b:

ici the examination of the only block Z allows us to allot the value 8 with the box Gg

… and finally a last example, less immediate:

exemple 01c:

les barred lines C, F and G do not leave in column a that a free box, the box Ha, to which one thus will be able to allot the value 5

Seek single values

(or seeks of a candidate " recluse nu")

This research consists in examining whether, for a given box (the box Cd in the 02a example below), it would not have only one possible value there (single value, still called " recluse nu" , in opposition to the recluses " camouflés" that we met in the preceding technique).

For that, it is enough:

to locate all the boxes already filled in the " voisinage" studied box (one calls " voisinage" of a box the line, the column and the paving stone to which the box belongs)
to count the number of these boxes filled
and if one finds 8 of them (and provided that one did not make an error!), to allot to the studied box the value which does not form part of the 8 already registered values.

exemple 02a:

Ici the value which it is advisable to place in the box (on yellow bottom) Cd is a 9, since all the other values already exist in the " voisinage" of Cd (the 1 in Cg, the 2 in Bd, the 3 in Fd, the 4 in Af, the 5 in Cj, the 6 in Ad, the 7 in Jd and the 8 in Cc).

This technique is simplest to include/understand but it is heavier to implement than the preceding one, since in theory, it should be under consideration for all the boxes remaining vides.

In practice, it is enough judicious, at least initially (i.e. as long as one does not encounter a difficulty of continuing to advance in the resolution of the sudoku), to consider this technique only in the areas where the number de well informed values is already rather high (initially 7, then 6 or with rigor 5).

Let us note that if an area (line, column or paving stone) has already 8 values informed (situation which only occurs extremely seldom at the beginning of the resolution of a sudoku, but is on the contrary very frequent at the end of the resolution), the value to be allotted to the last empty box is obvious, as in the example which follows:

exemple 02b:

Voici an example (rare after only 2 stages of resolution which resulted in placing a 7 in Af then a 6 in Cf…) in which it is obvious that, on the column f, the 2 missing in the only box Ef.

Indirect elimination

It is about an extension of the first method (direct elimination in four times - a - b - c and - d) in which the " time - b" is supplemented by possible the elimination of boxes supplémentaires (when it is possible).

Here thus four " temps" of this method:

- a: for a given value v (the value 1 in the first 03a example below), one locates all the boxes which contain this value;
- b: one mentally bars all the empty boxes of all the areas containing this value and, si one located 2 or 3 empty boxes rows belonging to the same paving stone and which one is sure that one of them contains the studied value (il is not necessary to know laquelle!), one bars also the empty boxes aligned with those which are located apart from the paving stone (it thus acts of a technique with " localization imprécise")! If it is possible, one repeats the operation - b, as in the 03c example (fourth image)!
- c: one seeks if there exists an area which contains an empty and not barred box;
- d: if it is the case and if this box is single, one registers the value v dans the found box.

Here a first example:

exemple 03a (described in 4 successive images)

explication détaillée : in the third image, one surrounded in red the 2 boxes vides Eg et Fg du paved Yz qui allow to extend the suppressions to the box Gg, and one notes whereas in the paving stone Zz (or on the line G), only the box Gj (in yellow) remains free: it only can thus receive the value 1 !

Here a second example (for which one illustrated only the stage b) :

exemple 03b:

Ici, one still works with the value 1. Empty boxes Ee and Ef of the paving stone Yy makes it possible to extend the suppressions to the boxes Eb and Ej and it is noted whereas, in the paving stone Yz (or on the column j), only the box Fj (in yellow) remains free and can thus see itself allotting the value 1!

Here finally a third example (more complex because it illustrates a case of doubling of the phase - b and which, for this reason, deserves to be illustrated by 4 successive images) :

exemple 03c (described in 4 successive images)

explication: in the third image, one surrounded in red the 2 empty boxes rows Bg and Bj of the paving stone Xz which allows, on the same line B, to extend the suppressions to the box Bb , which involves that, in paving stone Xx, there remain nothing any more but 2 empty boxes, the boxes Ac and Cc which is surrounded in red on the fourth image; as those are aligned on the column C, one can then remove the box Jc of the same column, which involves that, in the paving stone Zx, only the box Ga (in yellow) remains free: it only can thus receive the value 8!

This method of indirect elimination is in general regarded as a case particuler of the method of the dominant areas. This point of view is rather debatable because it does not require, for its implementation, to carry out the tiresome identification of the " candidats" of all the boxes not renseignée.

Method of the indirect, easy elimination and more rapid to be implemented that the method of research of the single values, is of a great interest because it allows:

- in many cases: to completely solve a sudoku without having to pass to the techniques of phase 2 which require obligatorily the recourse to the dentification of the " candidats" ;

- rather often: to discover a " solitaire" (naked or camouflaged) which had escaped to the attention…

Three elaborate techniques

The whole of the elaborate techniques lines up in three main categories:

- the dominant areas

- the naked groups

- the camouflaged groups

But before approaching in detail these worked out techniques, it should be observed that the différence fondamentale which exists between the simple techniques and the others (which they are " élaborées" or " complexes"), it is that the first have the aim of determining directly the value of one of the boxes of the sudoku, while the objective - more modest - other techniques is only to remove one or more candidates of one or more boxes, even if that does not end immediately in the attribution of a value to a box.

To be able to use a worked out technique, it is thus necessary to identify the candidates of the still unsolved boxes.

Preliminary identification of the candidates

Pour this to make, it is necessary, for each examined box, to proceed in three times:

to mentally draw up the list of the 9 potential candidates (from 1 to 9)
then, while examining (exhaustively!) the whole of the boxes of the " voisinage" studied box, to eliminate from this box the figures which correspond to the value of an already solved box of the vicinity,
and finally to note the remaining candidates.

Here, on a purely illustrative basis, which that gives in the case of some of the examples already met (01a, 01b, 01c and 02a):

candidats of the 01a example:

L' examination of the candidates of the boxes of the paving stone Xz watch that only the box Ch it presents candidate 4 (solitaire known as " camouflé" because he is not the only candidate of the box Ch)

candidats of the 01b example:

Les candidates of the boxes of the paving stone Zz show that only the box Gg the candidate 8 (solitaire camouflé)

candidats of the 01c example:

Les candidates of the boxes of the column a show that only the box Ha the candidate 5 (solitaire camouflé)

candidats of the 02a example:

La box Cd one candidate, the 9 (solitaire known as " nu" )

Dominant areas

The techniques based on the concept of dominant area are founded on the généralisation following obviousness:

" Lorsque that a value is allotted to a box, it can be unobtrusive at once list of the candidates of the boxes of any sound voisinage."

Here is the principle.
If one notes, while working on a fixed candidate and while being interested only in the unsolved boxes whose list of the candidates contains this candidate (one disregards other box), who boxes of an area R1 (area " dominante") do all started from another area R2 (area " dominée"), then one can remove the candidate for all the boxes of R2 which does not form part of R1! (to justify these suppressions, it is enough to observe that, whatever the box of area R1 whose value will be equal to the fixed candidate, the boxes of its vicinity will always include/understand the boxes of area R2 which has this candidate; one can thus remove this candidate for all these boxes) .

In this type of situation, one of 2 areas (R1 or R2) is a paving stone, the other being an area " mince" , i.e. a line or a column (it will be seen that, among the extreme techniques, one can define a technique - that of the networks taking as a starting point the same principle but implementing lines and columns) .

Let us give two examples:

exemple 04a:

Ici, for the candidate 6, the area " dominante" R1 is the paving stone Yy and the area " dominée" R2 is the column e; the 6 can thus be withdrawn of the candidates of the boxes Be and Ge (then, the 6 of the box Gd becomes a " recluse camouflé" line G and Gd thus takes the value 6)

exemple 04b:

Ici, for the candidate 8, area R1 is the line A and area R2 is the paving stone Xx; the 8 can thus be withdrawn of the candidates of the boxes Ba, Bb, Bc and Ca (then, the 3 of the box Bc becomes a " recluse nu" line B and Bc thus takes the value 3 )

Naked groups

The techniques based on the groupes nus constitute a generalization of the method of research of the single values (" recluses nus").

The principle consists in here locating if, in the same area, a group of n unsolved boxes would not be such as, if one mentally gathers the liste candidates of these n boxes (by entering each identical figure only once), this liste includes/understands n figures and not more!

If n is worth 2, one speaks about " paire nue" ; if n is worth 3, one speaks about " trio nu" and if n is worth 4, of " quatuor nu".

Once one located a naked group in an area, one can, for all the boxes of this area which do not form part of the group, éliminer their candidates the figures appearing in the liste of n figures (the boxes of the group thus have the " exclusivité" candidates of the list).

When n is higher than 2, it frequently happens that at least one of the boxes of the group does not have like candidates the whole of the figures of the liste: one speaks then about group (trio or quartet) " incomplet" , but that does not remove anything with the validity operation elimination.

Here some examples:

exemple 05a:

Le group of the 2 boxes Ce and Ge of the column e form a paire nue whose candidates are 78; one can thus eliminate the candidates 7 and the 8 of the other boxes of the column e (the 8 of the box Fe and the 7 and 8 of the boxes Ae, De and Je) (the continuation is delicate… and one needs a very long reasoning calling upon technical extremes to establish that… the box Je the value 9!)

exemple 05b:

Le group of the 2 boxes Eg and Eh of the line E form a paire nue whose candidates are 24; one can thus eliminate the candidate 2 of Ed (what reveals in column d a 2 solitary camouflaged with the box Fd) and the 4 of Ee…

But the same naked group also belongs to the paving stone Yz, which allows other eliminations: the 4 of Dj (what creates in line D a 4 solitary camouflaged with the box De) and the 2 of Fj…

exemple 05b
(continuation) :

La even configuration presents the group of 3 boxes Bd, Be and Bf of the line B which forms a trio naked dont the candidates are 379 (trio " incomplet" because only Be all 3 candidate presentpresents); one can thus eliminate the candidates 3 and 7 of Ba.

The same group also belongs to the paving stone Xy, but it does not result any elimination from it because the other boxes of the paving stone are already indicated!

exemple 05c:

Le group of the 3 boxes Ea, Eb and Fc of the paving stone Yx form a trio naked dont the candidates are 189 (incomplete trio); one can thus eliminate the candidate 8 of Da et the candidates 1 and 9 of Fa.

It appears then on the line D a naked pair 26 in Da and Dh, which involves the exclusion of the candidates 2 and 6 of the box Dg which preserves nothing any more but one candidate " recluse nu" being worth 8!

exemple 05d:

Le group of the 4 boxes Da, Db, Ec and Fc of the paving stone Yx form a quatuor naked dont the candidates are 3459 (incomplete quartet); one can thus eliminate (in addition to the candidate 5 of the boxes Ea and Eb) the candidate 3 of the box Ea, which reveals in column a a recluse camouflaged 3 with the box Ga.

exemple 05e:

Le group of the 4 boxes Ja, Jf, Jg and Jh of the line J form a quatuor naked (incomplete) whose candidates are 3478; one can thus eliminate, in addition to the candidates 4 and 8 of the box Jd, the candidates 7 and 8 of the box Jj where a candidate 5 solitary nu.

Camouflaged groups

Techniques baseés on the groupes camouflés" constitutes a generalization of the method of direct elimination which seeks the " recluses camouflés".
(la method seen previously - that based on the naked groups - constituted as for it a generalization of the method of research of the single values or " recluses nus" )

The principle consists in here locating if, in the same area, a group of n unsolved boxes and a list of n distinct figures would not be such as:

- the boxes which have among their candidates one of the figures of the list do all left the group of n boxes;

- the boxes of the area which do not form part of the group do not have any of their candidates who belongs to the list of N chiffres.

If n is worth 2, one speaks about " paire camouflée" ; if n is worth 3, one speaks about " trio camouflé" and if n is worth 4, of " quatuor camouflé".

Once one located a group camouflaged in an area, one can, for all the boxes of this group, éliminer all the candidates who do not appear in the list of n figures. Thus, at the end of the operation, the camouflaged group is transformed into a " group; nu" (what can possibly allow new eliminations if the group also belongs to a second area) !

When n is higher than 2, it frequently happens that at least one of the boxes of the group does not have like candidates the whole of the figures of the list: one then speaks about group (trio or quartet) " incomplet" , but that does not remove anything with the validity operation élimination.

As many the location camouflaged recluses are easy (and easier than that of the naked recluses), as much the location of the camouflaged groups is delicate (much more than that of the naked groups in the same way effective n): the location of the camouflaged pairs is rather delicate, that of the camouflaged trios is very difficult; as for that of the camouflaged quartets, it requires qualities and efforts of extreme attention… Heureusement, the problems which require the location of trios (and especially of quartets) camouflaged are extremely rare!

Here two examples:

exemple 06a:

Le group of 2 boxes Jd and Je of the line J form a paire camouflaged dont the candidates are 29; one can thus eliminate (in addition to the candidate 4, 5 and 8 of the box Jd) the candidate 5 and especially the candidate 7 of the box Je, which fact of appearing in column e un solitary camouflaged 7 with the box De.

Remarquons that the camouflaged pair also belongs to the paving stone Zy and that, become a naked pair of this paving stone, it makes it possible to still eliminate the candidate 9 of the boxes Hd and He

exemple 06b:

Le group of 3 boxes Af, Gf and Jf of the column f form a trio camouflaged (incomplete) whose candidates are 124 ; one can thus eliminate (in addition to the candidates 8 et 9 of the boxes Af and Je, and the candidates 3 and 8 of the box Jf) the candidate 7 box Gf, which reveals in line G un solitary camouflaged 7 with the box Gd.

nota: dans the image opposite, the candidates who appear are already, contrary to the practice taken for the other images, the result of particular eliminations (based successively on an incomplete naked trio 349 in the Zx paving stone and a camouflaged pair 39 with the line H)!

We do not present an example of camouflaged quartets because those are really extremely rare! Moreover, it is exceptional that a sudoku presenting a configuration of camouflaged quartet requires to call upon this technique to solve the problem…!

Two extreme techniques

The extreme techniques only intervene very exceptionally at the beginning of the resolution of a sudoku!

We will be interested only in the two categories of the extreme techniques most useful:
- the networks
- various alternatives of coloring

Techniques based on the networks

These techniques constitute, like the techniques (already seen) based on the dominant areas, a generalization of the assertion:
" Lorsque that a value is allotted to a box, it can be unobtrusive at once list of the candidates of the boxes of any sound voisinage".

These techniques which call upon the concept d'ensemble dominant are based on the following principle (let us recall that we indicate by area " mince" a line or a column but not a paving stone) .

If one notes, while working on a fixed candidate and while being interested only in the unsolved boxes whose list of the candidates contains this candidate (one disregards other box), which boxes of a unit E1 of n areas minces (together " dominant") do all started from another unit E2 of n régions minces (together " dominé"), then one can remove the candidate for all the boxes of E2 which does not form part of E1! (the justification of these suppressions is similar - in more complex however - to that which we gave for the techniques based on the dominant areas) .

In this type of techniques, one of units (E1 or E2) is always a whole of lines, the other being a whole of columns (as opposed to what we saw in the dominant areas, the whole of paving stones are excluded here!).

When n is higher than 2, it is possible (and it is even rather frequent) which a network of order n is " incomplet" , i.e. some of the boxes located at the intersections of the unit dominating and the dominated unit do not have among their candidates the studied candidate (or that they are already solved). As for the camouflaged groups or the naked groups, this does not invalidate the possibilities of elimination.

According to the value of n, the authors of English language speak about " X-Wing " when n is worth 2, of " Swordfish " when n is worth 3, of " Jellyfish" when n is worth 4 or even " Squirmbag" when n is worth 5 (what is completely superfluous because a sudoku of 9 X 9 = 81 boxes which presents Squirmbag can always be solved by considering Jellyfish " complémentaire" !).
In French, it is preferable to be expressed more simply while speaking about network of order n, or, in shortened form, of network-II, network-III or network-Iv!

Here three examples:

exemple 07a:

Ici one has, for the candidate 8, a réseau of order II : les 2 lines F and J constitute unit E1 (dominating) and the columns a and j unit E2; indeed, the two lines A and F all their candidates 8 located at the one of the boxes placed at the intersection with the columns a and j; one can thus eliminate the candidates 8 des boxes of unit E2 which does not form part of unit E1 (thus in Ha and Dj ).

exemple 07b:

Ici one has, for the candidate 8, a réseau of order III: les 3 lines B, E and G constitute unit E1 and the columns a, b and g unit E2; to note that the network is incomplet since the boxes Eb and Ga do not introduce the candidate 8, but this does not prevent from of anything from eliminating the candidates 8 des boxes Hg and Ja, which reveals in Ja a 2 solitary nu.

exemple 07c:

Ici one has, for the candidate 2, a réseau of order IV: the 4 columns c, d, f and g constitute unit E1 and lines A, C, G and J l' together E2 (to note that this network is complete what is rare enough for a network of order IV); one can thus eliminate the candidates 2 des boxes Aa, Ab, Aj, Ga, Gj, Ja, Jb and Jj ; but it is still necessary to make a long continuation of reasoning… to lead to a 9 solitary naked with the box Ej!

Techniques based on the coloring

Before in detail exposing each various technique of coloring, let us start by presenting a certain number of concepts and general principles: techniques, bonds, plays of color, principle of prohibition and principle of elimination.

General principles and vocabulary

Various techniques

There exist 5 techniques calling upon the principle of the coloring; , classified here by order of increasing difficulty:

the simple coloring,
the multiple coloring,
the Bi-coloring,
the mixed coloring and
the coloring generalized.

Three kinds of bonds

All these techniques benefit from the presence of three kinds of particular relations between two boxes " voisines" :

" liens simples" ,
" liens forts" or
" liens faibles".

• One speaks about " lien simple" between 2 boxes of the same area when these 2 boxes have un common candidate, and that none of the other boxes of this area has this candidate.
• One speaks about " lien of paires" when, in the same area, 2 boxes have deux candidates exactly and that l'un (at least) of these two candidates their is commun.
More precisely, one speaks:

- of " lien fort" if the common candidate of a lien of paires does not belong to any other box of the area;

- and of " lien faible" if, on the contrary, the common candidate of the lien of paires also belongs to (at least) another box of the région.

Note: 2 boxes dependant between them by a " bond simple" can be also dependant very well by a " bond fort" ; it is enough for that the 2 boxes have only 2 candidates; on the other hand, a " bond simple" and a " bond faible" cannot relate to the 2 same boxes!

The simple coloring and the multiple coloring use only " liens simples" (all relative to the same candidate); the Bi-coloring uses only " liens of paires" (" forts" or " faibles"), the mixed coloring uses indifferently the three kinds of bonds and finally the generalized coloring uses only the liens simples and the liens forts.

Plays of color

The five techniques of coloring all are based on the 2 concepts of couple and play of color (two of these techniques - the multiple coloring and the generalized coloring - use several plays of color, the three others uses one of them) .

• One calls couple a unit made up of a box and a figure (from 1 to 9). It will be said that a couple is vrai if the figure is well the value of the box (in the solution of the sodoku); it will be said that the couple is faux if this figure is not the value of the box and anything in the other cases (indetermination) are not said. Constantly process of resolution, the " statut" of a couple is thus is " vrai" , that is to say " faux" , that is to say (still) unspecified!

• One calls jeu couleurs a whole of two colors which one will say " opposées" (and that one will choose for this purpose)

for example C1 and C2, or C3 and C4, or C5 and C6, or C7 and C8…

and which is intended to mark resemblances (or contrary to the divergences) of " statut" between " couples" formed of a box and a candidat.

In the three techniques of simple coloring, from multiple coloring and generalized coloring, one goes each time it is possible:

- to give the same color to two couples if one is sure that the respective statute of these couples is, that is to say " vrai" and " vrai" , that is to say " faux" and " faux" (in this case, one will say that these two couples are " solidaires" because " vrais" all both or " faux" both)!
- to give colors " opposées" with two couples if one is sure that one of the two couples is " vrai" while the other couple is " faux" (couples which one will say " antagonistes") !

On the other hand (attention), with the Bi-coloring and the mixed coloring, it can arrive (but not always), if one took into account " bonds faibles" , that two couples of the same box-candidate color are not " solidaires" or that two couples of colors " opposées" are not " antagonistes" !

Note: if two couples are such as one at least of them is " faux" , it will be said that these couples are " incompatibles" ; it is in particular the case if the 2 boxes concerned are " voisines" …

Principle of prohibition

In the implementation of a technique of coloring, one progresses step by step while taking into account, with each step, a new bond. But it is interdict to take into account a new bond which would reveal, by the additional coloring which would result from it, a couple box-candidate which would have the same color as a couple box-candidate (already coloured) located on a box " voisine".

Remarque: it will be seen that the fact of falling on a " situation of interdiction" is often the index of the possibility of an elimination of candidate…

Principle of elimination

In any test of coloring, the sought-after goal is to allow, once the finished coloring, to eliminate a candidate under the terms of the following principle: if two couples box-candidate are at the same time coloured, antagonistic and " voisins" of one (even) third couple (coloured or not), this last couple box-candidate is necessarily " faux" and its candidate can thus be eliminated from the box of this couple.
To be able to apply this principle correctly, here what it is necessary to understand by " voisinage" between couples: two distinct couples box-candidate are " voisins" if they have, either the same box (and thus of the distinct candidates), or even candidate and even area (line, column or paving stone)!

Because they implement several plays of color, the multiple coloring and the generalized coloring cannot use the principle of elimination in the simple form which has just been explained, but they use it in more sophisticated form (although equivalent)!

Comparative table of the various techniques of coloring

We will finish these preliminaries by small a tableau comparatif:

Technique	Nombre of plays of couleurs	Types of bonds taken in compte	Nombre candidates analysés	Équivalences logiques " even color ó solidarité" " opposite colors ó antagonisme"	Voisinage taken in compte	Possibility of boxes multi-plays (••)
simple Coloring	1	simples	1	assurées	entre cases	impossible
multiple Coloring	2 or +	simples	1	assurées	entre cases	impossible
Bi-coloring without bonds faibles	1	forts	de 3 with 9	assurées	entre couples " box-candidat"	impossible
Bi-coloring with weak bonds (•)	1	liens strong and bonds faibles	de 3 with 9	uninsured	entre couples " box-candidat"	impossible
mixed Coloring without bonds faibles	1	liens simple and bonds forts	de 3 with 9	assurées	entre couples " box-candidat"	impossible
mixed Coloring with weak bonds (•)	1	tous	de 3 with 9	uninsured	entre couples " box-candidat"	impossible
Coloring generalized	2 or +	tous	de 3 with 9	assurées	entre couples " box-candidat"	possible

references:

(•) : technique " fonctionne" correctly that if 2 successive weak bonds never have the same common candidate;

(• •) : possible presence of boxes whose at least 2 candidates are coloured while using, for one, a play of color, and for the other, another play of color.

Simple coloring

Let us start with the simplest technique of the coloring, that which exploits only the presence of liens simples concerning tous the même candidat.

Here is the principle:

- a play of color " is chosen; opposées" (for example C1 and COLOR=" #0066CC" >C2)

- one chooses a candidate c (among the values which is not completely allotted)

- one is interested only in the boxes which introduces this candidate (one thus disregards all the others)

- one locates a " lien simple" for this candidate c

- one colors, with the color C1, the bottom of the one of the 2 boxes of this bond and one colors the other box with the color C2

- one seeks if one of the 2 boxes of the preceding bond does not present, for the same candidate c, another " lien simple" with a " nouvelle" put. If it is the case for the box colored with C1, one colors the new box with the color C2; if it is the case for the box colored with C2, one colors the new box with the color COLOR=" #0000FF" >C1. One thus obtains thus one (or two) new box coloriée.

- starting from this (or of these) new colored box, one starts again the process of the preceding stage to extend still gradually, and as much as possible, the coloring with other boxes

- one can thus continue this operation of coloring until it is not possible any more to extend it to new boxes

- one is then in the presence of a grid whose certain boxes are coloriées.

Attention:

Before each extension of the coloring, it is necessary to take care of the logical coherence of carried out work: it is necessary that the new box that one proposes to color with a certain color does not find to be " voisine" of a box already colored with this color; if not this extension should absolutely be prohibited. On the other hand, this " interdiction" an advantage has because it announces that one will be able, as one will see it below, to proceed not only to a elimination of candidate but even also to the attribution of the value c with at least of the coloured boxes!

The boxes thus coloured have the following properties:

- their prime coat is, that is to say C1, is C2 (the simple coloring is often called " coloring alterné" because the color is alternated each time new a " is exploited; bond simple") ;

- they have all the same candidate (who is the candidate c selected at the beginning);

- for this candidate, each one of them is associated with at least another of these boxes, forming with it a " lien simple" ;

- if one considers two unspecified boxes not having the same color, they are obligatorily " antagonistes" , i.e., even if they do not present between them a " lien simple" , if one has the value c, the other does not have it, and reciprocally!

- because in the way in which the coloring was carried out (change of color to each new detected simple bond), all boxes having the same color (C1 or C2) is, with respect to the candidate c choisi, " solidaires" , i.e. or this candidate c est the value of all these boxes, or none of these boxes has this candidate c comme value!

- what we will summarize by saying that all the boxes " C1" are interdependent, all the boxes " C2" are interdependent, and any box " C1 " is antagonistic of any box " C2" !

Elimination of candidate:

Once the simple coloring C1|C2 finished, it could be possibly used to advance in the resolution of the sudoku, provided that one is in the situation " favorable" following:

- the same box N, not coloured but introducing the candidate c, is at the same time in the vicinity of a box C1 and in the vicinity of a box C2: in this case, the candidate c peut and must be eliminated i.e. unobtrusive for the box N!

When that an elimination has just been carried out, it is recommended to proceed immediately to an update of the coloring corresponding because this one can possibly allow other eliminations!

If an elimination of the candidate c intervient in a coloured box, all the boxes equipped with the same color owe also " perdre" this candidate since they are interdependent of this one, and all the boxes which have the other color must on the contrary be affected value c !

Remarques:

- the situation " favorable" with the elimination of candidate necessarily meets if one fell on the prohibition described above: indeed, the box which one avoided coloring is close to a box coloured with C1 and of a box coloured with C2, and it must thus lose its candidate c ; moreover, this elimination of candidate has as an immediate consequence that one of its two coloured close boxes will be found with, for the candidate COLOR=" #993300" >c , a statute of recluse (camouflaged or naked) and must thus be seen allotting the value c, as well, possibly, as all the other boxes " solidaires" , i.e. equipped with the same color!

- if on the other hand, one did not fall on the situation from prohibition, it is not certain that the coloring carried out undoubtedly makes it possible to lead to an elimination of candidate! But the only way of knowing it, it is of " to try its chance" while examining, one by one, each not coloured box having the candidate c !

- in the four examples which go follow, the boxes were not entirely colored, contrary to the most frequent use: one indeed preferred to color only the bottom on which the candidate c with which one works, which makes it possible to better bring closer the technique to " coloring simple" other techniques of coloring (multiple coloring, Bi-coloring and generalized coloring); as for the sequence of the simple bonds, it was marked, in the comments of these examples, by using the symbol " ~".

To start, we will illustrate the technique of the simple coloring alternated by two examples (using each time the 2 same colors C1|C2) in which one is in the case of " prohibition " described above; and in accordance with what was explained, the first example (08a) will present, after initial elimination, a camouflaged recluse, while the second example (08b) will introduce a naked recluse:

exemple 08a:

Le coloring carried out here concerns the candidate 8. One with the sequence of simple bonds according to: Gg8 ~Gf8 ~He8 ~Hh8 ~Bh8 ~Cj8 ~Fj8 avec in Bh a " bifurcation" Bh8 ~Bb8 ~Ab8.
One avoided taking into account the connection Fj8~Ff8, to prevent that the two boxes " voisines" Gf and Ff of the column f are not equipped with same the couleur!
One can thus remove the candidate 8 of the box Ff, which allows, on the line F, to allot the value 8 with the box Fj (solitary camouflaged)!
All boxes interdependent of Fj thus will take the value in their turn 8, namely Gg, He, Bh and Ab.

exemple 08b:

The coloring carried out here concerns the candidate 4. One with the sequence of simple bonds according to: Ah4 ~Af4 ~Gf4 ~Jd4 ~Jh4 ~Gg4 ~Bg4 ~ Ba4 ~Cc4 ~Fc4 ~Fe4 ~Ee4 ~Ea4 . One avoided materializing the bond Jd4 ~Cd4 to avoid having on the line C two of the same boxes couleur, Cd and Cc. One can thus remove the candidate 4 for the box Cd which is " voisine" commune of the 2 boxes Cc and Jd qui is opposite colors. One has then, in column D, a 4 solitaire naked with the box Jd which must take the value 4, like all the boxes " solidaires" Af, Ba, Ee, Fc and Gg. As for the boxes of color " opposée" , they lose all their candidate 4, which makes it possible to still allot (naked candidates solitary) the value 2 with the boxes Ah, Fe and Gf, and the value 8 with the boxes Bg, Cc and Ea and Jh.

Here now two examples in which one can carry out an elimination of candidate without to have met a situation of " as a preliminary; interdiction" :

exemple 08c:

Le coloring carried out here concerns the candidate 2. One with the sequence of simple bonds according to: Ed2 ~Df2 ~Dc2 ~Ea2 ~Ba2 (here there is no " bifurcation").
The boxes Ba and Df are opposite colors and the box Bf " is them; voisine" commune: one can thus withdraw the candidate 2 and there remains to him a candidate 7 solitary naked which is its value!
The box Ba perd thus its candidate 7 and there remains to him the only candidate 2 (solitary naked) which is thus its value. 2 other boxes interdependent of Ba, i.e. Ed and Dc, thus take also the value 2, while the boxes " antagonistes" Df and Ea lose the candidate 2!

exemple 08d:

Le coloring carried out here concerns the candidate 8. One with the sequence (without " bifurcation") simple bonds according to: Fd8 ~Ad8 ~Bf8 ~Bc8 ~Aa8 ~ Da8 ~Ec8.
The boxes Da and Bf are opposite colors and the box Df " is them; voisine" commune: one must thus withdraw the candidate 8 ; in the same way, the boxes Da and Fd are opposite colors and the box De " is them; voisine" commune which cannot thus preserve its candidate 8. Now, on the line D, the box Da thus a 8 solitaire camouflaged: it must thus take the value 8, just as the boxes Ad and Bc qui of it is interdependent!

Multiple coloring

The coloriage multiple (called often also " coloring double" when it uses only two plays of color opposite) is an extension of the simple coloring.

Indeed, the multiple coloring implements, not only one, but at least two sequences of " liens simples" , these bonds concerning all the même candidat c. The first sequence uses for example the couple of opposite colors C1|C2 , while the second sequence uses the couple of opposite colors C3|C4.

Elimination of candidat:

In the event of multiple coloring, the possible elimination of a candidate rests on a " extension" elimination implemented in the simple technique of coloring: indeed, if one detects (instead of a not coloured isolated box…) two coloured boxes solidaires (it does not matter that they are both of the color C3 or of the color C4) and to which one is close to a box C1 while the other is close to a box of color C2 (opposed to C1), then one can affirm that:

- that the candidate c can be unobtrusive for all the interdependent boxes equipped with the color C3 (or C4), et

- that antagonistic boxes C4 (or C3) must take the value c!

exemple 08e:

Le multiple coloring carried out here concerns the candidate 8. There are two independent sequences, one with the couple of colors C1|C2, the other with the couple of colors C3|C4: the first sequence is formed by the simple bonds Dg8 ~Cg8 ~Bh8 ~Be8 (without " bifurcation"), while the second includes/understands the bonds Cd8 ~Ed8 ~Fe8 ~Fc8 ~Dc8 with the " bifurcation" Ed8~Eh8.
It is noted that the box Cd est close to the box Be, whereas the box Eh (interdependent of Cd) is close to the box Dg (antagonistic of Be).
One can thus erase the candidate 8 for the 4 interdependent boxes Cd, Fe, Dc and Eh (and to give consequently the value 3 with the boxes Fe, Dc and Eh) and to give the value 8 with the boxes which are " antagonistes" , i.e. Ed and Fc !

Remarquons that a multiple coloring does not have to necessarily comprise a great number of boxes: indeed, one can (in theory) conceive cases (extreme) where the first sequence counts only two boxes, and where the second sequence counts only three of them!

Bi-coloring

The Bi-coloring appeals, not with the " liens simples" , but with the " liens of paires" , i.e. with the couples of boxes " voisines" equipped with 2 candidates (neither more nor less) of which one at least is at the same time common and clean to these two boxes. " bonds of paires" can be " liens forts" or of the " liens faibles".
In addition, the Bi-coloring does not use qu' only one play of couleurs opposées.

Here how one proceeds:

- a " is located; lien of paires" ; one chooses one of the boxes of this bond and one colors the bottom of this first box two colors C1 and C2, the color C1 being assigned to the bottom of the first candidate of this box and the color C2 at the bottom of the second of his candidates. One then in the same way colors the second box with the colors C1 and C2, but by taking care that the fill color of the candidate common to both boxes is reversed!

- one seeks if one of the two boxes already " bi-coloriées" present a " lien of paires" with a box not colored yet; if it is the case, one colors this new box by always complying with the rule of the inversion of color for the bottom of box of the common candidate;

- one extends thus, gradually, the coloring, until it is not possible any more to go further;

- Attention: before each extension of the coloring, it is necessary to take care of the logical coherence of carried out work: is needed, for each of the two candidates of this new box, that the color which one proposes to assign to this candidate was not already assigned to the same candidate of the one of the boxes of the " voisinage" new box, if not it is necessary to give up this extension (what does not prevent from seeking the other possible ones…) !

In the event of Bi-coloring, the principles of a possible elimination of candidat resemble (partly) that of the elimination of the simple colorings; indeed:

If one detects a not coloured box N of which one of the candidates c is at the same time coloured with a bottom C1 in a box " voisine" V1 and coloured with a bottom C2 d' another box " voisine" V2 and if, moreover , one can be sure that among the 2 boxes V1 and V2, one has as a value c while the other does not have it, then the candidate c can be unobtrusive not coloured box N!

Lors of the examination of the advance of the n bonds of pairs which connect the boxes V1 and V2, here in particular three circumstances in which one can be certain that c is the value of the one of the two boxes V1 and V2 and of only one of them:
- cas n° 1: all the bonds of this advance are " bonds forts" ;
- cas n° 2: in the ordered continuation of the n common candidates of this advance, one never finds 2 times of continuation the same candidate and the two extreme candidates, c' (common to V1 and with the box which follows it) and c" (common to V2 and with the box which precedes it) is not ni one nor the autre the candidate c;
- cas n° 3: in the advance which goes from V1 with V2, each section whose bonds all are of the " bonds faibles" fact of intervening an ordered continuation common candidates in whom one never finds 2 times of continuation the same candidate (the case n° 3 is a kind of " hybride" of the 2 precedents and in fact the general case) represents.

To justify the preceding assertion (which does not go from oneself when one - at least - " bonds of paire" taken into account in the advance of V1 with V2 is a " bond faible" …), let us examine the " situation" box V1 with respect to the candidate c, when one is in the case n° 2 described above:

- if c is the value of COLOR=" #0000FF" >V1, c cannot be a candidate of N and must thus be eliminated for N;

- conversely, if c is not the value of V1, V1 takes necessarily the value c'; the box close to V1 in the sequence of bonds which leads V1 with V2 cannot thus have the value c' and this type of " impossibilité" will be transmitted gradually through the sequence of bonds… to lead to impossibility of giving the value c" with the box V2 which must thus take the value c, which, again, leads us to eliminate the candidate c for the box N!

Thus, whatever the value of V1, the candidate c must be eliminated from COLOR=" #FF0000" >N!

Remarque : instead of reasoning on the basis of V1 to lead to V2, one could as well reason on the basis of V2 to lead to V1 (the final conclusion remainder of course identical, namely elimination of the candidate c of N).

Like the technique of the " coloring simple" , the technique of the Bi-coloring leads to a coloring 2 colors (C1 and C2), and one finds also " solidarités" and of the " antagonismes" , but these solidarity and antagonisms relate to this time, not the Bi-colored boxes themselves, but of the " couples" made of a Bi-colored box and a coloured candidate; moreover, these solidarity systematically do not apply to all the " couples" of the same color! Indeed, if one is certain that one of the couples " box-candidat" is " vrai" (one wants to say by there that the candidate of this couple is the value of the box of this same duet), then one can affirm that:

- all the of the same couples color will be " vrais" provided that they are connected to the first couple by an uninterrupted continuation of " bonds forts" ;

- all the couples of the other color will be " faux" with same the condition!

This occurs in particular in the 08f example, like, partially, in the example 08g.

Because of this important difference between " bonds forts" and " bonds faibles" , sequences of " bonds of paires" are represented, in the comments which accompagent these 2 examples, by two distinct symbols: the symbol " =" for the " bonds forts" and the symbol " - " for the " bonds faibles" !

exemple 08f:

Le Bi-coloring of this example (which illustrates the case n° 1) rests on the circuit of " bonds forts" according to (here there is no bond " faible") : Gg27 =Gh27 =Ah37 =Aj37 =Hj36 =Hh38 =Hg68 =Bg26 =Bj26 =Dj27 (without junction). Let us notice that one avoided establishing the connections Gh27 =Fh28 and Hh38 =Fh28 in order to avoid the inconsistency of a 2 with the Fh box which is incompatible with that already allotted to the box Dj27 !
This prohibition will provide us a possibility of elimination: indeed, the candidate 2 of the not coloured box Fh which is at the same time close to the box Dj27 and of the box Gh27 doit to be eliminated!
One can thus allot the value 8 with the box Fh and thus the value 3 with the box Hh and, gradually (principle of solidarity), the 6 with Hj, the 3 with Aj, the 7 with Ah, the 2 with Gh, the 7 with Gg, and also the 8 with Hg, the 6 à Bg, the 2 with Bj and the 7à Dj!

exemple 08g:

Le Bi-coloring of this example (which illustrates the case n° 2) rests on the circuit of " bonds of paires" (here there are 8 " bonds forts" and 4 " bonds faibles") according to: Bj27 -Be74 -De48 =Df81 =Hf18 =Hd81 =Fd14 =Fb41 =Eb17 -Eh72 , with the three junctions Eb17 =Ab74 , Eb17 =Dc74 et Fd14 -Cd42 . Let us notice that one avoided establishing the connections Df81 =Dj17 and Dc74 =Dj17 in order to avoid the inconsistency of a 7 with the Dj box which is incompatible with that already allotted to the box Bj27 !
This prohibition will provide a possibility of elimination: indeed, the candidate 7 of the not coloured box Dj which is close to Bj27 and of Eh27doit to be eliminated!
One can thus allot the value 1 with the box Dj and thus the value 8 with the box Df (solitary camouflaged on the line D) and, gradually (principle of solidarity limited to only the " bonds forts"), the 4 à De, et also the 1 with Hf, the 8 with Hd, the 1 with Fd, the 4 with Fb, the 1 à Eb, the 7 with Ab and the 7 with Dc!

Bi-coloriage special on three cases (notices):
The 08g example presents another circuit of interesting Bi-coloring: this small circuit, which is made of two " bonds of paires" connecting 3 boxes (Bj27-Be74-Cd42) , allows the elimination of a candidate of the box (Ch247) , which is close at the same time to the first and the last of the 3 boxes of the circuit, because this candidate (here one 2) is coloured - but with two opposite colors -, in the first box and the last box of this circuit; the Anglo-Saxons call " XY-Wing" this rather frequent type of configuration c₁ c₂ - c₂ c₃ - c₃ c₁, where each of the 2 bonds can be indifferently " fort" or " faible" !

Mixed coloring

The mixed coloring is a technique of coloring which uses at the same time the possibilities of the simple coloring and those of the Bi-coloring, while using like them only one play of color opposite: C1|C2.

In the event of mixed coloring, the principles of a possible elimination of candidat are almost identical to those of the Bi-coloring; indeed:

If one detects a box (coloured or not) N of which one of the candidates c is at the same time " voisin" of a couple " box-candidate coloré" K1 of color C1 and " voisin" of a couple " box-candidate coloré" COLOR=" #0066CC" >K2 of color C2 and if, moreover , one can be sure that among the 2 couples " box-candidat" K1 and K2, one corresponds to a true assumption while the other corresponds to a false assumption, then the candidate c can be unobtrusive box N!

to be certain that one of the couples is " vrai" while the other is " faux" , it is necessary, in the examination of the advance which connects the couples K1 and K2, to be interested in each section which comprises only " bonds of paires" and to locate if, for each one of them, one is in one of the three following circumstances:

- cas n° 1: all the bonds of this section are " bonds forts" ;

- cas n° 2: in the ordered continuation of the n common candidates of this section, one never finds 2 times of continuation the same candidate;

- cas n° 3: each possible under-section (of this section) whose bonds all are of the " bonds faibles" fact of intervening an ordered continuation common candidates in whom one never finds 2 times of continuation the same candidate (the case n° 3 is a kind of " hybride" of the 2 precedents and in fact the general case) represents.

exemple 08:00 :

Le mixed coloring of this example is based on the following circuit: Fa13=Fd23/Fd3~Dd3 with a junction Fa13/Fa1~Ff1~Df1

The Df2 couple is at the same time " voisin" of Df1 and " voisin" of Fd2 and one is certain that Df1 and Fd2 is " antagonistes" since the bonds of pairs implemented in the circuit are all of the " bonds forts" (case n° 1): Df2 thus corresponds to a false assumption and one can eliminate the candidate 2 of the box Df (the continuation of the resolution is more delicate…)

Note:

- Voisinage between two couples " box-candidat" : concept of " voisinage" is more subtle in the case of 2 couples " box-candidat" that in the case of 2 boxes " entières" (that they are coloured or not coloured). It is intended to detect possible the " incompatibilité" between each assumption represented by these 2 couples, the " incompatibilité" being impossibility for these 2 assumptions of being true both (2 incompatible assumptions can be false both). Possible vicinity (and thus the " incompatibilité" corresponding) between 2 couples " box-candidat" is not established (and does not have to thus be examined) only in each following circumstance:

- the 2 candidates of these 2 couples are identical and the 2 boxes which contain these couples are different and " voisines" (with the direction which we gave to the concept of " voisinage" between boxes);

- the 2 boxes which contain these 2 couples are identical and the 2 candidates of these couples are different!

In other words, two couples " box-candidat" different are " voisins" if they have, either even box, or even candidate and even area; and if they are " voisins" , they represent assumptions " incompatibles" !

- a circuit " mixte" present at least a box " charnière" , i.e. a box presenting on a side a bond " simple" (for one of its candidates) and other a " bond of paire" ; this is not possible that if the box has only 2 candidates (pair) (dans the example above, one has 2 box-hinges, the Fa box and the box Fd) ;

- it can happen that a couple is " voisin" of another couple located on the same box (c' is the case of the Df1/Df2 couple of the ci-dessus example);

- it can happen that a box carrying a pair of candidates is a " double charnière" , when it connects two bonds " simples" relative to different candidates (l' example above does not comprise such a box) .

One will be able to find, in the following chapter devoted to the generalized coloration, two other examples of mixed coloring:

- the circuit C1|C2 of the 08i example and

- the circuit C3|C4 of the 08j example!

Generalized coloring

The generalized coloring is a combination of all the techniques of coloring and can use all the possibilities of them (mode of coloring and possibility of elimination), except the taking into account of the " bonds faibles".
At the difference in the simple coloring, Bi-coloring or mixed coloring, it implements, like the multiple coloring, at least two plays distinct from opposite colors: C1|C2, C3|C4, C5|C6, C7|C8, etc…
With the difference in the Bi-coloring and mixed coloring, the circuits of a generalized coloring exclude any bond from pairs " faible" !

Elimination of candidat:

- the principle used for the elimination of a candidate in the case of a coloriage multiple is usable in a generalized coloring, with however two small difference due to the fact that one works in general on several candidates at the same time:

- concept of " voisinage" ordinary between boxes must be replaced by that of " voisinage" between couples " box-candidat"

- moreover it can happen that a couple is " voisin" of another couple located on the same box (c' is the case of the Gd2/Gd5 couples of the 08i example and the Aa7/Aa8 couples of the 08j example; to see these 2 ci-dessous examples);

- When the coloring uses n plays of color opposed, the reasoning which allows an elimination of candidate brings into play, in theory, of the coloured boxes which utilize the whole of these n plays of color; also, as soon as n exceeds 2 (comme in the example 08j ci-dessous), the reasoning is delicate to establish with rigor and it is it more especially as n is larger…

to render comprehensible it, simplest is to present as of now the deux exemples announced:

Premier exemple

Le first example which follows (08i example) is a complex example rests on two circuits; the first circuit, based on the couple of opposite colors C1|C2, is a circuit " mixte" constituted at the same time of " bonds simples" and of " bonds of paire" , since it includes/understands successively a bond " simple" (candidate 2), then a bond of pair and finally a series of four " bonds simples" (candidate 2): Ee2~Ej2/Ej25=Dj25/Dj2~ Dd2~Ee2~He2~Gd2, with a junction (" bond simple" for the candidate 5) Ej25/Ej5~Ea5; the second circuit, based on the couple of opposite colors C3|C4, is a circuit " pur" constituted exclusively, and for the candidate 5, of bonds " simples" Gd5~Gc5~Ja5~Je5~Ce5~Cd5 with a junction Gc5~Dc5.
The box Gd25 belongs at the same time to the first and the second circuit!

exemple 08i:

On notices that the 2 couples " box-candidat" Dc5 and Gd5 are " solidaires" (even color) and respectively " voisins" couples " antagonistes" Ea5 and Gd2 (opposite colors). Consequently, these two couples Dc5 and Gd5, as well as the other couples équvalents (Ja5 and Ce5) correspond to a " assumption fausse" : one must thus withdraw the candidate 5 with the box Ce which thus takes the value 7 (solitary naked) and the same candidate 5 with the boxes Dc, Gd and Ja (whose value remains for the moment still unspecified).

nota: dans the image above, the registered candidates are already, contrary to the practice taken for the other images, the result of particular eliminations (based successively on an incomplete naked quartet 2578 in the Zy paving stone, a simple coloring of candidate 2, the predominance of the Yz paving stone on the column J for candidate 2, and finally a naked pair 68 in column J and in the Zz paving stone)!

Second exemple
Le second example complexes below (08j example) rests on three independent circuits: the first circuit, based on the couple of opposite colors C1|C2, of 4 " is a circuit; bonds simples" , the second, based on the couple of opposite colors C3|C4, is a circuit " mixte" formed of " bonds simples" and of " bonds forts" , finally the last circuit, based on the couple of opposite colors C5|C6 of 2 " is a circuit; bonds simples" ; the advance of the first circuit is written Da7~Aa7~Ab7~Db7 with a junction Ab7/Ab17/Ab1~Gb1 (to notice how pair 17 of the Ab box enables him to play a part of double hinge between 2 simple bonds relating to 2 different candidates), that of the second circuit is written Hc58=He58=Ge15/Ge5~Ga5~Ea5~Ec5 with a junction He58=Je18 and that of the third is written Ac18/Ac8~Aa8~Ja8
The box Aa78 belongs at the same time to the first and the second circuit!

exemple 08j:

Le couple " box-candidat" Ge1 is " voisin" couple Gb1, while the couple Je8 (interdependent of Ge1) is " voisin" couple Ja8: thus if the assumption C3 was true, it would involve that C1 and C5 would be both of the " assumptions fausses". However, with the box Aa, the couples " voisins" Aa7 and Aa8 show that the colors C2 and C6 are incompatible and thus that at least one of the colors C1 and C5 corresponds to a true assumption.
This is not possible that if the color C3 corresponds to a false assumption: one can thus affirm that the assumption C4 is true!
On can thus allot a 8 with the box He, a 5 in the Ea boxes, Ge and Hc and a 1 with the Je. box

nota: dans the image above, the candidates who appear are already, contrary to the practice taken for the other images, the result of particular eliminations (based successively on a naked pair 67 on the line H and the predominance of the Yy paving stone on the column E for candidate 6)!

Let us finish by some commentaires généraux:

- a generalized coloring always uses several (at least two) plays of color opposite: C1|C2, C3|C4, C5|C6, C7|C8, etc…

- to each play of color a " corresponds; circuit" , i.e. a sequence of bonds; and reciprocally, each circuit implements one set of 2 colors, and this play is clean for him;

- a circuit is not necessarily " pur" , i.e. constituted of bonds of comparable nature; it can on the contrary be " mixte" , i.e. to combine at the same time bonds " simples" (" ~") and of the " bonds (of pair) forts" (" =") ;

- a circuit " mixte" present at least a box " charnière" , i.e. a box presenting on a side a bond " simple" (for one of its candidates) and other a " bond of paire" ; this is not possible that if the box has only 2 candidates (pair);

- it happens that a box carrying a pair of candidates is a " double charnière" , when it connects two bonds " simples" relative to different candidates (c' is the case of the Ab box of the 08j example);

- it is rather frequent that a box is with horse on two distinct circuits (c' is the case of the box Gd of the 08i example and the Aa box of the 08j example).

Glossary

has B C D E F G H I J K L M
NR O P Q R S T U V W X Y Z

antagonistes se known as of 2 couples " box-candidat" (generally coloured) which has contrary statutes: the assertion " le candidate of the one of the couples is the value of the box of very the couple" is true for one of the couples and it is false for the other couple!

bloc ensemble of 3 contiguous paving stones. There exist 3 horizontal blocks (X, Y and Z) and three vertical blocks (X, there and Z). The horizontal blocks include/understand 3 lines; the horizontal blocks include/understand 3 colonnes

camouflé qualificatif applying, in an area, with a " solitaire" or with a " groupe" (pair, trio or quartet); a group of n candidates is " camouflé" if, in the area considered, there exists a subset of n boxes such as these boxes present all the whole of these n candidates, that at least one of them introduce at least another candidate and that the other boxes of the area do not present any of these n candidates; the contrary adjective of " camouflé" is " nu"

candidat chiffre which, at a given time of the advance of the resolution of the problem, is likely to be, among others, the value (still unspecified) of a given box still not " résolue"

coloriage technic which consists in coloring a certain number of couples " box-candidat" so that, as far as possible , all the couples equipped with the same color is " solidaires" two with deux

couple " box-candidat" association of a box and a candidate: the existence of a couple " box-candidat" mean that this candidate belonged to the candidates of this box; to a couple an assumption corresponds: this one is " vraie" if the candidate is the value of this box, and it is " fausse" in the contrary case! By extension, one can say of a couple which it is " vrai" or that it is " faux" !
Two couples box-candidate can in particular be " solidaires" , " antagonistes" or " incompatibles" (and thus " voisins")

étape dans a grid to be solved, there are as many stages as of unknown values to discover; to advance of a stage in the resolution of a sudoku thus consists in finding (by reasoning) the value of a still unsolved box.
A stage can comprise several under-stages, each one of it consisting in eliminating at least a candidate from the one of the boxes of the grill.

groupe ensemble of n candidates present in the lists of " candidats" boxes of the same area and presenting a certain characteristic; a group can be " nu" or " camouflé". According to the value about n, one speaks about pair, trio or quatuor

incompatibles se known as of the assumptions corresponding to two couples " box-candidat" , when one can affirm that one (at least) of these two assumptions is false. By extension, one can to speak about couples " incompatibles" ; two couples " voisins" are always " incompatibles"

lien présence of a special relation between 2 boxes " voisines" ; a bond can be " simple" , " fort" or " faible"

lien of paires " bond fort" or " bond faible"

lien faible présence in the same area of two boxes having each one two candidates - and two only -, one of these candidates (at least) being common to both boxes, this candidate also whom can belong to one (or several) another box of very the région

lien fort présence in the same area of two boxes having each one two candidates - and two only -, one of these candidates (at least) being at the same time common to both boxes and specific to these two only boxes (no other box of the area has it)

lien simple pour a " candidat" given, presence in the same area of two boxes - and two only - having this candidat

mince voir " région"

nu qualificatif applying, in a " région" , with a " solitaire" or with a " groupe" (pair, trio or quartet); a group of n candidates is " nu" if, in the area considered, there exists a subset of n boxes such as these boxes present all exactly n candidates, that these candidates are exactly those of the " groupe" and that the other boxes of the area do not present any of these n candidates; the contrary adjective of " nu" is " camouflé"

paire " groupe" of 2 candidates present in the lists of " candidats" boxes of the same area (see " groupe" and also " bond of paires")

pavé " région" square of 3x3=9 boxes, located at the intersection of 2 blocks and thus laid out on 3 contiguous lines and 3 columns

quatuor " groupe" of 4 candidates present in the lists of " candidats" boxes of same a région

région mot generic which indicates indifferently a line, a column or a paving stone of 9 boxes; an area is known as mince if it indicates a line or a column (but not a paving stone)

réseau ensemble of N lines and N columns whose boxes located at the intersections of these lines and these columns have some particularité

résolue se known as of a box which one knows the value (one says also " remplie")

solidaires se known as of 2 couples " box-candidat" (generally coloured) which has same the " statut" : or the assertion " le candidate of a couple is the value of the box of very the couple" is true for these 2 couples, or it is false for the 2 couples!

solitaire se known as of a " candidat" such as, in a certain area, there exists only one box which presents this " candidat". A solitary candidate can be " nu" or " camouflé" , according to whether he is or not the only candidate of this box. So for a certain candidate, a box introduces a recluse, naked or camouflaged, this candidate can be only the " valeur" of this case

trio " groupe" of 3 candidates present in the lists of " candidats" boxes of same a région

valeur chiffre which corresponds to the contents of a box. A value can be, is initial (if it belongs to the facts of the case), is deduced (if one found it by reasoning). So at a given time, the value is still unspecified, the possible figures at this moment are called the " candidats" of this case

voisinage le vicinity of a box is consisted all 20 box " voisines" of this box (see following definition); one can also speak about " voisinage" in connection with couples " box-candidat"

voisines se known as of two boxes which belong to the same area (line, column or paving stone). Example: the boxes Eh, Jd and FF are all of the " voisines" box ED, whereas cd. is not a " voisine" of Ed

voisins se known as of two couples " box-candidat" distinct which has, either the same box, or even candidate and even area (boxes " voisines") ; assumptions corresponding to two couples " voisins" are " incompatibles"

Small lexicon franco-anglais

bi-coloriage

ó
forcing chains

bi-coloriage

ó
XY-Chains

bi-coloriage " spécial" on 3 cases

ó
XY-Wing

bloc

ó
block

camouflé

ó
hidden

candidat

ó
candidate

case

ó
celle

colonne

ó
column

coloriage généralisé

ó
3D - Medusa

coloriage multiple

ó
multi-coloring

coloriage simple

ó
simple coloring

groupe

ó
subset

ligne

ó
row

nu

ó
naked

paire

ó
pair

pavé

ó
box (ou sometimes block)

quatuor

ó
quad

région

ó
group

régions dominantes

ó
interactions

régions dominantes

ó
locked candidates

réseau-II

ó
X-Wing

réseau-III

ó
swordfish

réseau-IV

ó
jellyfish

solitaire

ó
single

trio

ó
triple

3D - Medusa

ó
coloriage généralisé

block

ó
bloc (ou parfois paved)

box

ó
pavé

candidate

ó
candidat

celle

ó
case

column

ó
colonne

forcing chains

ó
bi-coloriage

group

ó
région

hidden

ó
camouflé

interactions

ó
régions dominantes

jellyfish

ó
réseau-IV

locked candidates

ó
régions dominantes

multi-coloring

ó
coloriage multiple

naked

ó
nu

pair

ó
paire

quad

ó
quatuor

row

ó
ligne

simple coloring

ó
coloriage simple

single

ó
solitaire

subset

ó
groupe

swordfish

ó
réseau-III

triple

ó
trio

X-Wing

ó
réseau-II

XY-Chains

ó
bi-coloriage

XY-Wing

ó
bi-coloriage " spécial" on 3 cases

Random links: 1891 | Arritmia cardiaca | Victor Boret | Hornets de Pittsburgh | Police chief of exposure | Reasoned negotiation | Variété_de_Severi-Brauer

antagonistes	se known as of 2 couples " box-candidat" (generally coloured) which has contrary statutes: the assertion " le candidate of the one of the couples is the value of the box of very the couple" is true for one of the couples and it is false for the other couple!
bloc	ensemble of 3 contiguous paving stones. There exist 3 horizontal blocks (X, Y and Z) and three vertical blocks (X, there and Z). The horizontal blocks include/understand 3 lines; the horizontal blocks include/understand 3 colonnes
camouflé	qualificatif applying, in an area, with a " solitaire" or with a " groupe" (pair, trio or quartet); a group of n candidates is " camouflé" if, in the area considered, there exists a subset of n boxes such as these boxes present all the whole of these n candidates, that at least one of them introduce at least another candidate and that the other boxes of the area do not present any of these n candidates; the contrary adjective of " camouflé" is " nu"
candidat	chiffre which, at a given time of the advance of the resolution of the problem, is likely to be, among others, the value (still unspecified) of a given box still not " résolue"
coloriage	technic which consists in coloring a certain number of couples " box-candidat" so that, as far as possible , all the couples equipped with the same color is " solidaires" two with deux
couple " box-candidat"	association of a box and a candidate: the existence of a couple " box-candidat" mean that this candidate belonged to the candidates of this box; to a couple an assumption corresponds: this one is " vraie" if the candidate is the value of this box, and it is " fausse" in the contrary case! By extension, one can say of a couple which it is " vrai" or that it is " faux" ! Two couples box-candidate can in particular be " solidaires" , " antagonistes" or " incompatibles" (and thus " voisins")
étape	dans a grid to be solved, there are as many stages as of unknown values to discover; to advance of a stage in the resolution of a sudoku thus consists in finding (by reasoning) the value of a still unsolved box. A stage can comprise several under-stages, each one of it consisting in eliminating at least a candidate from the one of the boxes of the grill.
groupe	ensemble of n candidates present in the lists of " candidats" boxes of the same area and presenting a certain characteristic; a group can be " nu" or " camouflé". According to the value about n, one speaks about pair, trio or quatuor
incompatibles	se known as of the assumptions corresponding to two couples " box-candidat" , when one can affirm that one (at least) of these two assumptions is false. By extension, one can to speak about couples " incompatibles" ; two couples " voisins" are always " incompatibles"
lien	présence of a special relation between 2 boxes " voisines" ; a bond can be " simple" , " fort" or " faible"
lien of paires	" bond fort" or " bond faible"
lien faible	présence in the same area of two boxes having each one two candidates - and two only -, one of these candidates (at least) being common to both boxes, this candidate also whom can belong to one (or several) another box of very the région
lien fort	présence in the same area of two boxes having each one two candidates - and two only -, one of these candidates (at least) being at the same time common to both boxes and specific to these two only boxes (no other box of the area has it)
lien simple	pour a " candidat" given, presence in the same area of two boxes - and two only - having this candidat
mince	voir " région"
nu	qualificatif applying, in a " région" , with a " solitaire" or with a " groupe" (pair, trio or quartet); a group of n candidates is " nu" if, in the area considered, there exists a subset of n boxes such as these boxes present all exactly n candidates, that these candidates are exactly those of the " groupe" and that the other boxes of the area do not present any of these n candidates; the contrary adjective of " nu" is " camouflé"
paire	" groupe" of 2 candidates present in the lists of " candidats" boxes of the same area (see " groupe" and also " bond of paires")
pavé	" région" square of 3x3=9 boxes, located at the intersection of 2 blocks and thus laid out on 3 contiguous lines and 3 columns
quatuor	" groupe" of 4 candidates present in the lists of " candidats" boxes of same a région
région	mot generic which indicates indifferently a line, a column or a paving stone of 9 boxes; an area is known as mince if it indicates a line or a column (but not a paving stone)
réseau	ensemble of N lines and N columns whose boxes located at the intersections of these lines and these columns have some particularité
résolue	se known as of a box which one knows the value (one says also " remplie")
solidaires	se known as of 2 couples " box-candidat" (generally coloured) which has same the " statut" : or the assertion " le candidate of a couple is the value of the box of very the couple" is true for these 2 couples, or it is false for the 2 couples!
solitaire	se known as of a " candidat" such as, in a certain area, there exists only one box which presents this " candidat". A solitary candidate can be " nu" or " camouflé" , according to whether he is or not the only candidate of this box. So for a certain candidate, a box introduces a recluse, naked or camouflaged, this candidate can be only the " valeur" of this case
trio	" groupe" of 3 candidates present in the lists of " candidats" boxes of same a région
valeur	chiffre which corresponds to the contents of a box. A value can be, is initial (if it belongs to the facts of the case), is deduced (if one found it by reasoning). So at a given time, the value is still unspecified, the possible figures at this moment are called the " candidats" of this case
voisinage	le vicinity of a box is consisted all 20 box " voisines" of this box (see following definition); one can also speak about " voisinage" in connection with couples " box-candidat"
voisines	se known as of two boxes which belong to the same area (line, column or paving stone). Example: the boxes Eh, Jd and FF are all of the " voisines" box ED, whereas cd. is not a " voisine" of Ed
voisins	se known as of two couples " box-candidat" distinct which has, either the same box, or even candidate and even area (boxes " voisines") ; assumptions corresponding to two couples " voisins" are " incompatibles"