Crear Sudoku.

[[seoane]]

Si te parece bien, vamos a poner un poco de código. Para resumir partimos de los siguiente:

El tipo TTablero es una matriz de 9x9
La función Valido nos dice si un numero, en esa posición, cumple con las reglas del Sudoku.
La función Obvio nos devuelve el único numero que puede ocupar esa posición, respetando las reglas, o 0 si puede haber mas de uno.
La función Resolver, resuelve el sudoku usando la estrategia "Backtracking"

El codigo, para generar Sudokus es el siguiente:

Código Delphi [-]
procedure GenerarTablero(var Tablero: TTablero; Dificultad: Integer);
var
  i,j,k,l: integer;
begin
  FillChar(Tablero,Sizeof(Tablero),0);
  Randomize;
  i:= 0;
  while i < NUM_COLUMNAS do
  begin
    j:= Random(9)+1;
    if Valido(Tablero, i, 0, j) then
    begin
      Tablero[i,0]:= j;
      inc(i)
    end;
  end;
  Resolver(Tablero);
  k:= 0;
  // Quitamos algunos obvios
  while k < 30 do
  begin
    i:= Random(NUM_COLUMNAS);
    j:= Random(NUM_FILAS);
    if Tablero[i,j] <> 0 then
    begin
      l:= Tablero[i,j];
      Tablero[i,j]:= 0;
      if Obvio(Tablero,i,j)>0 then
        inc(k)
      else
        Tablero[i,j]:= l;
    end;
  end;
  k:= 0;
  // Quitamos algunos que no son obvios
  while k < Dificultad do
  begin
    i:= Random(NUM_COLUMNAS);
    j:= Random(NUM_FILAS);
    if Tablero[i,j] <> 0 then
    begin
      l:= Tablero[i,j];
      Tablero[i,j]:= 0;
      if Obvio(Tablero,i,j)=0 then
        inc(k)
      else
        Tablero[i,j]:= l;
    end;
  end;
end;

Como ves primero rellenamos la primera fila del tablero con números del 0 al 9 de forma aleatoria pero respetando las normas a la hora de su colocación. Entonces mandamos el tablero a resolver, esto nos devuelve un tablero completamente lleno. Ahora es cuando empezamos a quitar números, primero quitamos números Obvios, es decir, solo quitamos números que se van a poder averiguar aplicando las normas. No se cuantos exactamente podemos quitar, pero por experiencia no muchos mas de 30, seguro que si buscas por internet encuentras algún matemático que te diga el numero exacto

Después de todo lo anterior tenemos un Sudoku, que con solo aplicar rigurosamente las normas puede ser resuelto. Para añadirle "dificultad", quitamos un par de números "no Obvios", de esta manera obligamos al jugador a aplicar el método de prueba y error para resolver el Sudoku, teniendo incluso que volver sobre sus pasos para resolverlo. El numero de "no Obvios" se lo paso como parámetro a la función, pudiendo así con una dificultad 0 crear Sudokus en los que la resolución es Obvia y no hay nunca que retroceder, si se aplican bien las reglas.

Caramba como me he liado.