1

yop,

J'ai une petite question d'algo pour laquelle les seules solutions que j'ai testées jusqu'à maintenant sont affreusement lentes. Je ne vois pas de méthode efficace et je ne sais pas s'il en existe, mais peut-être que ça parlera à certains d'entre vous.

Imaginons que je veuille générer une map de tiles. Je veux que le placement de ces tiles soit cohérent, par exemple si l'un d'eux représente une route verticale, le bord inférieur de celui qui sera placé juste au-dessus doit "continuer" cette route (il peut donc s'agir du même tile de route verticale, ou bien une route qui part du bas et tourne à gauche ou à droite, par exemple). On peut donc imaginer une liste de règles : à chaque tile est associée la liste de ceux qui peuvent se trouver à proximité (ceux pouvant être à gauche, ceux pouvant être à droite, etc).

Techniquement rien de bien compliqué pour l'instant, mais le problème arrive ici : comment générer aléatoirement une map de tiles qui respecte toutes ces contraintes ? Si on place un peu n'importe quoi de façon aléatoire, et même si on prend la peine de noter à chaque nouveau tile ceux qui du coup deviennent invalides sur les cases adjacentes, on a de grandes chances de se retrouver tôt ou tard bloqué (parceque deux tiles éloignés auront des contraintes incompatibles, et que la case en conflit ne pourra donc rien accepter qui satisfasse à la fois les deux règles concernées). C'est difficilement imaginable aussi de construire un algo récursif qui, en cas de blocage, annule son dernier coup et retente ailleurs : pour peu que le tile qui pose problème soit l'un des premiers placés, on peut attendre longtemps que ça finisse.

Auriez-vous des idées ?

[edit] Voyez le post ./9 pour un schéma explicatif
avatar
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)

2

Si ce n'est juste une placement de "routes" sur un tableau, une maniere simple est de prendre un point de départ et de tracer aléatoirement la route sur le tableau avec quelques regles si tu voix ce que je veux dire.

De toute maniere c'est faisable de maniere plus ou moins optimisé vu que certain jeux (types RTS) sont capable de generer "aléatoirement" des cartes cohérentes...

Apres rien n'empeche de tricher un peu et de pas faire reelement de maniere aléatoire, du moins pas sur toute la ligne
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

3

une approche façon "solveur sudoku" devrait être possible avec un grille de soluces possibles, pour chaque "tentative" tu peuples la liste des choix acceptés lrtb dans la grille de soluce possibles. ainsi, tu peux savoir directement quoi placer en diagonale en plus des placements adjacents que tu as déjà décrits
avatar
Webmaster du site Ti-FRv3 (et aussi de DevLynx)
Si moins de monde enculait le système, alors celui ci aurait plus de mal à nous sortir de si grosses merdes !
"L'erreur humaine est humaine"©Nil (2006) // topics/6238-moved-jamais-jaurais-pense-faire-ca

4

./2 : rah c'est pour ça que je n'aime pas donner trop d'exemples, pour éviter que les gens ne les confondent avec le cas général ^^ l'algo qui m'intéresse est celui décrit dans le post, donc il ne doit pas être limité seulement au placement de routes (ou de quoi que ce soit d'autre de spécifique), sinon ça serait en effet beaucoup plus simple

./3 : pas compris ?
avatar
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)

5

./4 ben disont que a pars pour faire des routes ou choses du genre, je sais pas ce qu'est sensé représenter ton tilemap, mais si c'est pour prendre le cas d'un RTS par exemple, contruire un camp, ou des routes, le reste ne demande pas forcement des contraites comme tu le demande. Apres ça dépend de ce que tu fait, mais par exemple un arbre peut ne tenir que sur une seule case etc... enfin, je suis pas sur de toute maniere qu'il soit possible d'avoir un algo généraliste, mais que des algos de "cas particuliers"



Sinon si c'est juste une ensemble de regles comme tu le dérit en ./1, tu tire le premier tile de maniere aléatoire dans le coin 0;0 et tu construit case apres case en choisisant aléatoirement dans les tiles qui sont authorisé a coté de maniere séquentiel, et si tu tombe sur une case qui ne peut etre rempli (liste de case autorisé vide) tu selectionne un des 4 coté et tu regarde si on peu le changer pour un autre de valide, pour en permettre un dans la case ou tu est. Le problème c'est que c'est un algo plutot brutal, et mal adapté. C'est ce que propose Vince il me semble
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

6

Hum j'ai l'impression que ça dépend pas mal des contraintes que tu as... on pourrait imaginer de concevoir les tiles de telle manière qu'il en existe toujours un qui va dans un trou, mais apparemment c'est pas ton cas ^^.

