Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

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 Profil Dlzlogicre : 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
weierstrass
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
lafol Moderateur
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.

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

Il en existe d'ailleurs en couleurs, autrement plus amusants à résoudre ....

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

Merci du renseignement, je ne connaissais pas.

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !