16 - Ejemplo práctico 7: asistente de Sudoku con pilas

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

#define N 9

typedef struct {
  int fila;
  int col;
  int candidatos[N];
  int idx;
} Decision;

typedef struct {
  Decision data[N * N];
  int top;
} StackDecision;

static int tablero[N][N];

void stack_push(StackDecision *s, Decision d) { s->data[s->top++] = d; }
Decision stack_pop(StackDecision *s) { return s->data[--s->top]; }
int stack_empty(const StackDecision *s) { return s->top == 0; }
Decision *stack_peek(StackDecision *s) { return s->top ? &s->data[s->top - 1] : NULL; }

int es_valido(int fila, int col, int valor) {
  for (int i = 0; i < N; ++i) {
    if (tablero[fila][i] == valor || tablero[i][col] == valor) return 0;
  }
  int sf = fila / 3 * 3;
  int sc = col / 3 * 3;
  for (int i = 0; i < 3; ++i)
    for (int j = 0; j < 3; ++j)
      if (tablero[sf + i][sc + j] == valor) return 0;
  return 1;
}

int siguiente_vacio(int *fila, int *col) {
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
      if (tablero[i][j] == 0) { *fila = i; *col = j; return 1; }
  return 0;
}

void construir_candidatos(Decision *d) {
  d->idx = 0;
  int pos = 0;
  for (int valor = 1; valor <= N; ++valor) {
    if (es_valido(d->fila, d->col, valor)) d->candidatos[pos++] = valor;
  }
  while (pos < N) d->candidatos[pos++] = 0;
}

int resolver(void) {
  StackDecision stack = {.top = 0};
  while (1) {
    int fila, col;
    if (!siguiente_vacio(&fila, &col)) return 1;
    Decision decision = {.fila = fila, .col = col};
    construir_candidatos(&decision);
    int colocado = 0;
    while (decision.idx < N && decision.candidatos[decision.idx]) {
      int valor = decision.candidatos[decision.idx++];
      if (es_valido(fila, col, valor)) {
        tablero[fila][col] = valor;
        stack_push(&stack, decision);
        colocado = 1;
        break;
      }
    }
    if (colocado) continue;
    while (!stack_empty(&stack)) {
      Decision retro = stack_pop(&stack);
      tablero[retro.fila][retro.col] = 0;
      while (retro.idx < N && retro.candidatos[retro.idx]) {
        int valor = retro.candidatos[retro.idx++];
        if (es_valido(retro.fila, retro.col, valor)) {
          tablero[retro.fila][retro.col] = valor;
          stack_push(&stack, retro);
          goto siguiente;
        }
      }
    }
    return 0;
siguiente:
    continue;
  }
}

void imprimir(void) {
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      printf("%d ", tablero[i][j]);
    }
    putchar('\n');
  }
}

int main(void) {
  int puzzle[N][N] = {
    {5,3,0,0,7,0,0,0,0},
    {6,0,0,1,9,5,0,0,0},
    {0,9,8,0,0,0,0,6,0},
    {8,0,0,0,6,0,0,0,3},
    {4,0,0,8,0,3,0,0,1},
    {7,0,0,0,2,0,0,0,6},
    {0,6,0,0,0,0,2,8,0},
    {0,0,0,4,1,9,0,0,5},
    {0,0,0,0,8,0,0,7,9}
  };
  memcpy(tablero, puzzle, sizeof(tablero));
  if (resolver()) {
    puts("Sudoku resuelto:");
    imprimir();
  } else {
    puts("Sin solución.");
  }
  return 0;
}