Comment résoudre le Sudoku. À propos des méthodes de résolution de problèmes - Cours complet de Sudoku

Ce qui vous aidera dans le développement de l’un des organes les plus importants – le cerveau. Bien sûr, les célèbres puzzles japonais Sudoku en font partie. Avec leur aide, vous pouvez grandement « gonfler votre cerveau », car en plus de la nécessité de calculer un grand nombre d'options pour la disposition des nombres, vous devez également être capable de le faire quelques dizaines de coups à l'avance. En un mot, c’est un véritable paradis si vous voulez éviter que vos neurones ne se dessèchent. Et aujourd'hui, nous examinerons les techniques de base utilisées par les experts du Sudoku. Cela sera utile aussi bien aux débutants qu’aux fans de longue date de ces puzzles. Après tout, quelqu'un doit faire ses premiers pas dans l'art du Sudoku, et quelqu'un doit améliorer l'efficacité de ses décisions !

Règles

Si vous ne les connaissez pas encore, vous devez d'abord vous familiariser avec les règles. Croyez-moi, ils sont très simples.

Le terrain de jeu est un carré qui mesure 9x9. Dans le même temps, il est divisé en carrés plus petits de dimensions 3x3. Autrement dit, le champ entier est constitué de 81 cellules.

La condition du problème réside dans les nombres déjà placés dans ces cellules.

Un bloc (bloc de cellules) est un petit carré, une rangée ou une ligne.

Ce qu'il faut faire : disposer tous les nombres restants en suivant plusieurs règles. Premièrement, il ne doit y avoir aucune répétition dans chacun des petits carrés. Deuxièmement, il ne doit pas non plus y avoir de répétitions dans toutes les colonnes et lignes. Autrement dit, chaque numéro ne doit apparaître qu’une seule fois dans chacun de ces blocs. Pour que tout soit encore plus clair, faites attention au Sudoku résolu :

Solution basique

En règle générale, si vous résolvez des grilles de Sudoku simples, il vous suffit d'écrire toutes les options possibles pour chacune des 81 cellules et de rayer progressivement les options qui ne conviennent pas. C'est très simple.

Mais si vous passez d'un niveau à un Sudoku plus complexe, les choses deviennent plus intéressantes. Il arrive souvent qu'il n'y ait aucun moyen de mettre de nouveaux nombres, et vous devrez passer par des hypothèses : « Qu'il y ait tel nombre ici », après quoi vous devrez considérer cette hypothèse et soit parvenir à une solution. au problème ou à une contradiction de votre hypothèse.

Mais bien sûr, il existe des techniques spéciales qui vous aideront à faire tout cela plus efficacement.

Techniques

1. Paires/trois/quatre nus

Si vous avez deux cellules dans un bloc (carré, ligne ou colonne) dans lesquelles vous ne pouvez mettre que 2 nombres, alors évidemment ces nombres peuvent être supprimés des options possibles pour les autres cellules de ce bloc.

De plus, cette astuce peut être facilement réalisée aussi bien avec des triplés qu'avec des quadruples :

2. Paires cachées

Une technique très utile, en quelque sorte à l’opposé des couples nus. Si dans deux cellules d'un carré dans les « options possibles », vous avez des nombres qui ne sont répétés nulle part ailleurs (à l'intérieur de ce carré), alors tous les autres nombres de ces deux cellules peuvent être supprimés.

Pour que ce soit encore plus clair, faites attention aux exemples (un simple et un plus complexe) :

Heureusement, cela fonctionne aussi bien à trois qu'à quatre, mais il convient de mentionner une fonctionnalité très importante et très intéressante. Il n'est pas nécessaire que trois/quatre cellules contiennent les mêmes 3 chiffres de la forme (a;b;c) (a;b;c) (a;b;c). Cette option vous suffira : (a;b) (b;c) (a;c).

3. Règle sans nom

Si vous avez une paire ou un triple dans une colonne/ligne, qui sont situés dans le même carré, vous pouvez supprimer ces nombres en toute sécurité des autres cellules de ce carré.

