Sous-ensembles nus

Qu'est-ce que les sous-ensembles nus dans Sudoku?

Un sous-ensemble nu est un groupe de N cellules au sein d'une même maison (ligne, colonne ou bloc) dont les candidats combinés contiennent exactement N chiffres distincts. Puisque ces N chiffres doivent occuper ces N cellules, ils ne peuvent pas apparaître dans aucune autre Case de cette maison. Cela vous permet d'éliminer en toute sécurité ces chiffres des cellules restantes. Le mot "nu" signifie que les candidats sont pleinement visibles et exposés. Vous n'avez pas besoin de chercher des chiffres cachés parmi d'autres candidats. Le sous-ensemble se révèle clairement par les marques au crayon dans ces cellules. Il existe quatre techniques de sous-ensemble nu, une pour chaque taille possible : - Simple nu (N=1) -- une Case avec un seul candidat - Paire nue (N=2) -- deux cellules dont les candidats combinés sont exactement deux chiffres - Triple nu (N=3) -- trois cellules dont les candidats combinés sont exactement trois chiffres - Quadruplet nu (N=4) -- quatre cellules dont les candidats combinés sont exactement quatre chiffres Ces quatre techniques forment une famille. Elles partagent la même logique fondamentale et diffèrent uniquement par le nombre de cellules impliquées. Une fois que vous avez compris le principe de base, les sous-ensembles plus grands deviennent des extensions naturelles des plus simples.

Le principe fondamental : Pourquoi les sous-ensembles nus fonctionnent-ils ?

La logique derrière les sous-ensembles nus repose sur un argument fondamental de dénombrement parfois appelé principe des tiroirs. En langage courant : si vous avez N emplacements et exactement N éléments à les remplir, chaque élément occupe un seul emplacement, et aucun autre élément ne peut occuper ces emplacements. Considérez une ligne composée de neuf cellules. Chaque Case non résolu possède un ensemble de chiffres candidats, les marques au crayon qui pourraient encore légalement être placées dans cette Case. Supposons que vous trouviez deux cellules dans cette ligne dont les candidats proviennent tous deux du même ensemble de deux chiffres, par exemple {4, 6}. L'une de ces cellules doit contenir 4 et l'autre doit contenir 6. Il n'y a pas d'autre possibilité. Cela signifie qu'aucune autre Case de la ligne ne peut contenir 4 ou 6, car ces deux chiffres sont entièrement attribués à ces deux cellules. Le même raisonnement s'applique à une échelle plus grande. Trois cellules dont l'ensemble des candidats ne comprend que trois chiffres fixent ces trois chiffres dans ces trois cellules. Quatre cellules dont l'ensemble des candidats ne comprend que quatre chiffres fixent ces quatre chiffres. Dans chaque Case, les chiffres verrouillés peuvent être éliminés de toutes les autres cellules du même groupe partagé. Ce principe s'applique de la même manière, que le groupe soit une ligne, une colonne ou un bloc 3x3. La seule condition est que les N cellules appartiennent toutes au même groupe.

Simple nu : La base de la résolution de Sudoku

Un Simple nu est le sous-ensemble nu le plus simple possible. Il se produit lorsque un Case n'a qu'un seul candidat restant dans ses marques au crayon. Puisqu'il n'y a qu'un seul chiffre qui peut légalement aller dans cet Case, ce chiffre est la solution pour cet Case. Tout résolveur de Sudoku, humain ou algorithmique, repose sur les singles nus. C'est la dernière étape de la chaîne d'élimination : après que toutes les contraintes de la ligne, de la colonne et du bloc ont éliminé les chiffres impossibles, le dernier candidat restant est la réponse. Trouver un Simple nu nécessite de suivre soigneusement les marques au crayon de chaque Case. Un Case commence avec jusqu'à neuf candidats possibles. À mesure que vous placez des chiffres ailleurs sur le plateau, les candidats sont éliminés : - Si un chiffre est placé n'importe où dans la même ligne, supprimez-le des candidats de cet Case. - Si un chiffre est placé n'importe où dans la même colonne, supprimez-le des candidats de cet Case. - Si un chiffre est placé n'importe où dans le même bloc 3x3, supprimez-le des candidats de cet Case. Lorsque ces éliminations réduisent un Case à un seul candidat, vous avez trouvé un Simple nu. Considérez Case R5C3 dans un puzzle partiellement résolu. Les contraintes de la ligne, de la colonne et du bloc éliminent les chiffres suivants : - La ligne 5 contient déjà : 1, 3, 5, 8 - La colonne 3 contient déjà : 2, 6, 9 - Le bloc 4 (le bloc du milieu-gauche) contient déjà : 7 Réunis, les chiffres 1, 2, 3, 5, 6, 7, 8 et 9 sont tous éliminés. Le seul candidat restant est 4. Case R5C3 doit être 4. C'est un Simple nu. Les singles nus doivent être votre première vérification après chaque mouvement. Chaque fois que vous placez un chiffre, il peut réduire des cellules voisines à un seul candidat. Dans les puzzles plus faciles, des chaînes de singles nus peuvent résoudre de grandes parties du plateau sans aucune autre technique. Même dans les puzzles plus difficiles, les singles nus nettoient le plateau après que des techniques plus avancées ont éliminé des candidats.

