J'ai récemment obtenu une nouvelle application Sudoku qui produit des Sudoku très durs, qui ne peuvent pas être résolus en utilisant les stratégies standard. J'ai donc dû en apprendre quelques nouveaux. L'une de ces stratégies est la stratégie Y-Wing . Il est classé sous "Tough Strategies", mais ce n'est pas si difficile.
Exemple
Pour cette stratégie, seules 4 cellules sont importantes. J'ai donc ignoré toutes les autres cellules des images.
Nous examinons tous les candidats pour chaque cellule. Dans l'exemple suivant, nous avons une cellule avec les candidats 3 7(cela signifie que nous avons déjà rejeté les candidats 1 2 4 5 6 8 9, par exemple parce qu'il y en a un 1dans la même ligne, un 2dans la même case 3x3, ...), une cellule avec les candidats 6 7, une cellule avec les candidats 3 6et une cellule avec les candidats 2 6. La stratégie Y-Wing suggérera que le 6peut être retiré des candidats de la cellule carrément, ne laissant qu'un 2candidat, que vous pouvez remplir. Nous avons donc trouvé un nombre correct et sommes un pas de plus dans la résolution du Sudoku complet.
Pourquoi l' 6enlever?
Explication
Supposons que le 6est le nombre correct pour la cellule pure et simple. Maintenant, il y a un 6dans cette colonne, donc nous pouvons supprimer le 6des candidats de la cellule en haut à droite, ne laissant qu'un 7, que nous pouvons remplir. La même chose se produit avec la cellule en bas à gauche. Nous pouvons supprimer le 6et remplir le 3. Maintenant, si nous regardons la cellule en haut à gauche, nous obtenons une contradiction. Parce que maintenant, il y a déjà un 7dans la même ligne et un 3dans la même colonne, donc nous pouvons supprimer le 7et le 3des candidats, ne laissant aucun candidat du tout. Ce qui n'est clairement pas possible. Par conséquent, le 6 ne peut pas être le numéro correct de la cellule carrément.
Plus précisément: si nous avons 4 cellules avec les candidats [A B] [A C] [C D] [B C](dans cet ordre ou circulaire tourné) et les cellules sont connectées (via la même ligne, la même colonne ou la même case 3x3) dans un cercle (la cellule 1 est connectée à la cellule 2, qui est connecté à la cellule 3, qui est connecté à la cellule 4, qui est connecté à la cellule 1), que vous pouvez supprimer Cde la [C D]cellule. Il est essentiel que les trois cellules [A B], [A C]et [B C]ne contiennent que deux candidats chacun. Différemment la cellule [C D], qui peut contenir plus ou moins ( Dpeut être zéro, un ou plusieurs candidats).
Notez que j'ai explicitement dit qu'ils peuvent être connectés dans les deux sens. Dans l'exemple suivant, vous pouvez voir à nouveau la stratégie appliquée. Mais cette fois, les 4 cellules ne forment pas un rectangle. Les cellules en bas à gauche et en bas sont simplement connectées, car elles sont dans la même boîte 3x3. Y-Wing dit que nous pouvons supprimer le 1candidat de la cellule en haut à gauche. Cette fois, il reste encore 2 candidats dans cette cellule, nous n'avons donc pas trouvé de nouveau numéro correct. Mais néanmoins, la suppression du 1peut ouvrir la porte à différentes stratégies.
Si vous voulez plus d'informations sur la stratégie ou si vous voulez quelques exemples supplémentaires, visitez sudokuwiki.org .
Spécifications du défi
Vous recevrez 4 listes en entrée, représentant les candidats des cellules. Les quatre cellules sont connectées comme un cercle (la cellule 1 est connectée à la cellule 2, qui est connectée à la cellule 3, qui est connectée à la cellule 4, qui est connectée à la cellule 1). Vous pouvez supposer que chaque liste est triée par ordre croissant.
Votre travail consiste à supprimer un candidat (en appliquant la stratégie Y-Wing) et à renvoyer les listes de candidats résultantes dans le même ordre. Si vous ne pouvez pas appliquer la stratégie, renvoyez simplement les mêmes listes de candidats.
S'il existe deux solutions possibles (vous pouvez supprimer A de la cellule B ou supprimer C de la cellule D), ne renvoyez qu'une seule solution. Peu importe lequel.
L'entrée peut être dans n'importe quel format natif de liste ou de tableau. Vous pouvez également utiliser une liste de listes ou quelque chose de similaire. Vous pouvez recevoir l'entrée via STDIN, l'argument de ligne de commande, l'invite ou l'argument de fonction et renvoyer la sortie via la valeur de retour ou simplement en imprimant sur STDOUT.
C'est du code-golf. Le code le plus court (en octets) gagne.
Cas de test
[3 7] [6 7] [2 6] [3 6] => [3 7] [6 7] [2] [3 6] # Example 1
[6 7] [2 6] [3 6] [3 7] => [6 7] [2] [3 6] [3 7] # Example 1, different order
[2 6] [3 6] [3 7] [6 7] => [2] [3 6] [3 7] [6 7] # Example 1, different order
[3 6] [3 7] [6 7] [2 6] => [3 6] [3 7] [6 7] [2] # Example 1, different order
[1 2 8] [1 8] [8 9] [1 9] => [2 8] [1 8] [8 9] [1 9] # Example 2
[3 8] [4 8] [3 4 8] [3 4] => [3 8] [4 8] [3 8] [3 4]
[1 3 6 7 8] [3 8] [3 4] [4 8] => [1 3 6 7] [3 8] [3 4] [4 8]
[7 8] [7 8] [4 7] [4 8] => [7 8] [8] [4 7] [4 8] or [7] [7 8] [4 7] [4 8]
[4 7] [7 8] [4 8] [4] => [4 7] [7 8] [4 8] [] # Fictional example
[3 7] [2 6] [6 7] [3 6] => [3 7] [2 6] [6 7] [3 6] # Y-Wing can't be applied here
[4 7] [2 7 8] [4 8] [1 4] => [4 7] [2 7 8] [4 8] [1 4] # -||-
7 8sont les candidats pour la première et la deuxième cellule. La stratégie Y-Wing peut toujours être appliquée.Réponses:
CJam, 90 octets
Ugghhh, c'est trop long à cause de la contrainte que les 3 autres cellules ne doivent avoir que 2 candidats.
Cela attend l'entrée comme une liste de liste au format CJam. Par exemple:
donne une sortie dans une liste CJam de format de liste:
Ajoutera une explication une fois que j'aurai fini de jouer au golf ..
Essayez-le en ligne ici ou essayez toute la suite de tests ici .
la source
Mathematica,
124110 octetsExemples:
la source