4. Paires de pointage

S'il y a deux nombres identiques dans une ligne/colonne dans les « options possibles », alors ces nombres peuvent être supprimés de la colonne/ligne correspondante.

Cela peut parfois être très utile, surtout si vous trouvez plusieurs de ces paires :

Bien entendu, dans ce cas, ces nombres doivent être absents dans les autres cellules du carré, mais selon la règle sans nom, cela n'est pas obligatoire.

Vous aimez le Sudoku et autres énigmes, jeux, puzzles et tests visant à développer divers aspects de la réflexion ? Accédez à tous les supports interactifs du site pour vous développer plus efficacement.

Conclusion

Nous avons examiné les techniques de base utilisées pour résoudre le Sudoku. Je note que ce n'est qu'un début et dans les articles suivants, nous examinerons des fonctionnalités plus complexes et plus intéressantes, grâce auxquelles la résolution de tels problèmes deviendra encore plus intéressante et plus simple.

En guise de formation, les éditeurs de 4brain vous invitent à vous familiariser avec le fichier, qui contient des grilles Sudoku de différents niveaux de difficulté. Prenez le temps de pratiquer, car si vous consacrez suffisamment de temps à cette activité, alors à la fin de ce cours d'articles, croyez-moi, vous deviendrez un véritable as dans la résolution d'énigmes japonaises.

Si vous avez des questions sur ces techniques ou sur le Sudoku, que nous joignons à l'article, n'hésitez pas à les poser dans les commentaires !

Beaucoup de gens aiment se forcer à penser : certains - pour développer l'intelligence, d'autres - pour garder leur cerveau en forme (oui, le corps n'est pas le seul à avoir besoin d'exercice), et le meilleur simulateur pour l'esprit sont divers jeux de logique et puzzles. L'une des options pour un tel divertissement éducatif peut être appelée Sudoku. Cependant, certains n'ont même jamais entendu parler d'un tel jeu, encore moins en connaissant les règles ou d'autres points intéressants. Grâce à l'article, vous apprendrez toutes les informations nécessaires, par exemple comment résoudre les Sudoku, ainsi que leurs règles et types.

Général

Le Sudoku est un casse-tête. Parfois complexe, difficile à résoudre, mais toujours intéressant et addictif pour quiconque décide de jouer à ce jeu. Le nom vient du japonais : « su » signifie « chiffre » et « doku » signifie « debout seul ».

Tout le monde ne sait pas comment résoudre le Sudoku. Des énigmes complexes, par exemple, peuvent être résolues soit par des débutants intelligents et réfléchis, soit par des professionnels qui pratiquent le jeu depuis plus d'une journée. Il ne sera pas possible pour tout le monde de résoudre le problème en cinq minutes.

Règles

Alors, comment résoudre le Sudoku. Les règles sont très simples et claires, faciles à retenir. Cependant, ne pensez pas que des règles simples promettent une solution « indolore » ; vous devrez beaucoup réfléchir, appliquer une réflexion logique et stratégique et vous efforcer de recréer l’image. Vous devez probablement aimer les chiffres pour résoudre le Sudoku.

Tout d’abord, un carré de 9 x 9 est dessiné. Ensuite, avec des lignes plus audacieuses, il est divisé en « régions » de trois carrés chacune. Le résultat est 81 cellules, qui devraient éventuellement être entièrement remplies de chiffres. C'est là que réside la difficulté : les chiffres de 1 à 9 placés sur tout le périmètre ne doivent être répétés ni en « régions » (3 x 3 carrés) ni en lignes verticales et/ou horizontales. Dans tout Sudoku, il y a initialement des cellules remplies. Sans cela, le jeu est tout simplement impossible, car sinon le résultat ne sera pas une décision, mais une invention. La complexité du puzzle dépend du nombre de nombres. Les sudokus complexes contiennent quelques nombres, souvent disposés de telle manière qu'il faut se creuser un peu la tête avant de les résoudre. Dans les poumons, environ la moitié des chiffres sont déjà en place, ce qui rend leur détermination beaucoup plus facile.

