Fonction récursive et deux types de retour

Version imprimable

Bonjour à tous,

Voici mon problème, j'ai entrepris de convertir une fonction récursive qui permet de générer des grilles de sudoku de PHP vers VB.

Le problème qui se pose est le type de retour qui est à la fois un Integer(,) et un booléen.

Je ne sais pas comment résoudre la solution, l'algorithme marche mis à part la fin de l'appel ( le damier est bien remplis ).

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 Private Function creer_grille(Optional ByVal grille As Integer(,) = Nothing, Optional ByVal position As Integer = 0)
        Dim i, j, v As Integer
        Dim valeurs = New List(Of Integer)
        Dim resultat As Boolean
 
        'retourne la grille trouvée si nous sommes a la fin
        If (position = 81) Then
            Return (grille)
        End If
 
        'calcul de la ligne et colonne
        i = Math.Floor(position / 9)
        j = position Mod 9
 
        'liste des nombres de 1 à 9
        valeurs.AddRange({1, 2, 3, 4, 5, 6, 7, 8, 9})
 
        'efface les valeurs déjà utilisées
        If (v > 0) Then
            For k As Integer = 0 To 8
                'retire la valeur de la ligne
                If (v = Int(grille(i, k))) Then
                    valeurs.RemoveAt(v - 1)
                End If
 
                'retire la valeur de la colonne
                If (v = Int(grille(k, j))) Then
                    valeurs.RemoveAt(v - 1)
                End If
 
                'retire la valeur de la zone
                If (v = Int(grille(i + Math.Floor(k / 3), j + (k Mod 3)))) Then
                    valeurs.RemoveAt(v - 1)
                End If
            Next
        End If
 
        'mélange les valeurs
        valeurs = shuffleList(valeurs)
 
        For Each v In valeurs
            grille(i, j) = v
 
            resultat = creer_grille(grille, position + 1)
 
            If (resultat) Then
                Return resultat
            End If
 
            grille(i, j) = Nothing
        Next
 
        Return False
    End Function

Merci d'avance pour votre aide ;)

05/01/2010, 15h23
Pol63

tu peux transformer la fonction en sub et mettre 2 paramètres byref
05/01/2010, 15h24
dtom99

Mais je vais devoir modifier quoi dans le programme ?

Je vois pas trop là où tu veux en venir... :(
05/01/2010, 15h30
Pol63
pas grand chose, remplacer les 2 byval par des byref, retirer les optionnal

Code:

Private Function creer_grille(ByRef grille As Integer(,), ByRef position As Integer)

et déclarer les variables avant l'appel de la sub
Code:

1 2 3 dim grille As Integer(,) = Nothing dim position as integer = 0 creer_grille (grille, position)
comme ca tu récupères grille et position dans l'appelant

mais en regardant de plus près, je suis pas sur que tu ai besoin de la position, donc que tu n'aurais pas besoin non plus d'une fonction qui retourne 2 choses

Mais pour les lignes

Code:

1
2
3
4
        If (position = 81) Then
            Return (grille)
 
        End If

Je remplace par quoi ?

Citation:

Envoyé par dtom99

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 Private Function creer_grille(Optional ByVal grille As Integer(,) = Nothing, Optional ByVal position As Integer = 0)
        Dim i, j, v As Integer
        Dim valeurs = New List(Of Integer)
        Dim resultat As Boolean
 
        'retourne la grille trouvée si nous sommes a la fin
        If (position = 81) Then
            Return (grille)
        End If
 
'...................
 
        Return False
    End Function

Et si tu essaye comme t'as dit Pol63 de passer les paramètres byref mais laisse la fonction et dans ce cas elle va retourner comme valeur un boolean :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 Private Function creer_grille(ByRef grille As Integer(,), 
ByRef position As Integer) as Boolean
        Dim i, j, v As Integer
        Dim valeurs = New List(Of Integer)
        Dim resultat As Boolean
 
        'retourne la grille trouvée si nous sommes a la fin
        If (position = 81) Then
            Return True    ' Veux dire que la grille est déjà remplie
        End If
 
'...................
 
        Return False
    End Function

Qui ce que t'en pense ?

05/01/2010, 16h45
Pol63

sinon exit sub

J'ai testé vos modifications :

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
Private Function creer_grille(ByRef grille As Integer(,), ByRef position As Integer) As Boolean
        Dim i, j, v As Integer
        Dim valeurs = New List(Of Integer)
        Dim resultat As Boolean
 
        'retourne la grille trouvée si nous sommes a la fin
        If (position = 81) Then
            Return True
            'GoTo end_creer_grille
        End If
 
        'calcul de la ligne et colonne
        i = Math.Floor(position / 9)
        j = position Mod 9
 
        'liste des nombres de 1 à 9
        valeurs.AddRange({1, 2, 3, 4, 5, 6, 7, 8, 9})
 
        'efface les valeurs déjà utilisées
        If (v > 0) Then
            For k As Integer = 0 To 8
                'retire la valeur de la ligne
                If (v = Int(grille(i, k))) Then
                    valeurs.RemoveAt(v - 1)
                End If
 
                'retire la valeur de la colonne
                If (v = Int(grille(k, j))) Then
                    valeurs.RemoveAt(v - 1)
                End If
 
                'retire la valeur de la zone
                If (v = Int(grille(i + Math.Floor(k / 3), j + (k Mod 3)))) Then
                    valeurs.RemoveAt(v - 1)
                End If
            Next
        End If
 
        'mélange les valeurs
        valeurs = shuffleList(valeurs)
 
        For Each v In valeurs
            grille(i, j) = v
 
            resultat = creer_grille(grille, position + 1)
 
            If resultat Then
                Return resultat
            End If
 
            'If (grille.Length > 0) Then
            'GoTo end_creer_grille
            'creer_grille(grille, position + 1, isOk)
            '  End If
 
            grille(i, j) = Nothing
        Next
 
        Return False
 