Paire nue : Deux cellules, deux candidats, éliminations puissantes

Un couple nu apparaît lorsque deux cellules dans la même maison contiennent chacune exactement les mêmes deux candidats et aucun autre candidat. Puisque ces deux chiffres doivent obligatoirement se trouver dans ces deux cellules, vous pouvez éliminer ces deux chiffres de toutes les autres cellules de cette maison. Les couples nus sont l'une des stratégies intermédiaires les plus couramment appliquées. Ils apparaissent fréquemment et permettent souvent des progrès importants en éliminant des candidats qui bloquent d'autres techniques. Supposons que deux cellules dans la ligne 1 contiennent chacune les candidats {4, 6} et aucun autre candidat : - R1C2 a pour candidats : {4, 6} - R1C7 a pour candidats : {4, 6} L'une de ces cellules sera 4 et l'autre sera 6. Nous ne savons pas encore laquelle est laquelle, mais nous savons avec certitude que 4 et 6 sont entièrement utilisés par ces deux cellules. Par conséquent, aucune autre cellule de la ligne 1 ne peut contenir 4 ou 6. Si R1C4 avait les candidats {3, 4, 6, 9}, elle pourrait être réduite à {3, 9} en éliminant 4 et 6. Si R1C8 avait les candidats {2, 6}, elle pourrait être réduite à {2}. Cette réduction à un seul candidat est elle-même une Simple nu, qui résout immédiatement la Case. Parcourez chaque maison à la recherche de cellules n'ayant que deux candidats. Lorsque vous trouvez deux cellules dans la même maison ayant des ensembles identiques de deux candidats, vous avez un Paire nue. Comme les cellules n'ayant que deux marques au crayon se distinguent visuellement, les couples nus sont parmi les techniques intermédiaires les plus faciles à repérer. Une habitude utile : chaque fois que vous remarquez un Case n'ayant que deux candidats, vérifiez immédiatement si une autre Case dans la même ligne, colonne ou bloc partage le même couple.

Triple nu : Trois cellules, trois candidats, une touche subtile

Un Triple nu se produit lorsque trois cellules de la même maison ont des candidats tirés exclusivement d'un même ensemble de trois chiffres exactement. L'ensemble combiné de tous les candidats des trois cellules contient exactement trois chiffres distincts. Voici l'élément clé qui surprend souvent les résolveurs : chaque Case individuel n'a pas besoin de contenir les trois chiffres. Un Triple nu valide peut inclure des cellules ne contenant que deux des trois chiffres. Ce qui compte, c'est que l'union de tous les candidats des trois cellules totalise exactement trois valeurs distinctes. Beaucoup de joueurs apprennent d'abord les paires nues, puis supposent que les triplets nus nécessitent trois cellules contenant chacune les mêmes trois candidats, comme {1, 3, 7} dans les trois cellules. Bien que ce soit une forme valide d'Triple nu, ce n'est pas la seule, ni même la plus courante. Considérez ces trois cellules dans la colonne 5 : - R2C5 : {1, 3} - R4C5 : {1, 7} - R8C5 : {3, 7} Les candidats combinés sont {1, 3, 7}, ce qui correspond exactement à trois chiffres dans trois cellules. C'est un Triple nu valide, même si aucun Case individuel ne contient les trois chiffres. La logique est la même que pour les paires nues. Ces trois chiffres doivent occuper ces trois cellules dans un certain ordre. Un Case obtient 1, un autre obtient 3, un autre obtient 7. Par conséquent, les chiffres 1, 3 et 7 peuvent être éliminés de toutes les autres Case de la colonne 5. Commencez par repérer les cellules ayant deux ou trois candidats. Dans une maison donnée, si vous trouvez trois cellules dont les candidats combinés forment un ensemble de trois chiffres exactement, vous avez un Triple nu. Une approche pratique : 1. Dans chaque maison, listez toutes les cellules non résolues ayant trois candidats ou moins. 2. Choisissez n'importe quelle combinaison de trois telles cellules. 3. Prenez l'union de leurs candidats. Si l'union contient exactement trois chiffres, il s'agit d'un Triple nu. Comme il existe plusieurs combinaisons possibles, les triplets nus nécessitent un balayage plus attentif que les paires nues. C'est ce qui fait partie de leur difficulté, les plaçant parmi les techniques de niveau supérieur.

