Bonjour,

je souhaite résoudre un sudoku par backtracking, cependant je bloque sur une fonction, ce code est présent sur le site en C mais la traduction en OCaml est plus compliquée que prévue, voici les codes respectivement en C et en OCaml :

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>


// Fonction d'affichage
void affichage (int grille[9][9])
{
    for (int i=0; i<9; i++)
    {
        for (int j=0; j<9; j++)
        {
            printf( ((j+1)%3) ? "%d " : "%d|", grille[i][j]);
        }
        putchar('\n');
        if (!((i+1)%3))
            puts("------------------");
    }
    puts("\n\n");
}

bool absentSurLigne (int k, int grille[9][9], int i)
{
    for (int j=0; j < 9; j++)
        if (grille[i][j] == k)
            return false;
    return true;
}

bool absentSurColonne (int k, int grille[9][9], int j)
{
    for (int i=0; i < 9; i++)
        if (grille[i][j] == k)
            return false;
    return true;
}

bool absentSurBloc (int k, int grille[9][9], int i, int j)
{
    int _i = i-(i%3), _j = j-(j%3);  // ou encore : _i = 3*(i/3), _j = 3*(j/3);
    for (i=_i; i < _i+3; i++)
        for (j=_j; j < _j+3; j++)
            if (grille[i][j] == k)
                return false;
    return true;
}

bool estValide (int grille[9][9], int position)
{
    if (position == 9*9)
        return true;

    int i = position/9, j = position%9;

    if (grille[i][j] != 0)
        return estValide(grille, position+1);

    for (int k=1; k <= 9; k++)
    {
        if (absentSurLigne(k,grille,i) && absentSurColonne(k,grille,j) && absentSurBloc(k,grille,i,j))
        {
            grille[i][j] = k;

            if ( estValide (grille, position+1) )
                return true;
        }
    }
    grille[i][j] = 0;

    return false;
}

int main (void)
{
    int grille[9][9] =
    {
        {9,0,0,1,0,0,0,0,5},
        {0,0,5,0,9,0,2,0,1},
        {8,0,0,0,4,0,0,0,0},
        {0,0,0,0,8,0,0,0,0},
        {0,0,0,7,0,0,0,0,0},
        {0,0,0,0,2,6,0,0,9},
        {2,0,0,3,0,0,0,0,6},
        {0,0,0,2,0,0,9,0,0},
        {0,0,1,9,0,4,5,7,0}
    };

    printf("Grille avant\n");
    affichage(grille);

    estValide(grille,0);

    printf("Grille apres\n");
    affichage(grille);
}

et voici mon code pour le moment :

let in_colonne vald grille i j = try
for k = 0 to Array.length grille.(0) - 1 do
	if (grille.(k).(j) = vald && k <> i) then raise Exit done;
false with Exit -> true ;;

let in_ligne vald grille i j = try
for l = 0 to Array.length grille.(0) - 1 do
	if (grille.(i).(l) = vald && l <> j) then raise Exit done;
false with Exit -> true ;;

let in_bloc vald grille i j =
try
    let i_bloc = i - (i mod 3) in
    let j_bloc = j - (j mod 3) in
    for k = i_bloc to (i_bloc + 2) do
        for l = j_bloc to (j_bloc + 2) do
            if grille.(k).(l) = vald then raise Exit
            done
        done;
    false
with
    Exit -> true ;;

let afficher_grille a =
for i = 0 to Array.length a -1 do
        for j = 0 to Array.length a.(0) - 1 do
            print_int a.(i).(j);
            let mot = if ((j+1) mod (Array.length a.(0))) = 0 then "\n" else "\t" in
            print_string mot;
            done;
        done;
    print_string "\n \n";;


let rec est_valide sudok pos =
    let possible = ref false in
    if pos = 81 then true
    else
        let i = pos / 9 in
        let j = pos mod 9 in
        if sudok.(i).(j) <> 0 then
            est_valide sudok (pos + 1)
        else
        begin
        for k=0 to 9 do
            if not(in_ligne k sudok i j) && not(in_colonne k sudok i j) && not(in_bloc k sudok i j) then 
                sudok.(i).(j) <- k;
                if (est_valide sudok (pos + 1)) then possible := true done
        end
        sudok.(i).(j) <- 0;
        !possible;;


let g = Array.make_matrix 9 9 0 in
afficher_grille g;

Merci d'avance.

Encore toi

Je te conseille d'utiliser un IDE genre Emacs pour coder en OCaml, ca te permettra de voir l'indentation des blocs et de comprendre ce qui ne va pas.
Je te propose ceci (à toi de voir si j'ai bien compris le code) :

let rec est_valide sudok pos =
    let possible = ref false in
    if pos = 81 then true
    else
        let i = pos / 9 in
        let j = pos mod 9 in
        if sudok.(i).(j) <> 0 then
            est_valide sudok (pos + 1)
        else
            begin
                for k=0 to 9 do
                    if not(in_ligne k sudok i j) && not(in_colonne k sudok i j) && not(in_bloc k sudok i j) then
                        begin
                            sudok.(i).(j) <- k;
                            if (est_valide sudok (pos + 1)) then
                                possible := true
                        end
                done;
                sudok.(i).(j) <- 0;
                !possible
            end
;;

Si tu as plusieurs instructions dans un if ou un else, utilise un begin ... end. Une boucle for s'ouvre et se ferme avec do ... done.

Merci énormément mon programme est complet grace à toi, oui merci des conseils j'ai encore du mal avec ce langage. Encore une fois merci beaucoup.

Bonne soirée