Exemple entièrement démonté

Il est difficile de comprendre comment résoudre le Sudoku s'il n'y a pas d'exemple spécifique montrant étape par étape comment, où et quoi insérer. L'image fournie est considérée comme simple, car de nombreux mini-carrés sont déjà remplis avec les chiffres nécessaires. C’est d’ailleurs sur eux que nous compterons pour trouver une solution.

Pour commencer, vous pouvez regarder les lignes ou les carrés, où se trouvent particulièrement de nombreux nombres. Par exemple, la deuxième colonne en partant de la gauche s'adapte parfaitement ; il ne manque que deux chiffres. Si vous regardez ceux qui sont déjà là, il devient évident qu'il manque 5 et 9 dans les cellules vides des deuxième et huitième lignes. Avec les cinq, tout n'est pas encore clair, cela peut être à la fois ici et là, mais si vous regardez les neuf, tout devient clair. Puisqu'il y a déjà un chiffre 9 sur la deuxième ligne (dans la septième colonne), cela signifie que pour éviter les répétitions, il faut placer le neuf vers le bas, sur la 8ème ligne. En utilisant la méthode d'élimination, nous ajoutons 5 à la 2ème ligne - et nous avons maintenant une colonne remplie.

Vous pouvez résoudre l'ensemble du puzzle Sudoku de la même manière, mais dans des versions plus complexes, lorsqu'il manque non seulement quelques chiffres dans une colonne, une ligne ou un carré, mais bien plus encore, vous devrez utiliser une méthode légèrement différente. Nous allons également analyser cela maintenant.

Cette fois, nous prendrons comme base la « région » médiane, dans laquelle il manque cinq nombres : 3, 5, 6, 7, 8. Nous remplissons chaque cellule non pas avec de grands nombres effectifs, mais avec de petits « brouillons ». On écrit simplement dans chaque carré les nombres qui manquent et qui peuvent être là en raison de leur manque. Dans la cellule du haut, c'est 5, 6, 7 (3 sur cette ligne est déjà dans la « région » à droite, et 8 à gauche) ; la cellule de gauche peut en contenir 5, 6, 7 ; au milieu - 5, 6, 7; à droite - 5, 7, 8 ; d'en bas - 3, 5, 6.

Voyons maintenant quels mini-chiffres contiennent des nombres différents des autres. 3 : ce n’est qu’à un endroit, ce n’est pas au reste. Cela signifie qu'il peut être corrigé pour être plus grand. Les 5, 6 et 7 sont dans au moins deux cellules, ce qui veut dire qu'on les laisse tranquilles. Il y en a 8 dans un seul, ce qui signifie que les chiffres restants disparaissent et que vous pouvez laisser les huit.

En alternant ces deux méthodes, nous continuons à résoudre le Sudoku. Dans notre exemple, nous utiliserons la première méthode, mais il faut rappeler que dans les variations complexes la seconde est nécessaire. Sans lui, ce sera extrêmement difficile.

À propos, lorsqu'un sept du milieu est trouvé dans la « région » supérieure, il peut être supprimé des mini-chiffres du carré du milieu. Si vous faites cela, vous remarquerez qu’il n’en reste qu’un 7 dans cette région, vous ne pouvez donc que la quitter.

C'est tout; résultat final :

Types

Il existe différents types de grilles de Sudoku. Dans certains cas, une condition préalable est l'absence de nombres identiques non seulement dans les lignes, les colonnes et les mini-carrés, mais également en diagonale. Certains contiennent d’autres chiffres au lieu des « régions » habituelles, ce qui rend la résolution du problème beaucoup plus difficile. D'une manière ou d'une autre, vous savez comment résoudre le Sudoku, du moins la règle de base qui s'applique à tout type de Sudoku. Cela vous aidera toujours à faire face à un puzzle de toute complexité, l'essentiel est de faire de votre mieux pour atteindre votre objectif.

Conclusion

