Bonjour, j'essaie de résoudre un gratte-ciel, tout est nickel jusque la grace aux fonctions " logique " qui place les chiffres logique, ex: devant le 4 -> placer 1, devant le 4 -> placer 1234 sur la ligne etc.., il me reste plus qu'a brute-force pour trouver les derniers chiffres mais, c'est la première fois que j'essaie cette méthode, donc c'est nouveau pour moi mais malheureusement pour moi, ca ne fonctionne pas.
Aussi, même si je suis loin de la solution je sais pas, mais svp pouvez vous juste me donnez des indications ? Par exemple sur le fait qu'il trouve forcément au moins la bonne combinaison une fois mais la fonction continue de s'executer..
int check_left_range(int tab[4][4], int consign[4][4], int x)
{
int j = 0;
int max = 0;
int value = consign[LEFT][x];
int count = 0;
while (j < 4)
{
if (tab[x][j] > max)
{
max = tab[x][j];
count++;
}
j++;
}
return (count == value);
}
int check_right_range(int tab[4][4], int consign[4][4], int x)
{
int j = 3;
int max = 0;
int value = consign[RIGHT][x];
int count = 0;
while (j >= 0)
{
if (tab[x][j] > max)
{
max = tab[x][j];
count++;
}
j--;
}
return (count == value);
}
int line_has_double(int tab[4][4], int x)
{
int i = 0;
int j;
while (i < 4)
{
j = i + 1;
while (j < 4)
{
if (tab[x][i] == tab[x][j])
return (1);
j++;
}
i++;
}
return (0);
}
int line_is_filled(int tab[4][4], int x)
{
int y = 0;
while (y < 4)
{
if (tab[x][y] == 0)
return (0);
y++;
}
return (1);
}
void place(int (*tab)[4][4], int consign[4][4], int i, int j, int tmp)
{
if (check_right_range(*tab, consign, i)
&& check_left_range(*tab, consign, i)
&& line_is_filled(*tab, i)
&& !line_has_double(*tab, i))
return ;
if (j >= 4) j = 0;
if (tmp > 4) tmp = 0;
while (!check_right_range(*tab, consign, i)
|| !check_left_range(*tab, consign, i)
|| line_has_double(*tab, i)
|| !line_is_filled(*tab, i))
{
(*tab)[i][j] = tmp % 4 + 1;
print_tab(*tab);
place(tab, consign, i, j + 1, tmp + 1);
}
print_tab(*tab);
printf("\nquit\n");
}
rien n'est clair dans ton message. Tu veux résoudre le problème en parcourant tout l'espace de solutions ?
Une méthode dans ton cas serait de générer les 24=4! permutations possibles de 4 chiffres distincts, à chaque permutation associer ses nombres gratte ciel gauche et droit, pour chaque ligne d'indice essayer les permutations correspondantes et avancer par backtracking …
Oui désolé, et oui je veux le remplir à partir 0, donc quand le tableau est vide. C'est vrai que du coup j'ai créer les autres fonctions, mais je l'adapterais plus tard, pour bien comprendre comment ça marche.
Dis comme ça c'est vrai que ça parait bien plus simple !
Mais en posant un chiffre un à un c'est pas possible ? Je voudrais essayer comme ça si c'est possible
J'ai vu le message en retard et je ne connaissais pas le jeu du gratte-ciel. Je pense comme White Crow qu'un algorithme récursif avec backtracking implicite serait la meilleure solution.
Le Tout est souvent plus grand que la somme de ses parties.
En posant les chiffres un à un ? oui, c'est possible. Dans ton cas la version naïve revient à parcourir les 4¹⁶=4294967296 4×4 grilles possibles remplies de chiffres allant de 1 à 4. Ça fait beaucoup de grilles à explorer, même si tu arrives à élaguer rapidement l'arbre de recherche.
L'algorithme est récursif et relativement simple : pour chaque les cases tu places un chiffre, si ce chiffre ne viole pas les contraintes et si ce chiffre est le dernier d'une ligne ou d'une colonne et qu'il permet de satisfaire les conditions aux bords alors tu passes à la case suivante sinon tu essayes un autre chiffre et si tous les chiffres ont été utilisés alors tu arrêtes là la descente récursive.
En pseudo-code
solve( board , l, c)
for digit in (1,4)
board[l][c] ← digit
if check_digits(board) and check_boundary_conditions(board, conditions)
if is_complete(board)
print(board)
else
(next_l, next_c) = next(l,c)
solve(board, next_l, next_c)
board[l][c] ← 0
Maintenant si tu préremplis le jeu avec «les cas faciles» alors tu peux sauter les cases préremplies.
solve( board , l, c)
if board[l][c] = 0
for digit in (1,4)
board[l][c] ← digit
if check_digits(board) and check_boundary_conditions(board, conditions)
if is_complete(board)
print(board)
else
(next_l, next_c) = next(l,c)
solve(board, next_l, next_c)
board[l][c] ← 0
else
if is_complete(board)
print(board)
else
(next_l, next_c) = next(l,c)
solve(board, next_l, next_c)
Ça se factorise évidemment, mais là c'est pour te montrer un peu la démarche.
En effet, a part la brute force, je vois plein d'astuces.
Deja certaines cases triviales :
- si une case latérale te dit 1, alors ça veut dire que tu as l'immeuble 4 en premier (l'immeuble N pour un cas quelconque), tu remplis une case.
- si une case latérale te dit 4, alors ça veut dire que tu les vois tous, donc qu'ils sont rangés dans l'ordre croissant 1,2,3,4 : tu remplis 4 cases.
Ensuite, comme évoquait whitecrow, il faut partir des permutations : tu dois mettre 1,2,3,4 dans chaque ligne et chaque colonne. ça te fait 4!=24 cas différents.
Je te suggère d'énumérer ces cas, et de les grouper par nombre d'immeubles.
Par exemple 1,2,3,4 est dans le groupe 4 (et est le seul) car c'est le seul ou on verra les 4 immeubles
1,3,4,2 est dans le groupe 3, etc...
Ensuite, si tu considères une ligne, tu as les chiffre à gauche, et le chiffre à droite : donc tu as des candidats (le groupe) pour le chiffre de gauche, et des candidats (un autre groupe) pour le chiffre de droite (a regarder dans l'autre sens). L'intersection des deux groupes devrait donner déjà peu de possibilité pour chaque ligne, et chaque colonne. Surtout s'il y a déjà des chiffres en place (voir première partie de mon message).
Pour chaque ligne ou chaque colonne ou il n'y a qu'une seule possibilité, remplis. Avec un peu de chance tu termines deja les cas les plus simples.
Ensuite tu peux essayer de voir les intersections possibles des cas entre les lignes et les colonnes.
Et si ça ne se termine pas ainsi, tu finis en backtracking, mais avec uniquement les possibilités énumérées pour chaque lignes/colonnes.
Je n'ai pas tout à fait compris la règle de ce jeu. Est-ce que tous les édifices doivent être visible du côté gauche ou du droit seulement ou bien du haut ou du bas également? Est-ce que les indices latéraux sont fournis au départ ou si on les évalue au fur et à mesure qu'on avance? À mon avis, on pourrait s'en passer.
@hugoducine: Tu pourrais clarifier ton code en remplaçant les while par des for dans la plupart des cas. Je pense qu'on pourrait améliorer les fonctions check... La fonction placer() est bien récursive, mais la condition d'arrêt n'existe pas à mon avis. Il y a des chose faites en double. Il semble qu'on avance sur les colonnes d'une ligne et on passe à la ligne suivante quand la ligne courante est pleine. La condition d'arrêt pourrait être de tester au départ si le numéro )indice) de ligne est N (pour un 4x4, si le numéro est 4) La fonction pourrait être booléenne et retourner true si on se rend jusqu'au bout. Elle retourne false si on ne peut pas remplir à un endroit. Si on réussit, on appelle la fonction pour la case suivante, et on fait suivre le true si ça marche: if(placer(...)) return true; // passer à la possibilité suivante.
Algorithme vite fait: bool placer(...) { si dernier rempli return true pour toutes les possibilités { si on peut placer { le placer si c'est visible de partourt { si placer(...) return true } // visible effacer } // si peut être placé } // possibilité return false } // fonction
Le Tout est souvent plus grand que la somme de ses parties.
Merci à tous pour vos messages, j'ai réussi à pondre quelque chose, par encore fonctionnel mais un bon début, qui est juste de remplir les cases s'il n'y a pas le même chiffre sur la colonne et la ligne. j'ai galérer toute la nuit à essayer de comprendre le pourquoi du comment, mais en relisant mon code sa paraissait pas difficile lol
Et puis pour les boucles while, oui j'ai appris comme ça désolé (piscine 42)^^
Mais merci vraiment beaucoup vous m'avez beaucoup aider !!
PS: que veut dire 4!=24 j'ai arrêter l'école en 3e
Et puis pour les boucles while, oui j'ai appris comme ça désolé (piscine 42)^^
Alors si tu développes professionnellement en C en entreprise (ou du moins en équipe) le seul avantage de 42 c'est que tu apprends à suivre une norme. Mais attends toi à ce que la norme piscine ne soit absolument pas répandue et souvent considérée comme obsolète (et c'est un euphémisme).
Il n'est jamais trop tard pour te mettre un peu plus au goût du jour et apprendre le C moderne (et je parle autant du langage que des outils).
hugoducine a écrit:
PS: que veut dire 4!=24 j'ai arrêter l'école en 3e
Et bien cela signifie 3 choses :
n! est une notation mathématique qui représente le produit des entiers de 1 à n avec pour convention 0!=1 d'où 4! = 1×2×3×4 = 24 ; on appelle ce produit la factorielle de n. n! représente également le nombre de permutations de n symboles différents ⇒ il y a 24 manières distinctes possibles d'écrire les symboles 1,2,3 et 4 sur une ligne ;
qu'il va falloir rattraper les lacunes en math, c'est vraiment toujours utile en dèv ;
qu'il va falloir prendre l'habitude de faire des recherches avec google (ou ton moteur de recherche favori).
Je t'assure que je ne cherche pas à t'offenser ou à me moquer.
Edit: @edgarjacobs 👍pour le lien !
Edit 2: à propos … @hugoducine, si tu considères le sujet comme clos, mets le en résolu
Petite constatation en passant ... On a unegrille 4x4, donc on utilise 4 façons de placer les nombres 1 à 4 sur une ligne. Et au total, on a 24 façons de les placer. Déjà plusieurs façons sont conflictuelles parce que chaque nombre ne peut pas apparaître deux fois sur la même colonne. On pourrait sans doute remplacer les consignes par des bit-map pour chaque nombre Ça irait peut-être plus vite pour remplir les lignes. On n'est pas obligé d'attendre que la ligne soit pleine pour tester. Si j'ai 3 2 4 0, je sais que 2 sera caché. Si on accepte qu'il soit visible du haut ou du bas, il faut attendre. Il faut effacer les bits des bit-map quand on recule.
Le Tout est souvent plus grand que la somme de ses parties.
@hugoducine: 4!, c'est factorielle de 4, soit 4*3*2 (*1)
- Edité par edgarjacobs il y a environ 1 heure
Merci pour l'info ! Et oui justement j'ai déjà eu l'occasion de m'entrainer ahah
White Crow a écrit:
hugoducine a écrit:
Et puis pour les boucles while, oui j'ai appris comme ça désolé (piscine 42)^^
Alors si tu développes professionnellement en C en entreprise (ou du moins en équipe) le seul avantage de 42 c'est que tu apprends à suivre une norme. Mais attends toi à ce que la norme piscine ne soit absolument pas répandue et souvent considérée comme obsolète (et c'est un euphémisme).
Il n'est jamais trop tard pour te mettre un peu plus au goût du jour et apprendre le C moderne (et je parle autant du langage que des outils).
Je m'y attendais à ça, car leur norme est assez stricte je trouve et quelque fois, pose plus de problèmes qu'autre chose. Et ça oui je compte bien m'y mettre !
Et bien cela signifie 3 choses :
n! est une notation mathématique qui représente le produit des entiers de 1 à n avec pour convention 0!=1 d'où 4! = 1×2×3×4 = 24 ; on appelle ce produit la factorielle de n. n! représente également le nombre de permutations de n symboles différents ⇒ il y a 24 manières distinctes possibles d'écrire les symboles 1,2,3 et 4 sur une ligne ;
qu'il va falloir rattraper les lacunes en math, c'est vraiment toujours utile en dèv ;
qu'il va falloir prendre l'habitude de faire des recherches avec google (ou ton moteur de recherche favori).
Je t'assure que je ne cherche pas à t'offenser ou à me moquer.
Edit: @edgarjacobs 👍pour le lien !
Edit 2: à propos … @hugoducine, si tu considères le sujet comme clos, mets le en résolu
Rattraper les lacunes en math ? Dans mon cas, ça risque d'être très difficile ahah mais merci pour le conseil
Pff, tu sais mon moteur de recherche doit en avoir marre de toutes les requêtes envoyées par jour sur le même sujet
Mais malgré tout ça, j'ai une bonne nouvelle, j'ai réussi, j'ai essayé en partant de 0 et avec les valeurs pré écrite et c'est fonctionnel !! En fait, j'avais déjà essayer cette solution bien plus tôt c'est juste que dans mes fonctions check_left etc.. j'oublier d'incrémenter l'index .. (comme dans l'exemple du haut où j'ai poster une de mes fonctions, ici check_right: l'index n'est pas incrémenté)
20 août 2021 à 17:47:42
- Message modéré pour le motif suivant : Message complètement hors sujet
Le Prince
Gratte ciel
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Le Tout est souvent plus grand que la somme de ses parties.
On écrit "j'ai tort", pas "tord" qui est le verbe "tordre" à la 3ème personne de l'indicatif présent
Le Tout est souvent plus grand que la somme de ses parties.
Le Prince