Discussion :

[Tokapi]

Bonjour.

Je programme actuellement en C un petit solveur de Sudoku pour occuper mon temps perdu. Seulement je me heurte pour la première fois à un vrai problème de programmation : complexité d'algorithme =/

En fait actuellement mon truc résout à peu près tout ce qui lui passe sous la main, excepté ce qui passe obligatoirement par X-Wing et généralisation.
J'ai alors besoin d'executer un test du type :

for(a1=0;a1<2;a1++)
{for(a2=0;a2<2;a2++)
{for(a3=0;a3<2;a3++)
(...)
{for(a27=0;a27<2;a27++)
{ //test sur la combinaison des ai
}}}}}}}}}}}}}}}}}}}}}}}}}}}

J'immagine que vous voyez direct le problème, ca fait quelque chose comme 134 000 000 de tests...

Seulement, dans disons 99,99999 % des cas ces tests ne sont effectifs que pour des combinaisons de moins de 4 ai à l'état "1".
Mon idée est donc d'ordonner ces tests de manière à ce qu'ils se fassent dans l'ordre suivant :

-> toutes les combinaisons de 2 ai à l'état "1" (le cas 1 ai est inutile)
-> toutes les combinaisons de 3 ai à l'état "1"
-> toutes les combinaisons de 4 ai à l'état "1"
-> (...)
-> toutes les combinaisons de 27 ai à l'état "1"

afin d'arreter l'algorithme le plus tôt possible dans la plupart des cas (dès qu'un résultat en ressort).
Mais voilà ... je sais du tout comment faire un truc pareil =X

En fait, j'aimerais bien ne pas avoir de code, mais simplement une technique qui puisse me permettre de faire mes tests dans cet ordre.

Au fond ca revient à trouver toutes les combinaisons de n parmi 27 pour les tester en temps réel. J'ai déjà trouvé des fonctions qui permettent de créer des tableaux de combinaisons de ce genre, simplement je préfèrerais éviter d'avoir à créer un tableau plus grand que mon pc pour l'interprêter ensuite, le but étant quand même d'accélérer mon programme...
Ce qui m'intéresse surtout est de pouvoir comprendre le principe afin de créer ma propre fonction qui puisse faire mes tests sans créer de poids titanesque et inutile dans la mémoire =d.

Bref, merci d'avance à qui pourrait essayer de m'aider.

[Zavonen]

Au fond ca revient à trouver toutes les combinaisons de n parmi 27 pour les tester en temps réel.

Ca c'est un grand classique et je peux (si tu veux) te passer un snippet python qui fait le boulot.

[Tokapi]

Ben c'est sympa mais à vrai dire outre le fait que je lise pas le python c'est surtout le principe qui m'intéresse, mon truc c'est de programmer le plus possible à la main, je préfère éviter d'importer des fonctions que je pourrais coder moi même =o