end_creer_grille:
    End Function

Mais voilà ce que ça donne :

http://motx.travian-search.com/screenshots/sudoku1.JPG

PS : en rouge ce sont les valeurs erronnées
PS2 : Le script en php fonctionne trés bien

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
<?php
function creer_grille( $grille = array(), $position = 0 ) {
 
       // Si nous sommes arrivés à la fin, la grille est trouvée
       if( $position == 81 ) {
               return $grille;
       }
 
       // Calculer la ligne et la colonne
       $i = floor( $position / 9 );
       $j = $position % 9;
 
       // Créer une liste des nombres de 1 à 9
       $valeurs = range( 1, 9 );
 
       // Retirer les valeurs déjà utilisées
       for( $k=0; $k<9; $k++ ) {
 
               // Oter de la liste les nombres de la ligne
               if( $v = $grille[ $i ][ $k ] ) {
                       unset( $valeurs[ $v-1 ] );
               }
 
               // Oter de la liste les nombres de la colonne
               if( $v = $grille[ $k ][ $j ] ) {
                       unset( $valeurs[ $v-1 ] );
               }
 
               // Oter de la liste les nombres du carré
               if( $v = $grille[ $i + floor($k/3) ][ $j + ($k%3) ] ) {
                       unset( $valeurs[ $v-1 ] );
               }
       }
 
       // Melanger le tableau
       shuffle( $valeurs );
 
       // Essayer les valeurs restantes jusqu'à trouver la solution
       foreach( $valeurs as $v ) {
 
               $grille[$i][$j] = $v;
               $resultat = creer_grille( $grille, $position + 1 );
 
               // Si on trouve la solution, on la retourne
               if( $resultat ) {
                       return $resultat;
               }
 
               unset( $grille[$i][$j] );
       }
 
       // Si nous arrivons à la fin de la boucle, aucune grille n'existe
       // avec les valeurs précédentes
       return false;
}
?>

05/01/2010, 21h14
Pol63

il serait peut etre préférable d'apprendre le vb.net, et de réécrire l'algo en réfléchissant plutot qu'en copiant collant

http://plasserre.developpez.com/cours/vb-net/

c'est toi qu'a écrit le code php ?
05/01/2010, 21h26
dtom99

Le problème c'est que je fais plein de langages différents ( C++, C#, Java, PHP, et là VB ).

Les cours ne répondent pas un problème bien particulier, et je n'arriverais à maîtriser le VB qu'au cours d'une longue utilisation, et si j'en viens à demander sur ce forum votre aide, c'est que je n'ai malheureusement pas le temps nécessaire :(

Sinon, non je n'ai pas écris ce code php

En fait le probleme vient que la condition suivante :
Code:

1 2 3 4 // Si on trouve la solution, on la retourne if( $resultat ) { return $resultat; }
Retourne non pas un booléen mais les resultats ( vérifié avec un print_r )

05/01/2010, 22h44
Spirit 203

Bonjour,
Je suis l'auteur du code php. La solution du ByRef est effectivement la meilleure manière de résoudre le problème du retour.

Votre problème vient à mon avis du RemoveAt() qui doit décaler les indexes. Ainsi, lors du premier RemoveAt(v-1), cela correspond bien à l'index de la valeur v, mais après, les indexes sont décalés et vous retirez des valeurs trop grandes.

Est-ce qu'il n'y aurait pas plutôt une méthode Remove( value ) qui retire par la valeur et non par l'index ?

Bien cordialement,
05/01/2010, 23h02
dtom99

En effet, j'ai remis la fonction comme au départ, en passant le type de retour en "Object", mais les valeurs ne sont toujours pas cohérentes... surement cette ligne

Code:

grille(i, j) = Nothing
03/02/2010, 16h39
Sehnsucht
Et voilà ce qu'il se passe quand on fait un copier-coller d'un code sans trop savoir ce que l'on fait:
Code:

1 2 3 4 5 if( $v = $grille[ $i ][ $k ] ) { unset( $valeurs[ $v-1 ] ); }
Converti en:
Code:

1 2 3 4 If (v = Int(grille(i, k))) Then valeurs.RemoveAt(v - 1) End If
Ne pas confondre en php le "=" avec "==". En php le double égal sert à la comparaison alors que le égal simple sert à l'affectation alors qu'en VB c'est le même égal dans les deux cas ce qui fait que se qu'il se passe réellement dans le code php c'est:
on met dans $v ce qui est dans $grille[$i][$k] est ensuite on teste (booléennement :aie:) $v
Alors que dans le code VB on teste juste si v et grille(i, k) contienne la même valeur.

Je sais pas si c'est bien clair, désolé sinon; en espérant avoir pu être utile.
03/02/2010, 20h13
dtom99

Bonsoir,

Oui en effet je connais bien les différences d'affectation et de comparaison sur ces deux langages.

De toute façon le code php fourni et détaillé sur lequel je m'étais basé ne fonctionne pas correctement à la base...
03/02/2010, 20h30
Sehnsucht

Citation:

Envoyé par dtom99

Bonsoir,

Oui en effet je connais bien les différences d'affectation et de comparaison sur ces deux langages.

De toute façon le code php fourni et détaillé sur lequel je m'étais basé ne fonctionne pas correctement à la base...

Si tu connais bien les différences pourquoi alors nous avoir fourni en premier post une version VB qui est une traduction "mot-à-mot" du code php et au passage une conversion erronée (cf. mon post précédent) ?