пропозиції роботи
konto usunięte
Temat: Ożywienie tematu :)
Witajcie, w kwestii ożywienia tematu zamieszczę prosty przykład swojego autorstwa. Wykazuje on, że w niektórych zastosowaniach warto do problemu podejść od strony programowania logicznego z ograniczeniami.Przykładem jest program do rozwiązania SUDOKU. Kod napisany w GNU Prolog. Zasady gry:
- w każdej kratce wartosci 1..9
- 9 pól i wartości w polach nie powtarzają się
- 9 wierszy i wartości w wierszach nie powtarzają się
- 9 kolumn i wartości w kolumnach nie powtarzają się
Napisanie programu to w tym przypadku jedynie określenie dziedzin dla zmiennych decyzyjnych oraz zdefiniowanie ograniczeń. W kodzie dodatkowy komentarz. Napisanie tego programu w języku imperatywnym byłoby co najmniej mniej czytelne i bardziej czasochłonne :)
q:- statistics(runtime,_),
%Definije zmienne decyzyjne dla kazdego pola
Pole1 = [A1,B1,C1,D1,E1,F1,G1,H1,I1],
Pole2 = [A2,B2,C2,D2,E2,F2,G2,H2,I2],
Pole3 = [A3,B3,C3,D3,E3,F3,G3,H3,I3],
Pole4 = [A4,B4,C4,D4,E4,F4,G4,H4,I4],
Pole5 = [A5,B5,C5,D5,E5,F5,G5,H5,I5],
Pole6 = [A6,B6,C6,D6,E6,F6,G6,H6,I6],
Pole7 = [A7,B7,C7,D7,E7,F7,G7,H7,I7],
Pole8 = [A8,B8,C8,D8,E8,F8,G8,H8,I8],
Pole9 = [A9,B9,C9,D9,E9,F9,G9,H9,I9],
%Zmienne decyzyjne dla kazdego wiersza
Wiersz1 = [A1,B1,C1,A2,B2,C2,A3,B3,C3],
Wiersz2 = [D1,E1,F1,D2,E2,F2,D3,E3,F3],
Wiersz3 = [G1,H1,I1,G2,H2,I2,G3,H3,I3],
Wiersz4 = [A4,B4,C4,A5,B5,C5,A6,B6,C6],
Wiersz5 = [D4,E4,F4,D5,E5,F5,D6,E6,F6],
Wiersz6 = [G4,H4,I4,G5,H5,I5,G6,H6,I6],
Wiersz7 = [A7,B7,C7,A8,B8,C8,A9,B9,C9],
Wiersz8 = [D7,E7,F7,D8,E8,F8,D9,E9,F9],
Wiersz9 = [G7,H7,I7,G8,H8,I8,G9,H9,I9],
%Zmienne decyzyjne dla kazdej kolumny
Kolumna1 = [A1,D1,G1,A4,D4,G4,A7,D7,G7],
Kolumna2 = [B1,E1,H1,B4,E4,H4,B7,E7,H7],
Kolumna3 = [C1,F1,I1,C4,F4,I4,C7,F7,I7],
Kolumna4 = [A2,D2,G2,A5,D5,G5,A8,D8,G8],
Kolumna5 = [B2,E2,H2,B5,E5,H5,B8,E8,H8],
Kolumna6 = [C2,F2,I2,C5,F5,I5,C8,F8,I8],
Kolumna7 = [A3,D3,G3,A6,D6,G6,A9,D9,G9],
Kolumna8 = [B3,E3,H3,B6,E6,H6,B9,E9,H9],
Kolumna9 = [C3,F3,I3,C6,F6,I6,C9,F9,I9],
%Okreslam dziedzine kazdej zmiennej decyzyjnej
fd_domain(Pole1,1,9),
fd_domain(Pole2,1,9),
fd_domain(Pole3,1,9),
fd_domain(Pole4,1,9),
fd_domain(Pole5,1,9),
fd_domain(Pole6,1,9),
fd_domain(Pole7,1,9),
fd_domain(Pole8,1,9),
fd_domain(Pole9,1,9),
%Definiuje ograniczenia dla pól: wszystkie wartosci rozne
fd_all_different(Pole1),
fd_all_different(Pole2),
fd_all_different(Pole3),
fd_all_different(Pole4),
fd_all_different(Pole5),
fd_all_different(Pole6),
fd_all_different(Pole7),
fd_all_different(Pole8),
fd_all_different(Pole9),
%Definiuje ograniczenia dla kolumn: wszystkie wartosci rozne
fd_all_different(Kolumna1),
fd_all_different(Kolumna2),
fd_all_different(Kolumna3),
fd_all_different(Kolumna4),
fd_all_different(Kolumna5),
fd_all_different(Kolumna6),
fd_all_different(Kolumna7),
fd_all_different(Kolumna8),
fd_all_different(Kolumna9),
%Definiuje ograniczenia dla wierszy: wszystkie wartosci rozne
fd_all_different(Wiersz1),
fd_all_different(Wiersz2),
fd_all_different(Wiersz3),
fd_all_different(Wiersz4),
fd_all_different(Wiersz5),
fd_all_different(Wiersz6),
fd_all_different(Wiersz7),
fd_all_different(Wiersz8),
fd_all_different(Wiersz9),
%Deklaracja wartosci znanych na początku
C1 #= 3,
E1 #= 1,
F1 #= 7,
G1 #= 2,
A2 #= 2,
B2 #= 8,
D2 #= 5,
H2 #= 7,
A3 #= 5,
B3 #= 7,
C3 #= 9,
D3 #= 3,
A4 #= 6,
C4 #= 1,
D4 #= 7,
F4 #= 5,
C5 #= 2,
E5 #= 3,
G5 #= 9,
H5 #= 1,
C6 #= 4,
D6 #= 8,
F6 #= 2,
G6 #= 6,
D7 #= 1,
E7 #= 3,
G7 #= 8,
I7 #= 6,
B8 #= 2,
F8 #= 7,
H8 #= 4,
I8 #= 5,
C9 #= 1,
D9 #= 2,
E9 #= 6,
G9 #= 7,
%Na podstawie dziedzin i ograniczen wyznaczam wartości dla zmiennych decyzyjnych
fd_labeling(Wiersz1),
fd_labeling(Wiersz2),
fd_labeling(Wiersz3),
fd_labeling(Wiersz4),
fd_labeling(Wiersz5),
fd_labeling(Wiersz6),
fd_labeling(Wiersz7),
fd_labeling(Wiersz8),
fd_labeling(Wiersz9),
%Podaje wynik
write('---------------------------------'),nl,
write('|'),write(Wiersz1),write('|'),nl,
write('|'),write(Wiersz2),write('|'),nl,
write('|'),write(Wiersz3),write('|'),nl,nl,
write('|'),write(Wiersz4),write('|'),nl,
write('|'),write(Wiersz5),write('|'),nl,
write('|'),write(Wiersz6),write('|'),nl,nl,
write('|'),write(Wiersz7),write('|'),nl,
write('|'),write(Wiersz8),write('|'),nl,
write('|'),write(Wiersz9),write('|'),nl,
write('---------------------------------'),nl,
statistics(runtime,[_,MS]), write('time : '),
write(MS),nl
.
:- initialization(q).
Tablice pola, wiersze oraz kolumny uzupełnione zgodnie z poniższym układem zmiennych decyzyjncyh (9x9):
A1 B1 C1 A2 B2 C2 A3 B3 C3
D1 E1 F1 D2 E2 F2 D3 E3 F3
G1 H1 I1 G2 H2 I2 G3 H3 I3
A4 B4 C4 A5 B5 C5 A6 B6 C6
D4 E4 F4 D5 E5 F5 D6 E6 F6
G4 H4 I4 G5 H5 I5 G6 H6 I6
A7 B7 C7 A8 B8 C8 A9 B9 C9
D7 E7 F7 D8 E8 F8 D9 E9 F9
G7 H7 I7 G8 H8 I8 G9 H9 I9
Warto zaznajomić się lepiej czy to z prologiem,czy innym językiem programowania logicznego z ograniczeniami (np OZ) i poszukać bibliotek tego języka dla języka używanego przez siebie. Dla gnu prolog nie znalazłem bibliotek dla javy,ale już widziałem takie rozszerzenia dla SWI prolog.
Może macie jakieś interesujące zastosowania? :)
PozdrawiamDżafar - Sadik Ridha edytował(a) ten post dnia 30.11.08 o godzinie 10:45
