Un type de puzzle Sudoku légèrement différent

Aug 19 2020

L'image suivante montre deux Sudokus valides. Le premier a été copié textuellement sur Wikipédia, et le second a été obtenu en tournant de 90 degrés.

Deux Sudokus valides distincts doivent différer d'au moins quatre cellules. Étant donné un Sudoku terminé, un «mouvement» légal consiste à changer exactement quatre cellules pour former une autre grille de Sudoku.

Est-il possible de transformer la première grille en deuxième grille en utilisant uniquement des mouvements légaux?

(pour un crédit partiel: pouvez-vous réussir si les mouvements légaux permettaient de changer jusqu'à 6 cellules au lieu de 4?)

Réponses

Glorfindel Aug 19 2020 at 17:59

Observation:

Prenez par exemple le 5 en haut à gauche. Pour faire un coup valide qui change ce nombre, le 5 doit réapparaître ailleurs dans la même ligne, la même colonne et le même carré 3x3, donc cela définit deux ou trois autres cellules qui changent beaucoup.
Si vous choisissez trois autres cellules, celle du carré 3x3 a maintenant deux 5 dans la ligne et la colonne, donc cela ne fonctionne pas.
Ainsi, la cellule que vous choisissez pour la ligne ou la colonne doit également être dans le carré 3x3, et la quatrième cellule que vous modifiez doit former un rectangle avec le 5 en haut à gauche et les deux autres cellules que vous avez choisi de changer. De plus, les coins opposés du rectangle ont la même valeur. Un exemple où cela est possible est le rectangle de 5s et 4s formé sur la septième ligne et la huitième rangée, la quatrième et la neuvième colonne.
Le problème est qu'une telle opération, si elle existe dans la grille, signifierait que la grille n'a plus de solution unique, à moins que l' un des indices initiaux n'utilise l'une de ces cellules. Donc, ces situations sont relativement rares, et il est peu probable qu'un sudoku aléatoire puisse être transformé en un sudoku où (presque) toutes les valeurs ont changé, mais je n'ai pas encore de preuve.