Sudoku 17 indices Moyen

Comment jouer à Sudoku 17 indices

Le Sudoku est un puzzle de placement de nombres basé sur la logique. L'objectif est de remplir une grille 9x9 avec les nombres 1 à 9, de sorte que chaque ligne, colonne et sous-grille 3x3 contienne les neuf nombres exactement une fois.

En 2009, Gary McGuire et son équipe ont prouvé que tout puzzle Sudoku comportant 16 indices doit avoir au moins deux solutions. Ils l'ont fait en utilisant une technique appelée "modèles morts".

Un modèle mort est une configuration Sudoku qui a deux solutions possibles ou plus. McGuire et son équipe ont découvert que tout puzzle Sudoku comportant 16 indices doit contenir au moins un motif mort. Par conséquent, ces énigmes doivent avoir au moins deux solutions.

Ce résultat a plusieurs implications. Premièrement, cela signifie qu’il n’existe pas de puzzle Sudoku à 16 indices avec une solution unique. Deuxièmement, cela signifie que n’importe quel puzzle Sudoku à 16 indices peut être résolu de plusieurs manières. Troisièmement, cela signifie qu'il existe un nombre infini de grilles de Sudoku à 16 indices.

Voici une explication plus technique de la preuve que les grilles de Sudoku doivent avoir au moins 17 indices pour avoir une solution unique :

La preuve commence par considérer un puzzle Sudoku comportant 16 indices. Nous pouvons considérer ce puzzle comme un ensemble de contraintes sur les nombres pouvant être placés dans les cases vides.

On peut alors utiliser une technique appelée « backtracking » pour tenter de trouver une solution à l’énigme. Le backtracking est un algorithme récursif qui essaie toutes les combinaisons possibles de nombres dans les carrés vides jusqu'à ce qu'il trouve une solution.

S’il existe une solution unique à l’énigme, alors revenir en arrière finira par la trouver. Cependant, s'il existe plusieurs solutions, un retour en arrière risque de ne jamais trouver de solution.

McGuire et son équipe ont utilisé le backtracking pour montrer que s'il existe un puzzle Sudoku à 16 indices avec une solution unique, alors il doit y avoir un moyen de démarrer l'algorithme de backtracking de telle manière qu'il trouve toujours la solution.
Ils ont alors montré que cela n’était pas possible. Pour ce faire, ils ont construit un ensemble de 16 indices qui mènent à un modèle mort. Ce modèle mort signifie qu'il y a deux solutions possibles au puzzle, et aucun moyen de démarrer l'algorithme de retour en arrière de telle manière qu'il trouve toujours la même solution.
Ce résultat montre que tout puzzle Sudoku à 16 indices doit avoir au moins deux solutions.