Re: Récursivité

Le 15/01/2025 09:27, kurtz le pirate a écrit :

 Donc, voila le code C de la fonction :
  ——————————————————————————————————————————————————————————————————————
int solve(int board[SIZE][SIZE]) {
int row, col;
  if (!find_empty(board, &row, &col)) {
return 1;
}

for (int num = 1; num <= SIZE; num++) {
if (is_valid(board, num, row, col)) {
board[row][col] = num;
if (solve(board)) {
return 1;
}
board[row][col] = 0;
} // if (is_valid(board, num, row, col))
} // for (int num = 1; num <= SIZE; num++)

return 0;
}
  ——————————————————————————————————————————————————————————————————————

J'ai gardé ta fonction find_empty, même si elle n'est pas tellement efficace
puisqu'à chaque fois elle repart de [0][0].
typedef struct heap {
    int row, col;
    int num;
} heap_t;
int solve(int board[SIZE][SIZE]) {
    heap_t  heap[SIZE*SIZE];
    int     idx = 0;
    if (!find_empty(board, &(heap[idx].row), &(heap[idx].col))) {
        printf("Vous vous moquez, le sudoku est déjà terminé !\n");
        return 1;
    }
    heap[idx].num = 0;
    while (1) {
        int row = heap[idx].row;
        int col = heap[idx].col;
        if (heap[idx].num == SIZE) {
            // All possibilities are exhausted here
            board[row][col] = 0;
            if (idx == 0) {
                // No solution
                return 0;
            }
            idx--;
            continue;
        }
        heap[idx].num++;
        if (is_valid(board, heap[idx].num, row, col)) {
            board[row][col] = heap[idx].num;
            if (!find_empty(board, &row, &col)) {
                // Solution found
                return 1;
            }
            idx++;
            heap[idx].row = row;
            heap[idx].col = col;
            heap[idx].num = 0;
        }
    }
}
--
Olivier Miakinen