Quadruplet nu : Quatre cases, quatre candidats, complexité maximale

Un Quadruplet nu est le plus grand sous-ensemble nu couramment utilisé. Il se produit lorsque quatre cellules dans une maison ont des candidats tirés exclusivement du même ensemble de quatre chiffres exactement. Comme pour les triples, les cellules individuelles n'ont pas besoin de contenir tous les quatre chiffres. La condition essentielle est que l'union des candidats sur les quatre cellules soit exactement égale à quatre valeurs distinctes. La logique est identique à celle des sous-ensembles nus plus petits. Les quatre chiffres doivent occuper les quatre cellules. Ces chiffres ne peuvent pas apparaître ailleurs dans la maison. Les quadruplets nus sont rarement trouvés par simple inspection. Avec quatre cellules et quatre chiffres, il existe beaucoup plus de combinaisons à vérifier. Dans une maison comportant six cellules non résolues, il existe 15 façons possibles de choisir quatre d'entre elles. Vérifier mentalement chaque combinaison est fastidieux. La plupart des solveurs qui trouvent des quadruplets nus le font soit par une vérification systématique, soit en remarquant d'abord que les cellules restantes forment un sous-ensemble caché complémentaire. Malgré leur rareté, les quadruplets nus apparaissent effectivement dans des puzzles réels, surtout ceux notés de difficulté modérée à difficile. Avoir cette technique dans son répertoire garantit que vous ne serez pas bloqué lorsque les méthodes plus simples ont été épuisées.

Comment repérer les sous-ensembles nus : Conseils pratiques pour le balayage

Trouver efficacement les sous-ensembles nus nécessite une approche structurée plutôt qu'une recherche aléatoire. Voici les techniques utilisées par les solveurs expérimentés : Commencez par les nombres de candidats faibles : les cellules avec moins de candidats sont plus susceptibles de participer à des sous-ensembles nus. Une Case avec deux candidats peut faire partie d'une paire, d'un triplet ou d'un quadruplet. Une Case avec cinq candidats est moins utile car elle apporte trop de chiffres à l'union. Parcourez chaque maison en cherchant d'abord les cellules à deux candidats. Vérifiez les paires correspondantes. Ensuite, examinez ensemble les cellules à deux ou trois candidats pour repérer les triplets. Travaillez maison par maison : choisissez une ligne, une colonne ou un bloc et examinez tous ses cellules non résolues ensemble. Listez leurs candidats. Cherchez des groupes de cellules dont les candidats se chevauchent dans un petit ensemble de chiffres. Utilisez le contrôle par dénombrement : pour tout groupe de N cellules que vous soupçonnez de former un sous-ensemble nu, dénombrez les chiffres distincts présents dans leur ensemble de candidats. Si le décompte est égal à N, vous avez trouvé un sous-ensemble nu. Si le décompte dépasse N, ces cellules ne forment pas un sous-ensemble nu. Vérifiez après chaque élimination : lorsque une autre technique retire des candidats d'une Case, vérifiez à nouveau la maison de cette Case. L'élimination peut avoir créé un nouveau sous-ensemble nu qui n'était pas visible auparavant. De nombreuses paires nues apparaissent comme effet secondaire d'éliminations antérieures. Cherchez le complément : si une maison possède K cellules non résolues et que vous soupçonnez l'existence d'un sous-ensemble nu mais ne pouvez pas le trouver directement, essayez de regarder le complément. Trouver un sous-ensemble caché de taille M implique automatiquement un sous-ensemble nu de taille K - M.

La relation entre les sous-ensembles nus et les sous-ensembles cachés

