Niveau algorithmique

Algorithme pour remplir un tableau de cases N&B sous contraintes

Posté par
dedef 29-10-14 à 15:52

Bonjour,

Je dois remplir un carré de 29x29 avec des cases blanches et noires. Il y a à peu près autant de cases noires que de blanches. Pour chaque ligne et colonne je possède l'ordonnancement des séquences de cases noires : par exemple, 1325611 signifie que dans la ligne ou colonne concernée j'ai dans l'ordre, 1 noire puis 3 noires consécutives, puis 2 noires consécutives ... . Il y a toujours à minima 1 case blanche entre 2 séquences de cases noires, mais je ne sais rien de plus sur les cases blanches!

Je pense avoir tiré le maximum de ma pauvre cervelle pour identifier tout ce qui est certain (1/4 des cases noires). Il va donc falloir que je commence le grand jeu des hypothèses? Mais avant, je voudrais savoir si quelqu'un a une idée d'algorithme programmable par exemple sous Maple, pour éviter l'utilisation de la "force brute"?

Merci d'avance.

À titre d'exemple, simple, pour un carré de 5x5, lignes A à E et colonnes a à e, les informations ressemblent à :
A 1
B 21
C 3
D 11
E 111
a 11
b 3
c 111
d 2
e 2

Posté par re : Algorithme pour remplir un tableau de cases N&B sous contra 29-10-14 à 17:40

Bonjour,
C'est original votre problème.

Dans votre exemple, la ligne E est parfaitement définie.
Moi, je commencerais par la ligne ou la colonne qui est la mieux définie, ou totalement définie.
Je pense que chaque case devrait avoir 3 états possibles B (blanche) N (noire) I (ignoré) et peut-être une information par ligne et par colonne ou vous pourrez mettre par exemple "déjà essayé" "déjà trouvé" ou je ne sais quoi.
Si j'ai bien compris vous avez un fichier de données. Vous pouvez me l'envoyer, ce truc m'amuse.

Posté par re : Algorithme pour remplir un tableau de cases N&B sous contra 30-10-14 à 13:21

Bonjour,
on peux commencer à utiliser les règles de résolution classique du hanjie, pour les mêler à l'utilisation de la force brute...
L'enjeu est d'arriver à les "mathématiser"...
Par exemple
si on note $x_1,x_2,x_3,...,x_k$ les k nombres caractérisant une ligne, si la ligne à une longueur n alors:
si $x_1+x_2+...+x_k+k-1+max(x_1,...,x_k)>n,$ alors on peut placer des cases certaines...
$\forall x_i /x_1+x_2+...+x_k+k-1+x_i>n, \;\;\text{notons}\;\; d = x_1+x_2+...+x_k+k-1+x_i-n$
alors les cases $x_1+x_2+...+x_i+i-1 ,x_1+x_2+...+x_i+i-2,...,x_1+x_2+...+x_i+i-d-1$ sont noires

si une case noire jouxte le bord droit ou haut (respectivement gauche ou bas), alors les cases 1,2,3,...,x_1 sont noires (respectivement les cases n, n-1,..n-x_1+1 sont noires)

Posté par re : Algorithme pour remplir un tableau de cases N&B sous contra 30-10-14 à 14:21

Bonjour
ça n'a rien d'original : c'est le jeu de Hanjie, ça se trouve dans les magazines de jeux vendus dans les gares .....

plus connus en France sous le nom de logimage, peut-être ?
il est d'ailleurs fort possible qu'il existe des solveurs en ligne.