test([[0,2,6,0,0,0,0,0,0],
        [0,0,0,0,0,1,9,4,0],
        [1,9,4,0,0,0,0,0,5],
        [0,0,0,0,5,3,0,0,2],
        [3,0,0,0,0,0,4,0,0],
        [0,8,7,0,0,0,0,6,3],
        [9,0,0,1,0,0,2,0,4],
        [8,0,3,7,0,5,0,0,9],
        [0,6,0,8,4,0,0,0,0]]).

indice(0).
indice(1).
indice(2).
indice(3).
indice(4).
indice(5).
indice(6).
indice(7).
indice(8).

valor(1).
valor(2).
valor(3).
valor(4).
valor(5).
valor(6).
valor(7).
valor(8).
valor(9).

sudo :- test(S), !, resolverSudoku(S), nl, fail.

resolverSudoku(S) :- sudoku(S,R), imprimeTablero(R).

sudoku(R,R) :- tableroCompleto(R).
sudoku(S,R) :-
  pasoSudoku(S,T),
  sudoku(T, R).

pasoSudoku(Inicio, Fin) :-
  eligeHueco(Inicio, F, C),
  valor(Val),
  compruebaEleccion(F, C, Inicio, Val),
  colocaNumero(F,C,Inicio,Val,Fin).

imprimeTablero([]) :- write('|-----------------------|'), nl.
imprimeTablero([F1|[F2|[F3|R]]]) :-
   write('|-----------------------|'), nl,
  writef("| %p %p %p | %p %p %p | %p %p %p |", F1), nl,
  writef("| %p %p %p | %p %p %p | %p %p %p |", F2), nl,
  writef("| %p %p %p | %p %p %p | %p %p %p |", F3), nl,
  imprimeTablero(R).

/* Reemplaza le elemento N de la lista */
reemplaza(0, [_|Cola], Nuevo, [Nuevo|Cola]).
reemplaza(N, [Cab|Cola], Nuevo, Result) :-
  N1 is N - 1,
  reemplaza(N1, Cola, Nuevo, Inter),
  append([Cab], Inter, Result).

/* Comprueba si el tablero está resuelto. */
tableroCompleto(T) :- nonvar(T), completo(T).
completo([]).
completo([F|R]) :-
  not(member(0, F)),
  completo(R).

/* Coloca Val en la posicion (F,C) de Estado, y lo mete en Siguiente */
colocaNumero(F, C, Estado, Val, Siguiente) :-
  nth0(F, Estado, Fila),
  reemplaza(C, Fila, Val, NuevaFila),
  reemplaza(F, Estado, NuevaFila, Siguiente).

/* Elige un hueco para colocar un número.
   Al resatisfacer, escoge el siguiente. */
eligeHueco(Estado, F, C) :-
  indice(F),
  indice(C),
  libre(F,C,Estado), !.

/* La posición está libre */
libre(NFila, NCol, Estado) :-
  nth0(NFila, Estado, Fila),
  nth0(NCol, Fila, Pos),
  Pos = 0 .

/* El estado es correcto */
compruebaEleccion(Fila, Columna, Estado, Valor) :-
  filaLibre(Fila, Estado, Valor),
  columnaLibre(Columna, Estado, Valor),
  sectorLibre(Fila, Columna, Estado, Valor).

/* La fila NFila no contiene Val todavía */
filaLibre(NFila, Estado, Val) :-
  nth0(NFila, Estado, Fila),
  not(member(Val, Fila)).

/* La columna NCol no contiene Val todavía */
columnaLibre(_, [], _).
columnaLibre(NCol, [F|R], Val) :-
  nth0(NCol, F, ValComp),
  ValComp \= Val,
  columnaLibre(NCol, R, Val).

/* El sector que contiene a (NFila, NColumna) no tiene Val */
sectorLibre(NFila, NCol, Estado, Val) :-
  F is 3 * (NFila // 3), F2 is F + 1, F3 is F + 2,
  C is 3 * (NCol // 3),
  filSecLibre(F, C, Estado, Val),
  filSecLibre(F2, C, Estado, Val),
  filSecLibre(F3, C, Estado, Val).

/* Comprueba que la fila de sector, que comienza en (F,C) no contiene V */
filSecLibre(F, C, Estado, V) :-
  C1 is C + 1, C2 is C + 2,
  nth0(F, Estado, F1),
  nth0(C, F1, Elm), Elm \= V,
  nth0(C1, F1, Elm1), Elm1 \= V,
  nth0(C2, F1, Elm2), Elm2 \= V.