Re: Récursivité

Le 16/01/2025 11:20, Olivier Miakinen a écrit :

 
[fonction solve sans récursion]

Test avec ma fonction :
################################################################################

Avant résolution :
+---+---+---+
| 1 | 4 |28 |
|25 |83 | 69|
| 84|   |   |
+---+---+---+
|   | 5 |9  |
|7  |39 | 28|
|196|28 | 73|
+---+---+---+
|  8|   |69 |
|  9|76 |815|
| 6 | 28|   |
+---+---+---+

Après résolution :
+---+---+---+
|613|549|287|
|257|831|469|
|984|672|351|
+---+---+---+
|832|157|946|
|745|396|128|
|196|284|573|
+---+---+---+
|378|415|692|
|429|763|815|
|561|928|734|
+---+---+---+

################################################################################

Le programme complet :
################################################################################

#include <stdio.h>

#define SQR_SIZE    3
#define SIZE        (SQR_SIZE * SQR_SIZE)

int BOARD[SIZE][SIZE] = {
    { 0, 1, 0,  0, 4, 0,  2, 8, 0 },
    { 2, 5, 0,  8, 3, 0,  0, 6, 9 },
    { 0, 8, 4,  0, 0, 0,  0, 0, 0 },

    { 0, 0, 0,  0, 5, 0,  9, 0, 0 },
    { 7, 0, 0,  3, 9, 0,  0, 2, 8 },
    { 1, 9, 6,  2, 8, 0,  0, 7, 3 },

    { 0, 0, 8,  0, 0, 0,  6, 9, 0 },
    { 0, 0, 9,  7, 6, 0,  8, 1, 5 },
    { 0, 6, 0,  0, 2, 8,  0, 0, 0 }
};

/**************************************************************/

void print_delim() {
    for (int col = 0; col < SIZE; col++) {
        if (col % SQR_SIZE == 0) putchar('+');
        putchar('-');
    }
    puts("+");
}
void print_board(int board[SIZE][SIZE]) {
    for (int row = 0; row < SIZE; row++) {
        if (row % SQR_SIZE == 0) print_delim();
        for (int col = 0; col < SIZE; col++) {
            if (col % SQR_SIZE == 0) putchar('|');
            int num = board[row][col];
            putchar(num ? '0'+num : ' ');
        }
        puts("|");
    }
    print_delim();
    fflush(stdout);
}

/**************************************************************/

int find_empty(int board[SIZE][SIZE], int *prow, int *pcol) {
   int row, col;

   for (row = 0; row < SIZE; row++) {
     for (col = 0; col < SIZE; col++) {
       if (board[row][col] == 0) {
         *prow = row;
         *pcol = col;
         return 1;
         }
       }
     }
   return 0;
   }

/**************************************************************/

int is_conflict(int row0, int col0, int row, int col) {
    if ((row0 == row) && (col0 == col)) return 0;  // same cell
    if (row0 == row) return 1;  // same row
    if (col0 == col) return 1;  // same col
    if ((row0 / SQR_SIZE == row / SQR_SIZE) &&
        (col0 / SQR_SIZE == col / SQR_SIZE)) {
        return 1;   // same squared zone
    }
    return 0;   // ok
}
int is_valid(int board[SIZE][SIZE], int num, int row0, int col0) {
    for (int row = 0; row < SIZE; row++) {
        for (int col = 0; col < SIZE; col++) {
            if ((board[row][col] == num) &&
                is_conflict(row0, col0, row, col)
            ) return 0;
        }
    }
    return 1;
}

/**************************************************************/

#if 0   // Old function with recursion
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;
}
#endif

/**************************************************************/

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;
        }
    }
}

/**************************************************************/

int main() {
    printf("Avant résolution :\n");
    print_board(BOARD);

    if (solve(BOARD)) {
        printf("\nAprès résolution :\n");
        print_board(BOARD);
    } else {
        printf("\nSolution non trouvée.\n");
    }
}



--
Olivier Miakinen