Download Enunciado

PRACTICA de PROGRAMACIÓN LOGICA - Curso 2005/06
La práctica se puede hacer individualmente o en grupo de dos personas como máximo.
DOCUMENTACIÓN DE LA PRÁCTICA
•
•
•
•
•
•
Nombre(s) de los integrantes del grupo.
Enunciado del problema.
Explicación de las estrategias nuevas añadidas.
Especificación de los predicados nuevos (modo de uso) y un comentario sobre lo
que hacen.
Implementación de dichos predicados (cláusulas añadidas).
Juego de pruebas con varios ejemplos solucionados.
REALIZACIÓN Y FECHA DE ENTREGA
•
•
La fecha de entrega tope será el 30 de mayo de 2006. Día del examen de la
asignatura
La documentación debe entregarse en papel y en formato electrónico.
ENUNCIADO de la PRACTICA: “SUDOKU”
Se pretende realizar un programa que solucione Sudokus.
Para más información consultar http://www.sudokusolver.co.uk/
REGLAS del JUEGO
Se juega en un tablero de 9x9 casillas, subdividido en nueve cuadrantes de 3x3,
con algunos dígitos (del 1 al 9) fijos en el tablero, como se muestra abajo.
El jugador debe rellenar las casillas vacías con dígitos del 1 al 9, de modo que
no se repita ningún digito en cada fila, columna o cuadrante.
•
•
EJEMPLO de movimiento posible
5
3
7
8 4
9
9 3
4 7
1
3
2
Añadir el 3 en (8,4)
6 8
2 3
2
3
8
5
1
7
3
7
8 4
9
9 3
4 7
1
1
3
2
6 8
2 3
2 3
6
4
3
8
7
6
4
PROGRAMA
Se pide escribir (parte de) un programa que solucione Sudokus. En concreto, se deben
implementar dentro de:
%%%% ESTA ES LA PARTE A RELLENAR POR LOS ALUMNOS/AS: %%%%
a. El predicado denominado sin_backtraking
sin_backtraking(L,S): repite el proceso de aplicar las estrategias definidas (mientras
haya modificaciones posibles en la matriz L) obteniendo S.
b. Estrategias para reducir las listas de posibilidades con lógica.
Como mínimo estas dos estrategias (aunque es deseable que se hagan más):
Estrategia 1: Si en una fila (resp. columna, cuadrante) sólo hay una posición para un
número, se elimina de esa posición todos los demás números
Estrategia 2: Si en una fila (resp. columna, cuadrante) sólo hay un número en una
posición, se elimina dicho número de las demás posiciones de la fila (resp. columna,
cuadrante).
DATOS PROPORCIONADOS
%%%%
Operaciones para manipulación de la matriz
%%%%%%%%%
%% El sudoku se representa mediante una matriz, es decir,
%% es una lista de 9 filas, donde cada fila contiene 9 elementos.
%% Estos elementos son listas que inicialmente contienen un número
%% (del 1 al 9) o están vacías (sin números), pero que en general
%% cotienen las distintas posibilidades para esa posición.
%%%% Traspuesta de la matriz
%% traspuesta: obtenemos una matriz donde cada fila es una columna de la original.
traspuesta([L], T):columnas(L,T).
traspuesta([L|RL], T):traspuesta(RL, T2),
mezclar(L, T2, T).
columnas([], []).
columnas([X|RX], [[X]|RZ]):columnas(RX, RZ).
mezclar([], [], []).
mezclar([X|RX], [L|RL], [[X|L]|RR]):mezclar(RX, RL, RR).
%%%%%%% Cuadrantes de 3x3
%% cuadrados: obtenemos una matriz donde cada fila es un cuadrante de la original.
cuadrados([],[]).
cuadrados([L1,L2,L3|RL], C):tripletas(L1, L2, L3, L),
cuadrados(RL, R),
append(L, R, C).
tripletas([], [], [], []).
tripletas([X11, X12, X13|L1], [X21, X22, X23|L2], [X31, X32, X33|L3],
[[X11, X12, X13, X21, X22, X23, X31, X32, X33]|L]):tripletas(L1, L2, L3, L).
%%%%%% Escritura de la matriz
%% escribir: imprime en pantalla la matriz por filas.
escribir([]).
escribir([L|RL]):write(L), nl,
escribir(RL).
%%%%%% Inicializar el sudoku de partida dado para su ejecución
%% iniciar: rellena cada posición vacía de la matriz con todos los números (1 al 9).
iniciar([], []).
iniciar([F|RF], [I|RI]):iniciar_fila(F, I),
iniciar(RF, RI).
iniciar_fila([], []).
iniciar_fila([L|RL], [L|RY]):- length(L, 1),!,iniciar_fila(RL, RY).
iniciar_fila([L|RL], [[1, 2, 3, 4, 5, 6, 7, 8, 9]|RY]):length(L,0),iniciar_fila(RL, RY).
%%%% Operaciones de comprobación de propiedades sobre la matriz %%%
%% listas_unicas: comprueba si cada posición de la matriz contiene un único número.
listas_unicas([]).
listas_unicas([F|RF]):unitarios(F),
listas_unicas(RF).
unitarios([]).
unitarios([L|RL]):length(L, 1),
unitarios(RL).
%% Dada una matriz que verifica el predicado "listas_unicas" (precondición),
%% listas_diferentes: comprueba si cada fila de la matriz es un conjunto (sin
repetidos).
listas_diferentes([]).
listas_diferentes([L|RL]):is_set(L),
listas_diferentes(RL).
%% Dada una matriz que verifica el predicado "listas_unicas" (precondición),
%% correcta: comprueba si no hay repetidos en cada fila, cada columna y cada
cuadrante.
correcta(S):listas_diferentes(S),
traspuesta(S, S1),
listas_diferentes(S1),
cuadrados(S1, S2),
listas_diferentes(S2).
%%%% Operaciones de obtención de datos sobre la matriz %%%%
%% div_pos: Dada una lista genérica y una posición, obtiene
%% la sublista anterior y la sublista siguiente a dicha posición.
div_pos([], N, [], []):N > 0.
div_pos([_|RX], 1, [], RX).
div_pos([Y|RY], N, [Y|L1], L2):N > 1,
M is N-1,
div_pos(RY, M, L1, L2).
%% minima: cardinal del menor elemento del sudoku,
%% esto es, de la lista más pequeña de posibilidades no unitaria.
minima([], 10).
minima([F|RF], X):minima_fila(F, N),
minima(RF, NF),
X is min(N, NF).
minima_fila([], 10).
minima_fila([L|RL], NL):length(L, 1),!,
minima_fila(RL, NL).
minima_fila([L|RL], X):length(L, N),
N>1,
minima_fila(RL, NL),
X is min(N, NL).
%%%%%%%%%
Algoritmo principal
%%%%%%%%%
%% Dado un sudoku de partida ya inicializado (precondición),
%% sol: busca una matriz solución (con listas únicas y correcta).
sol(L,S):sin_backtraking(L,R),
write('sin backtracking se obtiene:'), nl,
solucion(R,S).
solucion(R,R) :- listas_unicas(R),!, comprobar(R).
solucion(R,S) :- escribir(R), nl, dar_un_paso(R, R1), sol(R1,S).
comprobar(R) :- correcta(R),!.
comprobar(R) :- escribir(R), write('es una solucion incorrecta'), nl, fail.
%% dar_un_paso: busca una posición de la matriz (con número mínimo de
%% posiblidades) y selecciona uno de dichos números para dicha posición.
dar_un_paso(S, R):minima(S, M),
write(M), write(' posibilidades:'), nl,
nth1(P, S, F),
nth1(N, F, L),
length(L, M), !,
div_pos(S, P, S1, S2),
div_pos(F, N, F1, F2),
member(X, L),
write('probamos con '), write(X),
write(' en la posicion '), write((P,N)),nl,
append(F1, [[X]], FN),
append(FN, F2, FNN),
append(S1, [FNN], RS),
append(RS, S2, R).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
ESTA ES LA PARTE A RELLENAR POR LOS ALUMNOS/AS:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% sin_backtraking: repite e proceso de aplicar las estrategias definidas
%% mientras haya modificaciones posibles en la matriz.
%%%% Estrategias para reducir las listas de posibilidades con lógica
%%% Estrategia 1: Si en una fila sólo hay una posición para un número,
%%% elimina de esa posición todos los demás números
%%% Estrategia 2: Si en una fila sólo hay un número en una posición,
%%% elimina de las demás posiciones dicho número
%%% Otras estrategias.
JUEGOS DE PRUEBA
- Para test1 y test2 son suficientes las dos estrategias mínimas (sin backtracking).
- Para test3, test4 y test5 no son suficientes las dos estrategias mínimas, esto es, si no se
añaden más estrategias será necesario el uso de backtracking.
- Por último, con test6 se muestra que, en algunos casos, hay problemas de eficiencia
(por el uso excesivo del backtracking) si no se añaden más estrategias adecuadas.
test1 :L=[
[[ ],[6],[ ],[1],[ ],[4],[ ],[5],[ ]],
[[ ],[ ],[8],[3],[ ],[5],[6],[ ],[ ]],
[[2],[ ],[ ],[ ],[ ],[ ],[ ],[ ],[1]],
[[8],[ ],[ ],[4],[ ],[7],[ ],[ ],[6]],
[[ ],[ ],[6],[ ],[ ],[ ],[3],[ ],[ ]],
[[7],[ ],[ ],[9],[ ],[1],[ ],[ ],[4]],
[[5],[ ],[ ],[ ],[ ],[ ],[ ],[ ],[2]],
[[ ],[ ],[7],[2],[ ],[6],[9],[ ],[ ]],
[[ ],[4],[ ],[5],[ ],[8],[ ],[7],[ ]]
],
iniciar(L, Y), sol(Y, S), escribir(S).
test2:L=[
[[ ],[ ],[4],[ ],[ ],[3],[ ],[7],[ ]],
[[ ],[8],[ ],[ ],[7],[ ],[ ],[ ],[ ]],
[[ ],[7],[ ],[ ],[ ],[8],[2],[ ],[5]],
[[4],[ ],[ ],[ ],[ ],[ ],[3],[1],[ ]],
[[9],[ ],[ ],[ ],[ ],[ ],[ ],[ ],[8]],
[[ ],[1],[5],[ ],[ ],[ ],[ ],[ ],[4]],
[[1],[ ],[6],[9],[ ],[ ],[ ],[3],[ ]],
[[ ],[ ],[ ],[ ],[2],[ ],[ ],[6],[ ]],
[[ ],[2],[ ],[4],[ ],[ ],[5],[ ],[ ]]
],
iniciar(L, Y), sol(Y, S), escribir(S).
test3 :L= [
[[8],[ ],[3],[ ],[2],[9],[7],[1],[6]],
[[ ],[ ],[6],[ ],[1],[8],[5],[ ],[4]],
[[ ],[ ],[ ],[ ],[6],[ ],[ ],[ ],[8]],
[[ ],[ ],[5],[ ],[4],[6],[ ],[8],[ ]],
[[7],[ ],[9],[ ],[3],[5],[6],[4],[2]],
[[ ],[6],[ ],[ ],[9],[ ],[1],[ ],[5]],
[[6],[ ],[ ],[ ],[7],[ ],[ ],[5],[1]],
[[ ],[ ],[1],[6],[5],[ ],[8],[ ],[ ]],
[[5],[ ],[ ],[9],[8],[1],[4],[6],[3]]
],
iniciar(L, Y), sol(Y, S), escribir(S).
test4:L =[
[[ ],[ ],[ ],[1],[ ],[7],[2],[ ],[ ]],
[[ ],[1],[ ],[ ],[ ],[ ],[ ],[6],[9]],
[[ ],[ ],[ ],[6],[ ],[ ],[8],[ ],[1]],
[[9],[2],[ ],[ ],[ ],[3],[ ],[ ],[ ]],
[[ ],[ ],[7],[ ],[ ],[ ],[6],[ ],[ ]],
[[ ],[ ],[ ],[7],[ ],[ ],[ ],[9],[4]],
[[6],[ ],[8],[ ],[ ],[9],[ ],[ ],[ ]],
[[2],[5],[ ],[ ],[ ],[ ],[ ],[3],[ ]],
[[ ],[ ],[4],[8],[ ],[1],[ ],[ ],[ ]]
],
iniciar(L, Y), sol(Y, S), escribir(S).
test5:L =[
[[1],[ ],[ ],[8],[ ],[ ],[ ],[3],[ ]],
[[7],[ ],[ ],[ ],[ ],[ ],[ ],[2],[ ]],
[[ ],[ ],[ ],[5],[6],[ ],[ ],[7],[ ]],
[[ ],[ ],[8],[ ],[ ],[ ],[9],[ ],[ ]],
[[ ],[ ],[5],[2],[1],[7],[4],[ ],[ ]],
[[ ],[ ],[4],[ ],[ ],[ ],[7],[ ],[ ]],
[[ ],[3],[ ],[ ],[8],[9],[ ],[ ],[ ]],
[[ ],[2],[ ],[ ],[ ],[ ],[ ],[ ],[8]],
[[ ],[8],[ ],[ ],[ ],[4],[ ],[ ],[6]]
],
iniciar(L, Y), sol(Y, S), escribir(S).
test6:L =[
[[7],[ ],[ ],[ ],[ ],[ ],[ ],[1],[9]],
[[4],[6],[ ],[1],[9],[ ],[ ],[ ],[ ]],
[[ ],[ ],[ ],[6],[8],[2],[7],[ ],[4]],
[[ ],[9],[ ],[ ],[ ],[ ],[ ],[ ],[7]],
[[ ],[ ],[ ],[3],[ ],[ ],[4],[ ],[5]],
[[ ],[ ],[6],[7],[ ],[ ],[ ],[ ],[ ]],
[[ ],[ ],[1],[ ],[ ],[ ],[ ],[ ],[ ]],
[[2],[ ],[ ],[ ],[7],[4],[ ],[ ],[ ]],
[[ ],[ ],[ ],[2],[ ],[ ],[3],[ ],[ ]]
],
iniciar(L, Y), sol(Y, S), escribir(S).