Algorithme logique Solution

[Adel13]

Salut à tous ! Je rencontre un petit problème j'espère pouvoir avoir de l'aide


Donc voila soit n, la taille d'une grille d'un sudoku. Donc pour une grille à 5 lignes et 5 colonnes,
n=5 .

Soit également : i,j,k , la triplette qui donne la valeur d'une cause .
Par exemple : 2,1,4 signifie qu'à la ligne 2, 1ère colonne, on a la valeur 4.


Le problème :
Mon objectif est de transformer la suite de triplette en variable unique, allant de 1 à n².

Autrement dit ( toujours pour n = 5) :
1,1,1 => 1
1,1,2 => 2
...
1,2,5 => 5
1,2,1 => 6

Afin d'établir cette relation, j'utilise la fonction suivante :
n²(i-1) + n(j-1) + k

Aucun soucis jusque là.
Le problème que je rencontre est de faire l'inverse, ce qui est apparemment impossible avec une fonction mathématique. Il me faudrait un algo.
L'objectif est donc par exemple :
On me donne l'entier "6", je dois retrouver = > 1,2,1.

C'est casse tête je sais :p , mais si quelqu'un a envie de se casser la tête bin ... merci d'avance !
Car je suis bloqué depuis plus de 2 jours pour trouver une solution ..

[Franck Dernoncourt]

http://fr.wikipedia.org/wiki/%C3%89q..._ax%2Bby_%3D_c ?

EDIT : désolé, j'avais lu trop rapidement, mon lien est mauvais car k est également une inconnue. Donc plus généralement, ton équation est de type diophantienne du premier degré (mais pas forcément une identité de Bézout, ce qui ne serait le cas que si k est une constante, i.e. ssi tu n'avais que 2 inconnues)

[Franck Dernoncourt]

Au passage je suppose que tu voulais dire 1,1,5 => 5 ?

Au-delà du caractère général de mon message précédent, ton problème a des contraintes spécifiques qui font que l'équation me semble facile à résoudre à coup de division et modulo.

E.g. pour 6 quelque chose du genre :
k = 6 (mod n) = 1 (si n = 5)
i = ceiling(6 / n) (mod n) = 2 (si n = 5)
j = ceiling(6 / n²) (mod n) = 1 (si n = 5)

[droggo]

Lai,

Oui, je suis arrivé au même genre de résultat :

Code C :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
uint32_t getIt(uint32_t n, uint32_t i,uint32_t j,uint32_t k)
{
    // n²(i-1) + n(j-1) + k
    uint32_t res = n*n*(i-1) + n*(j-1) + k;
    return res;
}
int main()
{
    const uint32_t n = 5;
    uint32_t i,j,k,r,modK,rModK,modJ,rModJ,modI;
 
    for (i=1; i<=n; ++i)
    {
        for (j=1; j<=n; ++j)
        {
            for (k=1; k<=n; ++k)
            {
                r = getIt(n,i,j,k);
                modK = (r-1) % n; // = k-1 !!!
                rModK = r - (modK+1);
 
                modJ = (rModK / n) % n; // = j-1 !!!
                rModJ = (rModK / n)- modJ;
 
                modI = rModJ / n; // = i-1  !!!
 
                printf("%1u%1u%1u => %3u, modK = %1u, rModK = %3u, modJ = %3u, rModJ = %1u, modI = %1u\n",i,j,k,r,modK,rModK,modJ,rModJ,modI);
            }
        }
    }
 
    return 0;
}

et en sortie (pas complète, pour éviter trop de lignes)

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
111 =>   1, modK = 0, rModK =   0, modJ =   0, rModJ = 0, modI = 0
112 =>   2, modK = 1, rModK =   0, modJ =   0, rModJ = 0, modI = 0
113 =>   3, modK = 2, rModK =   0, modJ =   0, rModJ = 0, modI = 0
114 =>   4, modK = 3, rModK =   0, modJ =   0, rModJ = 0, modI = 0
115 =>   5, modK = 4, rModK =   0, modJ =   0, rModJ = 0, modI = 0
121 =>   6, modK = 0, rModK =   5, modJ =   1, rModJ = 0, modI = 0
122 =>   7, modK = 1, rModK =   5, modJ =   1, rModJ = 0, modI = 0
123 =>   8, modK = 2, rModK =   5, modJ =   1, rModJ = 0, modI = 0
124 =>   9, modK = 3, rModK =   5, modJ =   1, rModJ = 0, modI = 0
125 =>  10, modK = 4, rModK =   5, modJ =   1, rModJ = 0, modI = 0
131 =>  11, modK = 0, rModK =  10, modJ =   2, rModJ = 0, modI = 0
132 =>  12, modK = 1, rModK =  10, modJ =   2, rModJ = 0, modI = 0
133 =>  13, modK = 2, rModK =  10, modJ =   2, rModJ = 0, modI = 0
134 =>  14, modK = 3, rModK =  10, modJ =   2, rModJ = 0, modI = 0
135 =>  15, modK = 4, rModK =  10, modJ =   2, rModJ = 0, modI = 0
141 =>  16, modK = 0, rModK =  15, modJ =   3, rModJ = 0, modI = 0
142 =>  17, modK = 1, rModK =  15, modJ =   3, rModJ = 0, modI = 0
143 =>  18, modK = 2, rModK =  15, modJ =   3, rModJ = 0, modI = 0
144 =>  19, modK = 3, rModK =  15, modJ =   3, rModJ = 0, modI = 0
145 =>  20, modK = 4, rModK =  15, modJ =   3, rModJ = 0, modI = 0
151 =>  21, modK = 0, rModK =  20, modJ =   4, rModJ = 0, modI = 0
...
532 => 112, modK = 1, rModK = 110, modJ =   2, rModJ = 20, modI = 4
533 => 113, modK = 2, rModK = 110, modJ =   2, rModJ = 20, modI = 4
534 => 114, modK = 3, rModK = 110, modJ =   2, rModJ = 20, modI = 4
535 => 115, modK = 4, rModK = 110, modJ =   2, rModJ = 20, modI = 4
541 => 116, modK = 0, rModK = 115, modJ =   3, rModJ = 20, modI = 4
542 => 117, modK = 1, rModK = 115, modJ =   3, rModJ = 20, modI = 4
543 => 118, modK = 2, rModK = 115, modJ =   3, rModJ = 20, modI = 4
544 => 119, modK = 3, rModK = 115, modJ =   3, rModJ = 20, modI = 4
545 => 120, modK = 4, rModK = 115, modJ =   3, rModJ = 20, modI = 4
551 => 121, modK = 0, rModK = 120, modJ =   4, rModJ = 20, modI = 4
552 => 122, modK = 1, rModK = 120, modJ =   4, rModJ = 20, modI = 4
553 => 123, modK = 2, rModK = 120, modJ =   4, rModJ = 20, modI = 4
554 => 124, modK = 3, rModK = 120, modJ =   4, rModJ = 20, modI = 4
555 => 125, modK = 4, rModK = 120, modJ =   4, rModJ = 20, modI = 4

[Adel13]

Franck Dernoncourt, j'ai l'impression que cela ne marche pas.
Par exemple pour 37

Pour n = 5
On a k = 37 % 5 = 1 ( ok )
on a i = (37/5)% 5 = 2 ( ok )
Mais on a :
j = (37/5²) % 5 = 1 alors qu'il devrait être égale à 3 :/

[Franck Dernoncourt]

Ah peut-être, je n'ai lu que très rapidement ton message et n'ai pas regardé les détails, je voulais simplement te donner une idée d'algorithme pour trouver les variables i,j et k. Je te laisse faire la fin

[Adel13]

Bin sincérement j'y travail depuis 2 jours j'y arrive pas ..
Pour le i et le k apparemment c'est bon mais le j ..

[droggo]

Xia,

Envoyé par Adel13

Bin sincérement j'y travail depuis 2 jours j'y arrive pas ..
Pour le i et le k apparemment c'est bon mais le j ..

Il se pourrait que lire mon message précédent t'aide !

[Adel13]

Oui dsl merci de ta réponse, j'ai vraiment eu du mal à la comprendre pourrais-tu me l'expliquer un peu ?
Quel sont toutes ces variables ?
Vraiment désolé ..

[droggo]

Vie,

J'ose espérer que tu plaisantes !!

n,i,j,k sont les mêmes que les tiens, les autres sont des calculs intermédiaires et/ou définitifs, et dans le code, il y a de petits commentaires pour dire leur finalité (enfin, les 3 qui comptent, celles qui contiennent ce que tu cherches).

Regarde la liste de sortie pour t'en convaincre.

[souviron34]

Envoyé par droggo

J'ose espérer que tu plaisantes !!

Optimiste !!