Vous savez maintenant comment résoudre le Sudoku et vous pouvez donc télécharger des puzzles similaires sur différents sites, les résoudre en ligne ou acheter des versions papier dans les kiosques à journaux. Dans tous les cas, vous aurez désormais quelque chose à faire pendant de longues heures, voire des jours, car les Sudoku sont irréalistes, surtout lorsqu'il faut réellement comprendre le principe de leur solution. Entraînez-vous, entraînez-vous et entraînez-vous encore - et vous résoudrez alors ce puzzle comme un fou.

Dans des articles précédents, nous avons examiné différentes approches pour résoudre des problèmes en utilisant les grilles de Sudoku comme exemples. Le moment est venu d'essayer, à son tour, d'illustrer les capacités des approches envisagées à l'aide d'un exemple assez complexe de résolution de problèmes. Aujourd’hui, nous allons donc commencer par la version la plus « incroyable » du Sudoku. Veuillez consulter la terminologie et les informations préliminaires, sinon il vous sera difficile de comprendre le contenu de cet article.

Voici les informations que j'ai trouvées sur cette option super complexe sur Internet :

Arto Inkala, professeur à l'Université d'Helsinki, affirme (2011) qu'il a créé les mots croisés Sudoku les plus difficiles au monde. Il a passé trois mois à créer ce puzzle complexe.

Selon lui, les mots croisés qu’il a créés ne peuvent être résolus en utilisant uniquement la logique. Arto Incala affirme que même les joueurs les plus expérimentés consacreront au moins plusieurs jours à la solution. L’invention du professeur s’appelait AI Escargot (AI – les initiales du scientifique, Escargot – de l’anglais « snail »).

Pour résoudre ce problème difficile, selon Arto Incala, il faut garder huit séquences en tête en même temps, contrairement aux puzzles ordinaires, où il faut mémoriser une ou deux séquences.

Eh bien, « séquences de recherches » – cela ressemble toujours à une version machine de la résolution de problèmes, et ceux qui ont résolu le problème d’Arto Incal avec leur propre cerveau en parlent différemment. Quelqu'un l'a résolu en quelques mois, quelqu'un a annoncé que cela n'avait pris que 15 minutes. Eh bien, le champion du monde d'échecs pourrait probablement faire face à la tâche dans un tel moment, et un médium, si une telle chose vit dans notre avion, peut-être encore plus vite. Et le problème pourrait également être rapidement résolu par quelqu’un qui aurait accidentellement choisi quelques numéros réussis pour remplir les cellules vides du premier coup. Disons qu'une personne sur mille résolvant le problème pourrait avoir la même chance.

Donc, à propos de la force brute : si vous réussissez à choisir deux ou trois chiffres corrects, vous n'aurez peut-être pas besoin de forcer huit séquences (ce qui signifie des dizaines d'options). C'était ma pensée lorsque j'ai décidé de commencer à résoudre ce problème. Pour commencer, ayant déjà été préparé dans le cadre des méthodes des articles précédents, j'ai décidé d'oublier ce que je savais jusqu'à présent. Il existe une telle technique que la recherche d'une solution doit se dérouler librement, sans schémas ni idées qui lui sont imposés. Et la situation était nouvelle pour moi, j’avais donc besoin de la regarder d’une nouvelle manière. J'ai placé (sous Excel) le tableau d'origine (à droite) et le tableau de travail dont j'ai déjà eu l'occasion d'évoquer la signification dans mon premier article sur le Sudoku :

Permettez-moi de vous rappeler que la feuille de calcul contient des combinaisons de nombres préautorisées dans des cellules initialement vides.

Après le traitement habituel presque routinier des tableaux, la situation est devenue un peu plus simple :

J'ai commencé à étudier cette situation. Eh bien, comme j’ai déjà oublié comment exactement j’ai résolu ce problème quelques jours plus tôt, je commence à y réfléchir à nouveau. Tout d'abord, j'ai prêté attention aux deux nombres 67 dans les cellules du quatrième bloc et les ai combinés avec le mécanisme de rotation (mouvement) des cellules, dont j'ai parlé dans l'article précédent. Après avoir parcouru toutes les options de rotation des trois premières colonnes du tableau, je suis arrivé à la conclusion que les nombres 6 et 7 ne peuvent pas être dans la même colonne et ne peuvent pas tourner de manière asynchrone ; pendant le processus de rotation, ils ne peuvent que se suivre. De plus, si vous regardez attentivement, les sept et quatre semblent se déplacer de manière synchrone le long des trois colonnes. Par conséquent, je fais l’hypothèse plausible que le chiffre 7 devrait être placé respectivement dans la cellule inférieure gauche du bloc 4 et le chiffre 6 dans la cellule supérieure droite.

Mais pour l’instant, j’accepte ce résultat uniquement comme ligne directrice possible pour tester d’autres options. Et je porte surtout attention au numéro 59 dans la cellule du 4ème bloc. Il peut y avoir soit le chiffre 5, soit le chiffre 9. Neuf promet de détruire de nombreux nombres supplémentaires, c'est-à-dire simplifier la suite de la résolution du problème, et je commence par cette option. Mais assez vite j’arrive à une « impasse », c’est-à-dire Ensuite, je dois refaire un choix et qui sait combien de temps mon choix sera vérifié. Je suppose que si neuf avait vraiment été le bon choix, Incala n'aurait guère laissé en vue une option aussi évidente, même si le mécanisme de son programme aurait pu permettre une telle erreur. En général, d'une manière ou d'une autre, j'ai décidé de vérifier d'abord soigneusement l'option avec le numéro 5 dans la cellule avec le numéro 59.

Mais plus tard, lorsque j'ai résolu le problème, pour ainsi dire, pour me débarrasser de ma conscience, je suis néanmoins revenu à l'option avec le chiffre 9 afin de déterminer combien de temps il faudrait pour la vérifier. Cela n'a pas pris beaucoup de temps pour vérifier. Lorsque j'ai eu le chiffre 6 dans la cellule supérieure droite du bloc 4, comme prévu selon le point de référence présélectionné, alors le chiffre 19 est apparu dans la cellule centrale droite (6 sur 169 ont été supprimés). J'ai choisi le chiffre 9 dans cette cellule pour des tests plus approfondis et suis rapidement arrivé à un résultat contradictoire, c'est-à-dire : le choix de neuf est incorrect. Ensuite, je choisis le numéro 1 et vérifie à nouveau ce qui en ressort.

À un moment donné, j'arrive à la situation :

où encore une fois je dois faire un choix - le chiffre 2 ou 8 dans la cellule supérieure centrale du bloc 4. Je coche les deux options (2 et 8) et dans les deux cas je me retrouve avec un résultat contradictoire (ne répondant pas à la condition Sudoku) . Je pourrais donc cocher l’option avec le chiffre 9 dans la cellule inférieure du milieu du bloc 4 dès le début et cela ne prendrait pas beaucoup de temps. Mais comme je l'ai déjà dit, j'ai quand même opté pour le chiffre 5 dans la cellule mentionnée. Cela m'a conduit au résultat suivant :

L'emplacement des chiffres 4 et 7 dans les trois premières colonnes (colonnes) indique qu'ils tournent de manière synchrone, ce qui était réellement attendu lors du choix du chiffre 7 pour la cellule inférieure gauche du 4ème bloc. Dans ce cas, un deux ou un neuf, que l'un d'entre eux soit le chiffre requis dans la cellule centrale gauche de ce bloc, doit donc se déplacer de manière asynchrone avec la paire 4 et 7. Dans ce cas, j'ai donné la préférence au chiffre 2, puisqu'il a « promis » d'éliminer de nombreux chiffres supplémentaires des numéros de cellule et, par conséquent, de vérifier rapidement l'admissibilité de cette option. Et neuf ont rapidement conduit à une impasse - cela a nécessité la sélection de nouveaux numéros. Ainsi, dans la cellule centrale gauche du bloc avec le numéro 29, j'ai inscrit, à mon avis, le numéro le plus préférable - 2. Le résultat est le suivant :