Sinon plutôt que d'avoir des listes de tiles qui peuvent se trouver à proximité j'aurais plutôt vu des listes de bords : chaque tile a 4 bords, ou 6 ou 3 enfin peu importe, et il y a un nombre fini de bords possibles en tout. Deux tiles adjacents doivent avoir le même bord (dans le même sens mais ça simplifie pas mal si les bords sont symétriques à mon avis ^^). Ensuite tes différents modèles de tiles indiquent quels sont les différentes combinaisons de bords possibles.

À partir de là, tu peux imaginer de remplir ta map ligne par ligne de haut en bas, genre ; à supposer que tu n'as pas de contraintes sur le bord de la map tu auras pour la plupart des tiles deux bords adjacents imposés (le bord gauche et le bord supérieur) et deux bords libres. Donc pour être sûr que c'est possible il suffit que toutes les combinaisons de deux bords adjacents existent dans ton ensemble de tiles, ce qui est peut-être une contrainte raisonnable ? par contre si tu as des contraintes en bord de map ça ne résout pas vraiment le problème, sur la dernière ligne tu auras trois côtés imposés, et quatre pour le dernier tile, mais bon c'est peut-être une piste ^^
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

7

Godzil (./5) :
Sinon si c'est juste une ensemble de regles comme tu le dérit en ./1, tu tire le premier tile de maniere aléatoire dans le coin 0;0 et tu construit case apres case en choisisant aléatoirement dans les tiles qui sont authorisé a coté de maniere séquentiel, et si tu tombe sur une case qui ne peut etre rempli (liste de case autorisé vide) tu selectionne un des 4 coté et tu regarde si on peu le changer pour un autre de valide, pour en permettre un dans la case ou tu est. Le problème c'est que c'est un algo plutot brutal, et mal adapté.

Le problème avec cette méthode, c'est que si tu commences toujours par le coin 0;0 (et qu'en plus tu te déplaces toujours de la même façon) tu conditionnes déjà énormément le résultat : les premiers tiles seront placés de façon totalement libre, alors que les suivants vont avoir de plus en plus de contraintes. De fil en aiguille, certains tiles "difficiles à placer" (avec des contraintes rarement satisfaites) ne se retrouveront jamais en bas à droite de la map, contrairement à certains tiles relativement génériques qu'on va voir tout le temps.
Sally (./6) :
Hum j'ai l'impression que ça dépend pas mal des contraintes que tu as... on pourrait imaginer de concevoir les tiles de telle manière qu'il en existe toujours un qui va dans un trou, mais apparemment c'est pas ton cas ^^.

Non effectivement, ça simplifierait pas mal le problème, mais toujours pour rester dans le cas général rien ne dit qu'il existerait un tile "universel" (d'ailleurs en pratique c'est difficilement réalisable... si on imagine une carte à la heroes of might & magic, je ne vois pas quel tile pourrait se placer aussi bien au milieu d'une plaine que dans une chaine de montagnes ou en plein dans l'eau ^^)

Sinon pour les bords, c'est une piste intéressante mais ta méthode de remplissage a le même défaut que celle proposée par Godzil. En remplissant aléatoirement, on se retrouve face à un autre problème : les bords seront placés, oui, mais existera-t-il les tiles qui possèdent des bords compatibles avec la configuration qu'on a générée ? (une fois que 2, 3 ou pire 4 bords sont définis, il y a très peu de chances de trouver un tile dont chaque coté corresponde).
avatar
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)

8

Le langage E permet de générer des données aléatoires en fonction de contraintes. Il doit y avoir d'autres outils de vérification fonctionnelle qui doit pouvoir faire ce genre de chose.
C'est une piste, maintenant je ne sais pas si c'est adaptable à ton problème.
Tout ce qui passe pas par le port 80, c'est de la triche.

9

Pour illustrer un peu (même si vous aviez probablement déjà saisi, mais là j'ai du temps à perdre grin), voilà un petit schéma. En premier, mon jeu de tiles :

VD2U

Les règles associées sont simples : un tile peut être à coté d'un autre si leurs bords en commun partagent la même couleur. Vous remarquerez qu'il manque (volontairement) le tile tout bleu. Maintenant admettons qu'à l'étape N - 1 de mon algo, j'en suis ici :

XCNg

Je suis bloqué. En respectant les contraintes, je ne peux pas remplir la dernière case. Et pourtant tout ce que j'ai placé jusqu'ici respectait parfaitement toutes les règles, l'objectif serait donc de se "rendre compte" le plus tôt possible que je vais vers une impasse puisqu'avec la façon naïve ce n'est que vers la fin que le problème apparaît.
avatar
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)

