Programmation

Résolvez Sudoku avec la programmation entière

Posted by admin

Un puzzle 9 X9 SUDOKU a les lignes suivantes. Chaque ligne et colonne doit avoir les nombres entre 1 et 9 et chacune des cases intérieures doit avoir les nombres entre 1 et 9. Chaque numéro dans chaque colonne et ligne et dans chaque petite case ne peut apparaître qu’une seule fois.

Définissons Xijk pour que toutes les valeurs de I, j et k de 1 à 9 soient 1. Si la cellule (I, j) contient le nombre k où I, j et k sont tous compris entre 1 et 9. la ième ligne et j représente la jième colonne et k représente un entier entre 1 et 9. Lorsque X134 = 1, cela signifie que la cellule (1,3) contient le nombre 4. Cela signifierait également qu’aucun des autres éléments de la 1ère ligne ou de la 3ème colonne à l’exception de la cellule (1,3) ne peut être égal à 4.

Pour modéliser le SUDOKU, nous utiliserons un total de 729 variables.

Formulons maintenant algébriquement chacune des trois classes de règles.

Chaque ligne ne peut contenir qu’une seule fois un nombre compris entre 1 et 9.

Pour la première ligne, cette ligne apparaîtrait comme (appelée «Contrainte» en langage de programmation entier).

pour tout I de 1 à 9 et pour tout k de 1 à 9 (I est une représentation mathématique d’une variable de compteur)

somme (Xijk) pour tout j de 1 à 9 = 1;

Écrit sous forme développée pour la première ligne pour tout nombre compris entre 1 et 9

X111 + X121 + X131 + X141 + X151 + X161 + X171 + X181 + X191 = 1.

X112 + X122 + X132 + X142 + X152 + X162 + X172 + X182 + X192 = 1.

X113 + X123 + X133 + X143 + X153 + X163 + X173 + X183 + X193 = 1.

X114 + X124 + X134 + X144 + X154 + X164 + X174 + X184 + X194 = 1.

Ces équations suivent pour les variables commençant par X115 à X119.

De même, formulons des équations pour les lignes de n’importe quel nombre entre 1 et 9 qui n’apparaissent qu’une seule fois dans chacune des 9 colonnes.

Écrit en notation mathématique,

somme X pour tout j de 1 à 9 (pour tout I et k entre 1 et 9) = 1

Écrit sous forme développée pour quelques colonnes pour tout nombre compris entre 1 et 9

Colonne 1

X111 + X211 + X311 + X411 + X511 + X611 + X711 + X811 + X911 = 1.

X112 + X212 + X312 + X412 + X512 + X612 + X712 + X812 + X912 = 1.

X113 + X213 + X313 + X413 + X513 + X613 + X713 + X813 + X913 = 1.

Ceci doit être entré pour tous les autres nombres 4 à 9.

Colonne 2

X121 + X221 + X321 + X421 + X521 + X621 + X721 + X821 + X921 = 1.

X122 + X222 + X322 + X422 + X522 + X622 + X722 + X822 + X922 = 1.

X123 + X223 + X323 + X423 + X523 + X623 + X723 + X823 + X923 = 1.

Ceci doit être rempli pour tous les autres nombres de 4 à 9.

Représentons maintenant les petits carrés (3 x 3) pour un total de 9 carrés.

Donc, dans chaque carré 3 x 3, il ne peut y avoir qu’un 1 ou 2 ou 3 ou 4 ou 5 ou 6 ou 7 ou 8 ou 9 etc.

Les cellules se trouvent entre les colonnes (1 à 3) et les lignes (1 à 3), les colonnes (4 à 6) et les lignes (1 à 3) les colonnes (7 à 9) les lignes (1 à 3). Pour le même ensemble de colonnes, elles apparaissent également en lignes (4 à 6) et (6 à 9). Formulons donc les équations pour un seul carré entre les colonnes (1 à 3) et les lignes (1 à 3). Les variables de décision correspondantes pour le chiffre “1” sont (9 au total)

X111, X121, X131, X211, X221, X231, X311, X321, X331.

Formons l’équation que ce carré (3×3) ne contient qu’un seul “1”.

Donc l’équation est

X111 + X121 + X131 + X211 + X221 + X231 + X311 + X321 + X331 = 1.

L’équation ci-dessus impliquerait qu’une seule de ces 9 variables ou une seule de ces neuf cellules peut prendre la valeur 1.

De même, des restrictions doivent être faites pour le chiffre «2», le chiffre «3» et ainsi de suite jusqu’à 9.

Pour les problèmes de programmation avec des entiers, en plus des équations décrivant les contraintes, des contraintes entières doivent également être imposées à chaque variable, de sorte que lorsque le système d’équations est résolu, on obtient un 0 ou un 1 comme solution à la variable Xijk.

L’équivalent géométrique d’un problème de programmation linéaire avec une fonction objectif et certaines contraintes n’est rien de plus qu’un polyèdre dimensionnel où n représente le nombre de contraintes dans le problème. Habituellement, la solution optimale sera trouvée sur les sommets du polytope, également les règles d’une méthode telle que SIMPLEX exigent que le polytope soit convexe afin que l’on puisse marcher de haut en haut le long des bords et trouver la solution optimale.

Imposer des contraintes entières signifierait que la solution optimale ne se trouve pas sur les sommets du polytope, car une solution trouvée au sommet peut ne pas être un entier. Donc si vous prenez en compte que la solution optimale doit être 0 ou 1, cela signifie que la solution sera géométriquement quelque part dans la plage des possibles du polytope convexe et sur l’une des nombreuses droites provenant de l’hyperplan équivalent à Xi jk avec valeurs entières.

A noter que la solution ci-dessus utilisait 729 variables de décision et 81 restrictions de conduite. 81 contraintes de colonne et 729 contraintes de petit carré avec un total de 901 contraintes. Il peut y avoir de nombreuses fonctions objectives, mais on peut formuler une fonction objective en trouvant le minimum de (somme des 729 variables). On peut réduire le nombre de contraintes en trouvant une certaine redondance.

Ces équations ci-dessus ne peuvent pas être résolues à l’aide de langages de programmation tels que Visual Basic, Pascal ou C.Les problèmes de programmation d’entiers peuvent être résolus à l’aide d’un logiciel d’optimisation tel que l’optimiseur CPLEX, le complément Excel pour résoudre les problèmes de programmation linéaire, Lingo, etc.

Leave A Comment