Combinaisons dans une ligne de Kakuro

Bonjour,

Je rencontre des difficultés dans l’élaboration d’une fonction en C++, mais le problème est à la base un problème d’algorithme.

Je suis sur un projet d’un programme visant à résoudre les grille de Kakuro. Ce petit jeu vise à mettre des chiffres de 1 à 9 dans des cases en respectant certaines contraintes. Pour les intéressés qui ne connaitraient pas, vous trouverez plus d’infos sur Wikipédia.

J’ai besoin d’une fonction de base pour mon algorithme principal. Cette fonction doit me retourner un tableau de tableau d’entier. Voilà son prototype :

entier ** combinaisons(entier valeur, entier nbcase)
ou
combinaisons(entier **tableau, entier valeur, entier nbcase)

J’ai des lignes de nbcase cases. Dans ces lignes je dois mettre des chiffres distincts de 1 à 9, et la somme de ces chiffres doit faire valeur. Cette fonction me retourne donc toutes les combinaisons possible pour ma ligne. Par exemple :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

combinaisons(8, 2) Retourne : 1 7 2 6 3 5   combinaisons(8, 3) Retourne : 1 2 5 1 3 4   combinaisons(11, 3) Retourne : 1 2 8 1 3 7 1 4 6 2 3 6 2 4 5 …

---

On remarque au passage que les sous-tableaux ont toujours la même taille : nbcase.
J’ai tenté une solution par récurrence, mais sans résultats…

Merci de votre aide.

Citation:

---

Envoyé par FabaCoeur

J’ai tenté une solution par récurrence, mais sans résultats…

---

Pourtant, le critere de récurrence a pas l'air bien compliqué.

- Liste des chiffres possibles LP = {1,2,3,..9}
- Construire liste sans doublon de taille N ayant une somme S avec les chiffres de LP

==>

LISTE(N,S,LP) = { Chiffre , LISTE(N-1, S-Chiffre, LP\{Chiffre}) }

et

LISTE(1,S,LP) = S si S est dans LP, sinon pas de solution.

exemple:

Citation:

---

LISTE(2,8,{1,2,3,4,5,6,7,8,9})

= {1, LISTE(1,7,{2,3,4,5,6,7,8,9}) } = {1, 7}
= {2, LISTE(1,6,{1,3,4,5,6,7,8,9}) } = {2, 6}
= {3, LISTE(1,5,{1,2,4,5,6,7,8,9}) } = {3, 5}
= {4, LISTE(1,4,{1,2,3,5,6,7,8,9}) } = pas de solution
= {5, LISTE(1,3,{1,2,3,4,6,7,8,9}) } = {5, 3}
...

---

Ce que j'avais fait était vraiment très proche de cela !
Mais je n'avais pas pensé à passer des listes de taille fixe {1,...,8,9} et à elever des éléments à chaque fois. Je vais donc essayer de traduire tout ça en C++ (en C même) maintenant et je posterai la solution.

Merci beaucoup pour ce coup de pouce :king: