Discussion :

[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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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