Created
January 4, 2023 14:21
-
-
Save Gro-Tsen/f96dbdf0e76586c16daad6473101d959 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
## Voir <URL: https://twitter.com/gro_tsen/status/1610641879216914432 > pour le contexte. | |
## Matrice des contraintes linéaires (la valeur [0] sert à encoder la | |
## contrainte somme et vaudra 1 sur toute solution, les valeurs [1] à | |
## [9] sont les cases du tableau avec [1] = nord-ouest, [2] = nord, | |
## [3] = nord-est, [4] = ouest, [5] = centre, [6] = est, [7] = | |
## sud-ouest, [8] = sud et [9] = sud-est): | |
mat = Matrix(ZZ,[(-19,1,1,0,1,1,0,0,0,0),(-19,0,1,1,0,1,1,0,0,0),(-19,0,0,0,1,1,0,1,1,0),(-19,0,0,0,0,1,1,0,1,1),(-45,1,1,1,1,1,1,1,1,1)]).transpose() | |
## Base échelonnée des solutions entières: | |
bas = mat.left_kernel().basis() | |
## Contraintes additionnelles sur une solution: | |
## Les valeurs sont tous les chiffres entre 1 et 9 inclus: | |
def isvalid(v): | |
return v[0] == 1 and sorted(v[1:10]) == list(range(1,10)) | |
## Le coin en nord-ouest ([1]) est le plus petit des quatre coins | |
## ([1],[3],[7],[9]), et la valeur nord ([2]) est plus petite que la | |
## valeur ouest ([4]), pour éliminer les symétries: | |
def isrepz(v): | |
return v[1]<v[3] and v[1]<v[7] and v[1]<v[9] and v[2]<v[4] | |
## Recherche exhaustive des solutions: | |
for i1 in range(1,10): | |
for i2 in range(1,10): | |
for i3 in range(1,10): | |
for i4 in range(1,10): | |
cand = bas[0] + i1*bas[1] + i2*bas[2] + i3*bas[3] + i4*bas[4] | |
# cand est l'unique solution entière ayant i1,i2,i3,i4 | |
# comme entrées aux cases [1],[2],[3],[4]. On vérifie | |
# qu'elle est valide et on l'imprime le cas échéant: | |
if isvalid(cand) and isrepz(cand): | |
print(cand[1:10]) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment