10. Additions croisées


Fichier source: p10_eq##.*

Les jeux de nombres ont depuis longtemps passionné et divertit les gens de tout âge. Pour qu'un jeu connaisse du succès, il doit être simple à comprendre, donc ne pas utiliser d'opérations mathématiques complexes. C'est précisément dans cette optique que le jeu des additions croisées, une variante des célèbres carrés magiques, a été créé.

Problème

Vous devez concevoir et réaliser un logiciel qui résout des grilles d'additions croisées.

Voici un exemple de grille non-résolue:

Le but du jeu est de compléter les additions, verticalement et horizontalement, en sachant que:

Les nombres dans les cases grises représentent la somme des chiffres à inscrire dans les cases blanches, en suivant le sens des flèches.
On utilise seulement les chiffres de 1 à 9 (pas de zéro).
On ne peut pas utiliser deux fois le même chiffre dans une addition.
La même séquence de chiffres, quel qu'en soit l'ordre, ne peut apparaître qu'une seule fois dans la grille. Par exemple, si la somme 8 en trois chiffres apparait deux fois dans la grille, l'une des combinaisons sera 8=1+2+5 et l'autre sera obligatoirement 8=1+3+4 .

Par déduction logique, on trouve qu'il n'y a toujours qu'une seule et unique bonne réponse pour chaque case.

La grille a toujours 8 (huit) cases en largeur par 10 (dix) en hauteur.

La solution unique en serait:

L'entrée

L'entrée est un fichier appelé p10.ent . Le fichier est constitué d'une séquence de groupes de 6 nombres entiers à raison de 1 (un) groupe par ligne. Chaque groupe représente une case. Les nombres entiers dans un groupes sont séparés par un espace.

Un groupe se compose comme suit: F V G D H B où:

F vaut 2 si on a affaire à une case grise (sans flèche et sans intérêt),

1 si on a affaire à une case fléchée et

0 si on a affaire à une case dans laquelle on doit écrire un nombre.

V est la valeur du nombre à écrire dans la case. Dans le fichier d'entrée, cette valeur sera zéro (0) !!!

G est la somme associée à la flèche pointant vers la gauche si la case est fléchée. G vaudra zéro (0) si la case n'est pas une case fléchèe ou s'il n'y a pas de flèche vers la gauche dans la dite case.

D, H et B ont la même signification que G sauf qui donnent de l'information sur les flèches vers la droite, vers le haut et vers le bas, respectivement.

Les cases, au nombre de 80, sont listées de gauche à droite, puis de haut en bas, c'est-à-dire comme si on énoncait les mots d'une page de livre.

La sortie

Elle sera constituée d'un fichier appelé p10.sor qui décrit la grille une fois résolue, dans le même format que le fichier d'entrée. C'est à dire que p10.sor est pareil à p10.ent sauf pour le deuxième nombre (V pour valeur) des cases non fléchées. Au lieu de zéro, ce nombre devra être celui correspondant à la solution trouvée pour la case donnée.

Exemple

Fichier d'entrée:

2 0 0 0 0 0

1 0 0 0 0 13

1 0 0 0 0 4

1 0 0 0 0 22

2 0 0 0 0 0

1 0 0 0 0 16

1 0 0 0 0 22

1 0 0 0 0 17

1 0 0 13 0 0

0 0 0 0 0 0

1 0 0 23 0 0

0 0 0 0 0 0

1 0 0 7 0 0

0 0 0 0 0 0

1 0 0 11 0 8

0 0 0 0 0 0

2 0 0 0 0 0

1 0 0 0 0 10

1 0 0 29 0 24

0 0 0 0 0 0

1 0 0 0 0 14

1 0 0 13 0 0

0 0 0 0 0 0

1 0 0 7 0 15

0 0 0 0 0 0

1 0 0 16 0 0

0 0 0 0 0 0

1 0 0 18 0 11

0 0 0 0 0 0

1 0 0 16 0 0

0 0 0 0 0 0

1 0 0 3 0 22

0 0 0 0 0 0

1 0 0 0 0 9

1 0 0 0 0 20

2 0 0 0 0 0

1 0 0 0 0 13

1 0 0 32 0 6

0 0 0 0 0 0

1 0 0 13 0 0

0 0 0 0 0 0

1 0 0 6 0 0

0 0 0 0 0 0

1 0 0 22 0 0

0 0 0 0 0 0

1 0 0 17 0 0

0 0 0 0 0 0

Fichier de sortie:

2 0 0 0 0 0

1 0 0 0 0 13

1 0 0 0 0 4

1 0 0 0 0 22

2 0 0 0 0 0

1 0 0 0 0 16

1 0 0 0 0 22

1 0 0 0 0 17

1 0 0 13 0 0

0 9 0 0 0 0

0 3 0 0 0 0

0 1 0 0 0 0

1 0 0 23 0 0

0 6 0 0 0 0

0 8 0 0 0 0

0 9 0 0 0 0

1 0 0 7 0 0

0 4 0 0 0 0

0 1 0 0 0 0

0 2 0 0 0 0

1 0 0 11 0 8

0 2 0 0 0 0

0 1 0 0 0 0

0 8 0 0 0 0

2 0 0 0 0 0

1 0 0 0 0 10

1 0 0 29 0 24

0 9 0 0 0 0

0 7 0 0 0 0

0 8 0 0 0 0

0 5 0 0 0 0

1 0 0 0 0 14

1 0 0 13 0 0

0 2 0 0 0 0

0 7 0 0 0 0

0 3 0 0 0 0

0 1 0 0 0 0

1 0 0 7 0 15

0 2 0 0 0 0

0 5 0 0 0 0

1 0 0 16 0 0

0 1 0 0 0 0

0 8 0 0 0 0

0 7 0 0 0 0

1 0 0 18 0 11

0 3 0 0 0 0

0 6 0 0 0 0

0 9 0 0 0 0

1 0 0 16 0 0

0 7 0 0 0 0

0 9 0 0 0 0

1 0 0 3 0 22

0 2 0 0 0 0

0 1 0 0 0 0

1 0 0 0 0 9

1 0 0 0 0 20

2 0 0 0 0 0

1 0 0 0 0 13

1 0 0 32 0 6

0 6 0 0 0 0

0 9 0 0 0 0

0 4 0 0 0 0

0 5 0 0 0 0

0 8 0 0 0 0

1 0 0 13 0 0

0 5 0 0 0 0

0 1 0 0 0 0

0 7 0 0 0 0

1 0 0 6 0 0

0 2 0 0 0 0

0 1 0 0 0 0

0 3 0 0 0 0

1 0 0 22 0 0

0 8 0 0 0 0

0 5 0 0 0 0

0 9 0 0 0 0

1 0 0 17 0 0

0 5 0 0 0 0

0 3 0 0 0 0

0 9 0 0 0 0

Correction et pointage

Le problème sera corrigé en soumettant votre programme à quatre fichiers d'entrée différents. Un fichier de test sera considéré comme réussi si le fichier de sortie présente une grille cohérente et dont toutes les cases blanches ont été remplies.


Nombre de fichiers réussis	Points accordés 



1				600 



2				800

Énoncés des problèmes