10

Zephyr (./7) :
si on imagine une carte à la heroes of might & magic, je ne vois pas quel tile pourrait se placer aussi bien au milieu d'une plaine que dans une chaine de montagnes ou en plein dans l'eau ^^
Ah oui bien sûr mais je n'imaginais pas UN tile universel, juste l'idée que pour 4 bords donnés il y a toujours un tile qui existe (mais bon c'est pas forcément évident quand même ^^)

Sinon quel est le défaut de ma méthode de remplissage exactement ? (s'il n'y a pas de contraintes en bord de map elle t'assure que tu n'auras jamais plus de deux bords — adjacents — qui sont imposés, tu es d'accord ?)
Après si certaines combinaisons de deux bords adjacents n'existent pas dans l'ensemble de tiles, ça signifie qu'en suivant cette méthode de façon purement aléatoire ça risque de se bloquer, donc ça ne résout pas le problème bien sûr...
mais après j'ai l'impression que ça dépend très fortement de l'ensemble de tiles, si ça se trouve ton problème n'a aucune solution par exemple (pour un ensemble de tiles très mal choisi). En tous cas je n'ai pas d'autre idée, dans le cas général, que le backtracking pour le moment ^^ (mais il me semble que ma méthode de remplissage a des chances de minimiser le backtracking nécessaire, si l'ensemble de tiles n'est pas trop pourri)
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

11

Zephyr (./7) :
Non effectivement, ça simplifierait pas mal le problème, mais toujours pour rester dans le cas général rien ne dit qu'il existerait un tile "universel"

Sauf que dans le cas général c'est NP-complet, donc il vaudrait mieux que ta liste de contraintes soit pas totalement arbitraire...

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

12

Zeph, toi tu compte gagner a un jeu ou le seul moyen c'est de faire un algo NP complet comme le dit Popo ^^

D'ailleurs si je me souvient bien le jeu en question n'est pas solvable facilement via un algo, du moins pas en un temps realiste smile

(j'ai oublié le nom du concours par contre sorry)
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

13

./9 > bon ben dans ton exemple justement, les combinaisons de deux bords adjacents possibles sont rouge/rouge, rouge/bleu, bleu/rouge et bleu/bleu et elles sont représentées toutes les quatre, donc avec ma méthode de remplissage (ligne par ligne de gauche à droite et de haut en bas) ça marche ^^.

Pour que ça puisse foirer il faudrait retirer tous les tiles qui contiennent une combinaison donnée, par exemple rouge/bleu, donc... tous sauf le premier, mauvais exemple triso
autre exemple, rouge/rouge, si tu retires les tiles 2, 3, 4, 5, 6, 8, 9 et 11 mon remplissage ne marche plus à tous les coups. (Mais bon évidemment sur un exemple avec seulement deux types de bord il faut être super restrictif pour que ça marche pas ^^)
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

14

Trouver des critères de validation pour les contraintes fait partie du "jeu" oui (puisqu'il suffit de deux règles mal fichues pour qu'aucune solution n'existe, de toutes façons), mais avoir forcément un tile pour chaque combinaison de bords n'est pas réaliste (si je prends une de mes planches de tiles au pif, il doit y avoir plus d'une centaine de bords différents, je vous laisse calculer le nombre de tiles que ça implique pour qu'elle soit complète).

[cross] ./13 : il faut imaginer qu'elles ne peuvent raisonnablement pas toutes exister, ces combinaisons :/ (c'est juste parceque l'exemple est basique que finalement ça reste faisable)
avatar
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)

15

géré dans deux tableaux différent, on a ça :
au départ, tableau vide 1,2,3,4,5,6,7,8
1,2,3,4,5,6,7,81,2,3,4,5,6,7,81,2,3,4,5,6,7,8
1,2,3,4,5,6,7,81,2,3,4,5,6,7,81,2,3,4,5,6,7,81,2,3,4,5,6,7,8
1,2,3,4,5,6,7,81,2,3,4,5,6,7,81,2,3,4,5,6,7,81,2,3,4,5,6,7,8
1,2,3,4,5,6,7,81,2,3,4,5,6,7,81,2,3,4,5,6,7,81,2,3,4,5,6,7,8

première case, je met 4 et j'en déduis les possibilités pour les cases adjacentes 4
3,5,6,71,2,3,4,5,6,7,81,2,3,4,5,6,7,8
1,2,3,71,2,3,4,5,6,7,81,2,3,4,5,6,7,81,2,3,4,5,6,7,8
1,2,3,4,5,6,7,81,2,3,4,5,6,7,81,2,3,4,5,6,7,81,2,3,4,5,6,7,8
1,2,3,4,5,6,7,81,2,3,4,5,6,7,81,2,3,4,5,6,7,81,2,3,4,5,6,7,8

si je pars en diagonale pour la prochaine, il faut qu'elle ait au dessus d'elle 3,5,6 ou 7 et à sa gauche 1,2,3 ou 7, ça m'offre donc le choix entre "tout"
prenons le 3, pour le coup, ça va réduire mes choix pour les deux cases adjacentes communes 4
3,5,6,7 et 1,4,5,7 => 5,71,2,3,4,5,6,7,81,2,3,4,5,6,7,8
1,2,3,7 et 2,4,6,7 => 2,731,2,4,81,2,3,4,5,6,7,8
1,2,3,4,5,6,7,84,5,6,81,2,3,4,5,6,7,81,2,3,4,5,6,7,8
1,2,3,4,5,6,7,81,2,3,4,5,6,7,81,2,3,4,5,6,7,81,2,3,4,5,6,7,8

et ainsi de suite, après à toi de voir si c'est plus simple pour toi de progresser par diagonales ou par lignes
légende :
3 : tile posée
4 : tile possible
tiles : -
1,4,5,7-
1,3,5,811,2,4,8
-1,2,3,7-
+ -
1,4,5,7-
1,3,5,823,5,6,7
-4,5,6,8-
┘ -
1,4,5,7-
2,4,6,731,2,4,8
-4,5,6,8-
└ -
2,3,6,8-
1,3,5,843,5,6,7
-1,2,3,7-
┐ -
2,3,6,8-
2,4,6,751,2,4,8
-1,2,3,7-
┌ -
2,3,6,8-
2,4,6,763,5,6,7
-4,5,6,8-
-
1,4,5,7-
2,4,6,773,5,6,7
-1,2,3,7-
| -
2,3,6,8-
1,3,5,881,2,4,8
-4,5,6,8-
-

pour chaque case, on ne fait le random que sur les choix possibles (en violet) et à chaque choix on "AND" les listes de possibles pour ne garder que les possibilités cohérentes
avatar
Webmaster du site Ti-FRv3 (et aussi de DevLynx)
Si moins de monde enculait le système, alors celui ci aurait plus de mal à nous sortir de si grosses merdes !
"L'erreur humaine est humaine"©Nil (2006) // topics/6238-moved-jamais-jaurais-pense-faire-ca

16

ta solution marcherait à condition de toujours remplir dans le même sens, ce qui rejoint les propositions de Godzil et Sally et présente le (gros) problème évoqué dans le 1er paragraphe du ./7 sad
avatar
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)

17

bon, les symboles (jai pris des "routes" mais ça peut marcher avec n'importe quoi, suffit de définir les tiles possibles correspondantes) sont après les tableaux de tiles, les deux tableaux seront donc "résultat", qu'on peuple au fur et à mesur et possibilités qu'on dépeuple au fur et à mesur
avatar
Webmaster du site Ti-FRv3 (et aussi de DevLynx)
Si moins de monde enculait le système, alors celui ci aurait plus de mal à nous sortir de si grosses merdes !
"L'erreur humaine est humaine"©Nil (2006) // topics/6238-moved-jamais-jaurais-pense-faire-ca

18

non, t'es pas obligé de le remplir dans l'ordre
avatar
Webmaster du site Ti-FRv3 (et aussi de DevLynx)
Si moins de monde enculait le système, alors celui ci aurait plus de mal à nous sortir de si grosses merdes !
"L'erreur humaine est humaine"©Nil (2006) // topics/6238-moved-jamais-jaurais-pense-faire-ca

19

Zephyr (./14) :
Trouver des critères de validation pour les contraintes fait partie du "jeu" oui (puisqu'il suffit de deux règles mal fichues pour qu'aucune solution n'existe, de toutes façons), mais avoir forcément un tile pour chaque combinaison de bords n'est pas réaliste (si je prends une de mes planches de tiles au pif, il doit y avoir plus d'une centaine de bords différents, je vous laisse calculer le nombre de tiles que ça implique pour qu'elle soit complète).

Mais on aurait du mal à deviner quels critères supplémentaires seraient pertinents si on a aucune idée du contexte et que tous tes exemples sont assortis d'un "attention, ça n'a rien à voir avec ce que je veux" triso

Par exemple je sais pas, pour faire des terrains style RTS ça peut être plus efficace de générer d'abord des grandes zones ("béton", "mer", "route"...) et ensuite d'appliquer une passe supplémentaire pour trouver les tiles avec les bons raccordements.

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

20

Ah oui mince j'avais pas lu la première partie du ./7 confus (c'est pour ça que je reposais la question cheeky). Par contre tous les tiles auraient le même nombre de contraintes (2) sauf ceux de la première ligne et de la première colonne, mais bon ça reste sans doute un résultat biaisé.

Ceci dit tu peux aussi partir du centre et escargoter par exemple, ça t'évitera aussi toujours d'avoir plus de deux contraintes à la fois, et plus généralement tu peux remplir dans un ordre suivant n'importe quel chemin qui ne laisse jamais un angle ouvert. Dans tous les cas tu auras des tiles qui seront plus contraints que d'autres (certains auront une contrainte et d'autres deux), mais ils ne seront pas toujours au même endroit, donc si tu choisis cet ordre de remplissage au hasard lui-même ça peut peut-être aller ?
Zephyr (./14) :
si je prends une de mes planches de tiles au pif, il doit y avoir plus d'une centaine de bords différents
Ah ok, je n'imaginais pas cet ordre de grandeur ^^
Ben ça fait 10000 combinaisons possibles (et si on les prend dans les deux sens ça fait presque 20000), par contre chaque tile contient plusieurs combinaisons (4 mais il peut y avoir plusieurs fois les mêmes... donc ça dépend, mais a priori il y a besoin de moins de 10000 tiles ; bon c'est déjà pas mal cheeky)
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

21

vince (./18) :
non, t'es pas obligé de le remplir dans l'ordre

Soit j'ai pas compris soit il ya un problème alors. Mettons que j'ai les tiles A, B, C et D.

A ne peut avoir que B à sa droite, D ne peut avoir que C à sa gauche, et B peut avoir tout sauf C à sa droite. À une étape de la génération (aléatoire donc), j'obtiens cette ligne : A | (B) | (C) | D (les tiles entre parenthèses indiquent les possibilités restantes pour la case correspondante). Jusqu'à présent rien n'a posé problème, mais inévitablement en continuant je vais être obligé de placer mon B en position 2, rendant impossible le C en position 3. Pour résumer, on peut en fonction des règles générer une configuration qui va nous bloquer plus tard, mais qui n'est pas évidente à déceler en ne regardant que ce qu'il y a autour.
Pollux (./19) :
Mais on aurait du mal à deviner quels critères supplémentaires seraient pertinents si on a aucune idée du contexte et que tous tes exemples sont assortis d'un "attention, ça n'a rien à voir avec ce que je veux" triso
Par exemple je sais pas, pour faire des terrains style RTS ça peut être plus efficace de générer d'abord des grandes zones ("béton", "mer", "route"...) et ensuite d'appliquer une passe supplémentaire pour trouver les tiles avec les bons raccordements.


Si j'ai pas donné de contexte c'est parcequ'il n'y en a pas... Je cherchais à faire un générateur universel, donc il ne peut pas connaître les notions de "grandes zones", de routes ou de quoi que ce soit d'autre. Il n'y a que deux choses en entrée : les tiles, et les règles associées.

Je me doute bien que mathématiquement il y a tout un tas de raisons qui font qu'une solution ne pourra pas être trouvée à chaque fois. Mais en pratique, même avec des algos complètement naïfs je peux obtenir des maps remplies à 95% sur lesquelles je vais pouvoir lancer une deuxième passe d'ajustement pour essayer de débloquer les cases qui posent problème. Il y a probablement plus intelligent que les voies dans lesquelles je suis parti (je détaillerai si besoin), d'où le topic.
avatar
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)

22

Plus précisément, pour le remplissage, je pense que tu peux procéder comme suit : tu ne peux jouer sur une ligne ou une colonne donnée que si soit elle est complètement vide, soit tu joues à côté d'un tile qui s'y trouve déjà. À part ça, tu choisis la case à remplir au hasard. Si je ne me trompe pas, ça doit éviter que tu puisses te retrouver avec trois contraintes à la fois sur la même case. Et ça reste quand même fortement aléatoire, il me semble.

Par contre je ne vois toujours pas mieux que le backtracking pour résoudre les cas où on a deux contraintes incompatibles, mais bon deux c'est mieux que trois cheeky.

Après je ne sais pas si ça peut être utile mais en respectant cette règle de remplissage les paires de contraintes ne peuvent porter que sur deux côtés adjacents (pas opposés), donc toutes les combinaisons de contraintes ne sont pas possibles.
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

23

Ah pas con comme méthode de sélection, je testerai mais ça peut être un bon compromis ^^ (sauf sur la fin où le problème se posera comme avant, mais chaque chose en son temps embarrassed)
avatar
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)