Les sous-ensembles nus et les sous-ensembles cachés sont deux aspects d'une même pièce. Comprendre leur dualité approfondit votre maîtrise de la logique Sudoku et peut vous aider à repérer des motifs que vous pourriez autrement manquer. Un sous-ensemble caché se produit lorsque N chiffres dans une maison apparaissent uniquement dans N cellules spécifiques. Les chiffres sont "cachés" car ces cellules peuvent également contenir d'autres candidats. L'élimination consiste à retirer les candidats superflus de ces N cellules, ne laissant que les chiffres cachés. Dans toute maison ayant K cellules non résolues, si un sous-ensemble nu de taille N existe, alors un sous-ensemble caché de taille K - N existe automatiquement. Ces deux sous-ensembles sont complémentaires : ils partagent les cellules non résolues et les chiffres restants en deux groupes non superposés. Par exemple, considérez une ligne avec 6 cellules non résolues. Si deux de ces cellules forment un Paire nue, les quatre autres cellules forment un Quadruple caché (ou de manière équivalente, un Quadruplet nu existe parmi les chiffres exclus de ces quatre cellules). Vous pouvez trouver l'un ou l'autre et appliquer les éliminations correspondantes. Cette dualité signifie que vous avez deux chemins menant à la même élimination. Si une maison a beaucoup de cellules non résolues, un petit sous-ensemble nu (paire ou triplet) est plus facile à repérer qu'un grand sous-ensemble caché. À l'inverse, si une maison a peu de cellules non résolues, un Paire Cachée pourrait être plus facile à trouver qu'une recherche du sous-ensemble Quadruplet nu complémentaire. Les solveurs expérimentés passent alternativement d'une perspective nue à une perspective cachée selon ce qui est le plus pratique dans une situation donnée. La capacité de voir les deux aspects vous donne un avantage significatif.

Progression de difficulté : Du débutant à l'expert

Les quatre techniques de sous-ensemble nu s'étendent sur plusieurs niveaux de difficulté, reflétant à quel point elles sont plus difficiles à trouver lorsque la taille du groupe augmente : Simple nu (N=1) : Niveau 2, Facile Paire nue (N=2) : Niveau 3, Facile Triple nu (N=3) : Niveau 4, Moyen Quadruplet nu (N=4) : Niveau 5, Difficile L'augmentation de la difficulté ne provient pas de la logique, qui reste identique dans chaque Case, mais de la complexité de recherche : Simple nu : Vous devez vérifier une seule Case. Si elle a un seul candidat, c'est terminé. Aucune recherche de combinaisons n'est nécessaire. Paire nue : Vous devez trouver deux cellules avec des candidats identiques. Dans une maison avec six cellules non résolues, il y a 15 paires possibles à vérifier. Mais comme vous cherchez des cellules ayant exactement deux candidats identiques, le motif visuel est distinctif et facile à repérer. Triple nu : Vous devez trouver trois cellules dont l'ensemble des candidats totalise trois chiffres. Dans une maison avec six cellules non résolues, il y a 20 triplets possibles. La recherche est plus difficile car les cellules n'ont pas besoin d'avoir des ensembles de candidats identiques. Quadruplet nu : Vous devez trouver quatre cellules parmi potentiellement beaucoup de cellules non résolues. Le nombre de combinaisons augmente, et les unions à quatre chiffres sont plus difficiles à calculer mentalement. La plupart des quadruplets sont trouvés indirectement, soit par un décompte systématique des candidats, soit en repérant le complémentaire Paire Cachée. Les évaluations de difficulté des puzzles dépendent souvent des techniques nécessaires à leur résolution. Un puzzle qui ne nécessite rien de plus que les singles et paires nues est noté comme facile. Un puzzle nécessitant des triples nus entre dans la catégorie moyenne. Un puzzle qui exige un Quadruplet nu est au moins difficile.

Erreurs courantes et comment les éviter

Erreur 1 : S'attendre à ce que toutes les cellules contiennent tous les chiffres L'erreur la plus courante avec les triplets et quadruples nus est de supposer que chaque Case du sous-ensemble doit contenir tous les N chiffres. Cela est faux. Un Triple nu avec les cellules {1,3}, {1,7} et {3,7} est tout à fait valable même si aucune Case ne contient les trois chiffres 1, 3 et 7. Comment l'éviter : Vérifiez toujours l'union des candidats, pas les cellules individuelles. Comptez les chiffres distincts présents dans toutes les cellules du groupe. Si le décompte est égal au nombre de cellules, il s'agit d'un sous-ensemble nu, quelle que soit la répartition des chiffres au sein des cellules individuelles. Erreur 2 : Confondre les sous-ensembles nus et cachés Un Paire nue possède N cellules dont les candidats sont limités à N chiffres. Un Paire Cachée possède N chiffres dont les emplacements sont limités à N cellules, mais ces cellules peuvent avoir d'autres candidats. Avec un Paire nue, vous éliminez les chiffres du couple à partir des autres cellules de la maison. Avec un Paire Cachée, vous éliminez les chiffres non appartenant au couple à partir des cellules du couple lui-même. Comment l'éviter : Posez-vous la question : « Regarde-je des cellules dont les candidats sont restreints (nus) ou des chiffres dont les emplacements sont restreints (cachés) ? » Le sens de la restriction détermine le type de sous-ensemble que vous avez trouvé. Erreur 3 : Éliminer à partir des mauvaises cellules Lorsque vous trouvez un Paire nue {4, 6} dans les cellules R1C2 et R1C7, vous éliminez les chiffres 4 et 6 des autres cellules de la ligne 1. Vous ne devez pas éliminer d'autres candidats des cellules R1C2 et R1C7 elles-mêmes. Les candidats de l'Paire nue restent intacts dans les cellules du sous-ensemble. Comment l'éviter : Rappelez-vous la règle : les sous-ensembles nus éliminent leurs chiffres des cellules en dehors du sous-ensemble. Les sous-ensembles cachés éliminent les chiffres non appartenant au sous-ensemble des cellules à l'intérieur du sous-ensemble. Erreur 4 : Oublier de vérifier toutes les maisons partagées Deux cellules peuvent partager plus d'une maison. Par exemple, R1C1 et R1C3 partagent à la fois la ligne 1 et le bloc 1. Si elles forment un Paire nue, vous pouvez éliminer les chiffres du couple des autres cellules de la ligne 1 et des autres cellules du bloc 1. Ne limitez pas vos éliminations à une seule maison. Comment l'éviter : Pour chaque sous-ensemble nu que vous trouvez, vérifiez quelles maisons sont partagées par toutes les cellules du sous-ensemble. Appliquez les éliminations dans chaque maison partagée.

Quand utiliser les sous-ensembles nus dans votre processus de résolution

Les sous-ensembles nus doivent être vérifiés dans l'ordre du plus petit au plus grand : 1. Les singles nus en premier. Après chaque placement, recherchez de nouveaux singles nus. Ils sont gratuits et immédiats. 2. Les paires nus en second. Une fois qu'il n'y a plus de singles nus, recherchez des paires nus dans chaque ligne, colonne et bloc. Ce sont la technique intermédiaire la plus courante et elles débloquent souvent de nouveaux singles nus. 3. Les triples nus en troisième position. Lorsque les paires sont insuffisantes, élargissez votre recherche aux triples. Concentrez-vous sur les maisons où plusieurs cellules ont deux ou trois candidats. 4. Les quadruples nus en dernier. Recherchez les quadruples uniquement lorsque les sous-ensembles plus petits et d'autres techniques ont été épuisés. Étant donné leur difficulté, envisagez de vérifier les paires ou triples cachés en premier, car ils peuvent être plus faciles à trouver et révéler les mêmes informations grâce au principe de dualité. En suivant cette progression, vous appliquez les techniques les plus simples et les plus productives en premier, économisant ainsi l'effort mental pour les moments où il est vraiment nécessaire.

Résumé

Les sous-ensembles nus sont une famille de quatre techniques Sudoku unies par un seul principe élégant : N cellules dans une maison avec exactement N candidats combinés bloquent ces chiffres en place, ce qui permet de les éliminer de toutes les autres cellules de la maison. Du modeste Simple nu qui résout directement un Case, en passant par les paires et triples nus qui éliminent des candidats, jusqu'au redoutable Quadruplet nu qui exige une recherche systématique soigneuse, ces techniques forment la colonne vertébrale de la résolution logique des Sudoku. Maîtriser ces méthodes vous fournit des outils fiables applicables à tous les niveaux de difficulté et constitue la base pour aborder des stratégies plus avancées comme les sous-ensembles cachés, les motifs de poisson et les chaînes.