Ensuite, j'ai dû encore une fois faire un choix semi-arbitraire : j'en ai choisi deux dans la cellule avec le numéro 26 dans le neuvième bloc. Pour ce faire, il suffisait de remarquer que 5 et 2 dans les trois lignes inférieures tournent de manière synchrone, puisque 5 ne tournait de manière synchrone ni avec 1 ni avec 6. Certes, 2 et 1 pouvaient également tourner de manière synchrone, mais pour une raison quelconque, ce n'est certainement pas le cas. Je me souviens - j'ai choisi 2 au lieu du chiffre 26, peut-être parce que cette option, à mon avis, a été rapidement cochée. Cependant, il restait déjà peu d’options et il était possible de vérifier rapidement chacune d’entre elles. Il était également possible, au lieu de l'option avec deux, de supposer que les nombres 7 et 8 tournent de manière synchrone dans les trois dernières colonnes (colonnes), et il en résulte que dans la cellule supérieure gauche du 9ème bloc, il ne pouvait y avoir que le chiffre 8, qui conduit également à une solution rapide au problème.

Il faut dire que le problème d'Arto Incal ne permet pas une solution purement logique à la portée d'une personne ordinaire - c'est ainsi qu'il est prévu - mais il permet néanmoins de remarquer quelques options prometteuses pour la recherche à travers d'éventuelles substitutions de nombres et de manière significative réduire cette recherche. Essayez de démarrer la recherche à partir de positions autres que celles de cet article, et vous verrez que presque toutes les options mènent très rapidement à une impasse et que vous devez faire de plus en plus de nouvelles hypothèses concernant la sélection ultérieure de substitutions de nombres appropriées. Il y a environ deux mois, j'ai déjà essayé de résoudre ce problème, sans avoir la préparation que j'ai décrite dans les articles précédents. J'ai vérifié dix options pour sa solution et j'ai abandonné d'autres tentatives. La dernière fois, étant déjà mieux préparé, j'ai résolu ce problème pendant une demi-journée ou un peu plus, mais en réfléchissant en même temps au choix de mon point de vue des options les plus indicatives pour les lecteurs et aussi à une réflexion préliminaire sur le texte du futur article. Et le résultat final de la solution était le suivant :

En fait, cet article n'a aucune signification indépendante, il est écrit uniquement pour illustrer comment les compétences acquises et les considérations théoriques décrites dans les articles précédents permettent de résoudre des problèmes assez complexes. Et les articles, je vous le rappelle, ne portaient pas sur le Sudoku, mais sur les mécanismes de résolution de problèmes en utilisant le Sudoku comme exemple. Les sujets, quant à moi, sont complètement différents. Cependant, comme le Sudoku intéresse beaucoup, j'ai donc décidé d'attirer l'attention sur une question plus importante qui ne concerne pas le Sudoku lui-même, mais la résolution de problèmes.

Pour le reste, je vous souhaite de réussir à résoudre tous vos problèmes.

Vérifiez s'il y a de grands carrés sur le terrain avec un numéro manquant. Vérifiez chaque grand carré et voyez s’il y en a un auquel il manque juste un chiffre. Si un tel carré existe, il sera facile à remplir. Déterminez simplement lequel des nombres de un à neuf manque.

• Par exemple, un carré peut contenir des nombres de un à trois et de cinq à neuf. Dans ce cas, il n'y a pas de quatre qui doivent être insérés dans une cellule vide.

Vérifiez s’il manque un seul chiffre dans des lignes ou des colonnes. Parcourez toutes les lignes et colonnes du puzzle pour voir s'il y a des cas où il manque un seul chiffre. S'il existe une telle ligne ou colonne, déterminez quel nombre de la ligne de un à neuf manque et écrivez-le dans la cellule vide.

• Si la colonne de nombres contient des nombres de un à sept et neuf, il devient alors clair qu'il manque un huit, c'est ce qui doit être saisi.