Scribd Logo
Upload

Welcome to Scribd!

  • 12 views

    21hcs4108 Akansha-Nep

    Uploaded by

    Akansha Sharma
    The document describes several Prolog programs including implementing Tower of Hanoi, Hill Climbing search, Best First Search, A* search, Water Jug problem, Sudoku problem using constraint satisfaction, representing a family tree, knowledge representation using frames, concatenating lists, and reversing lists.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    21hcs4108 Akansha-Nep

    Uploaded by

    Akansha Sharma
    12 views16 pages
    The document describes several Prolog programs including implementing Tower of Hanoi, Hill Climbing search, Best First Search, A* search, Water Jug problem, Sudoku problem using constraint satisfaction, representing a family tree, knowledge representation using frames, concatenating lists, and reversing lists.

    Original Title

    21hcs4108.Akansha-Nep

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes several Prolog programs including implementing Tower of Hanoi, Hill Climbing search, Best First Search, A* search, Water Jug problem, Sudoku problem using constraint satisfaction, representing a family tree, knowledge representation using frames, concatenating lists, and reversing lists.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    12 views16 pages

    21hcs4108 Akansha-Nep

    Uploaded by

    Akansha Sharma
    The document describes several Prolog programs including implementing Tower of Hanoi, Hill Climbing search, Best First Search, A* search, Water Jug problem, Sudoku problem using constraint satisfaction, representing a family tree, knowledge representation using frames, concatenating lists, and reversing lists.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 16

    1.

    Write a program in Prolog to implement TowerOfHanoi(N) where N


    represents the number of disks.
    move(1,X,Y,_):-
    write('Move top disk from '),
    write(X),
    write(' to '),
    write(Y),
    nl.

    move(N,X,Y,Z):-
    N>1,
    M is N-1,
    move(M,X,Z,Y),
    move(1,X,Y,_),
    move(M,Z,Y,Z).

    tower_of_hanoi(N):-
    move(N,'A','C','B').
    2. Write a program to implement the Hill climbing search algorithm in Prolog.
    hill_climb(List, Max):-
    select_max(List, Max, Rest),
    hill_climb(Rest, Max, Max).

    hill_climb([], Max, Max).

    hill_climb(List, CurrentMax, Max):-


    select_max(List, NewMax, Rest),
    NewMax > CurrentMax,
    hill_climb(Rest, NewMax, Max).

    hill_climb(List, CurrentMax, Max):-


    select_max(List, NewMax, Rest),
    NewMax =< CurrentMax,
    hill_climb(Rest, CurrentMax, Max).

    %Select the maximum value in a list


    select_max([X], X, []).
    select_max([X|Xs], Max, [X|Rest]):-
    select_max(Xs, Max, Rest),
    Max > X.
    select_max([X|Xs], X, Xs):-
    select_max(Xs, Max, _),
    Max =< X.
    3. Write a program to implement the Best first Search algorithm in Prolog.
    % Best-First Search Algorithm

    % Perform best-first search


    best_first([[Goal|Path]|_], Goal, [Goal|Path], 0).
    best_first([Path|Queue], Goal, FinalPath, N) :-
    extend(Path, NewPaths),
    append(Queue, NewPaths, Queue1),
    sort_queue(Queue1, NewQueue),
    best_first(NewQueue, Goal, FinalPath, M),
    N is M + 1.

    % Extend the current path with new nodes


    extend([Node|Path], NewPaths) :-
    findall([NewNode, Node|Path],
    (arc(Node, NewNode, _),
    \+ member(NewNode, Path)), % Avoiding loops
    NewPaths).

    % Sort the queue based on heuristic values


    sort_queue(Queue, SortedQueue) :-
    predsort(compare_heuristic, Queue, SortedQueue).

    % Comparison predicate for sorting based on heuristic values


    compare_heuristic(Result, [Path1|_], [Path2|_]) :-
    heuristic(Path1, H1),
    heuristic(Path2, H2),
    compare(Result, H1, H2).
    % Define your heuristic function here
    heuristic(State, Value) :-
    % Define your heuristic evaluation logic here
    h(State, Value).

    % Define the graph connections


    arc(a, b, 1).
    arc(a, c, 3).
    arc(b, d, 2).
    arc(c, d, 1).
    arc(c, e, 2).
    arc(d, f, 3).
    arc(e, f, 2).

    % Entry point to run the best-first search algorithm


    run_best_first_search :-
    write('Enter the initial node: '),
    read(Start),
    write('Enter the goal node: '),
    read(Goal),
    % Perform best-first search
    best_first([[Start]], Goal, Path, ExploredNodes),
    % Output the results
    write('Optimal path: '), writeln(Path),
    write('Number of explored nodes: '), writeln(ExploredNodes).

    % Sample heuristic function (replace with your own)


    h(_, 0).
    4. Write a program to implement A* search algorithm in Prolog.
    % A* search algorithm

    % Main predicate to initiate the A* search


    astar(Start, Final, Path, TotalPath) :-
    estimation(Start, Final, E),
    astar1([(E, E, 0, [Start])], Final, Path, TotalPath).

    % Base case: When the final state is reached, return the path
    astar1([(_, _, Tp, [Final | R]) | _], Final, [Final | R], Tp) :-
    reverse([Final | R], Path),
    write('Path = '), write(Path).

    % Recursive case: Expand nodes, calculate costs, and continue


    search
    astar1([(_, _, P, [X | R1]) | R2], Final, C, Tp) :-
    findall((NewSum, E1, NP, [Z, X | R1]),
    (street(X, Z, V),
    \+ member(Z, R1),
    NP is P + V,
    estimation(X, Final, E1),
    NewSum is E1 + NP),
    L),
    append(R2, L, R3),
    sort(R3, R4),
    astar1(R4, Final, C, Tp).

    % Heuristic estimation function


    estimation(C1, C2, Est) :-
    area(C1, X1, Y1),
    area(C2, X2, Y2),
    DX is X1 - X2,
    DY is Y1 - Y2,
    Est is sqrt(DX * DX + DY * DY).

    % Example area and street predicates


    area(1, 20, 80).
    area(2, 50, 30).
    area(3, 100, 100).
    area(4, 90, 70).
    area(5, 70, 50).
    area(6, 110, 50).
    area(7, 150, 90).
    area(8, 200, 90).
    area(9, 140, 60).
    area(10, 160, 20).
    area(11, 180, 60).
    area(12, 190, 20).
    area(13, 230, 70).
    area(14, 240, 30).
    area(15, 240, 20).
    % Define other areas as needed

    street(1, 2, 50).
    street(1, 3, 100).
    street(1, 4, 75).
    street(1, 5, 65).
    street(2, 5, 30).
    street(3, 4, 40).
    street(3, 7, 50).
    street(4, 5, 25).
    street(4, 6, 30).
    street(4, 9, 65).
    street(4, 7, 70).
    street(5, 6, 30).
    street(6, 9, 35).
    street(6, 10, 60).
    street(7, 8, 35).
    street(7, 9, 30).
    street(8, 9, 70).
    street(8, 11, 40).
    street(8, 13, 50).
    street(9, 10, 50).
    street(9, 11, 30).
    street(10, 11, 50).
    street(10, 12, 40).
    street(11, 12, 40).
    street(11, 13, 50).
    street(11, 14, 60).
    street(12, 14, 50).
    street(13, 14, 50).
    % Define other streets as needed

    % Define start and final states


    start_state(s1).
    final_state(s_final).

    5. Write a program to implement the min-max search algorithm in Prolog.


    6. Write a program to solve the Water-Jug Problem in Prolog.
    % Define initial state
    initial_state((0, 0)).

    % Define goal state


    goal_state((4, _)).

    % Define actions possible in the problem


    action((Jug1, Jug2), fill_jug1, (5, Jug2)) :-
    Jug1 < 5.
    action((Jug1, Jug2), fill_jug2, (Jug1, 3)) :-
    Jug2 < 3.
    action((Jug1, Jug2), empty_jug1, (0, Jug2)) :-
    Jug1 > 0.
    action((Jug1, Jug2), empty_jug2, (Jug1, 0)) :-
    Jug2 > 0.
    action((Jug1, Jug2), pour_jug1_to_jug2, (NewJug1, NewJug2)) :-
    Jug1 > 0,
    Total is Jug1 + Jug2,
    NewJug2 is min(Total, 3),
    NewJug1 is Jug1 - (NewJug2 - Jug2).
    action((Jug1, Jug2), pour_jug2_to_jug1, (NewJug1, NewJug2)) :-
    Jug2 > 0,
    Total is Jug1 + Jug2,
    NewJug1 is min(Total, 5),
    NewJug2 is Jug2 - (NewJug1 - Jug1).

    % Define the solve predicate using depth-first search


    solve(State, Path) :-
    solve_dfs(State, [State], [], Path).

    solve_dfs(State, _, Path, [State|Path]) :-


    goal_state(State).
    solve_dfs(State, Visited, Path, FinalPath) :-
    action(State, Action, NextState),
    \+ member(NextState, Visited),
    solve_dfs(NextState, [NextState|Visited], [Action|Path],
    FinalPath).

    7. Implement sudoku problem(minimum 9x9 size) using constraint


    satisfaction in Prolog.
    :- use_module(library(clpfd)).
    sudoku(Rows):-
    length(Rows, 9),
    maplist(same_length(Rows), Rows),
    append(Rows, Vs),
    Vs ins 1..9,
    maplist(all_distinct, Rows),
    transpose(Rows, Columns),
    maplist(all_distinct, Columns),
    Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
    squares(As, Bs, Cs),
    squares(Ds, Es, Fs),
    squares(Gs, Hs, Is).
    squares([],[],[]).
    squares([N1,N2,N3|Ns1],
    [N4,N5,N6|Ns2],
    [N7,N8,N9|Ns3]):-
    all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
    squares(Ns1, Ns2, Ns3).

    % Print Sudoku grid


    print_sudoku([]).
    print_sudoku([Row|Rows]):-
    print_row(Row),
    print_sudoku(Rows).

    print_row([]):- nl.
    print_row([Cell|Row]):-
    format('~d', [Cell]),
    write(' '),
    (Row = [] -> true ; write(',')),
    print_row(Row).
    % Example Sudoku grid
    example_sudoku([
    [_, _, _, 2, 6, _, 7, _, 1],
    [6, 8, _, _, 7, _, _, 9, _],
    [1, 9, _, _, _, 4, 5, _, _],
    [8, 2, _, 1, _, _, _, 4, _],
    [_, _, 4, 6, _, 2, 9, _, _],
    [_, 5, _, _, _, 3, _, 2, 8],
    [_, _, 9, 3, _, _, _, 7, 4],
    [_, 4, _, _, 5, _, _, 3, 6],
    [7, _, 3, _, 1, 8, _, _, _]
    ]).

    solve_and_print_sudoku:-
    example_sudoku(Grid),
    sudoku(Grid),
    maplist(labeling([ff]), Grid),
    print_sudoku(Grid).

    8. Write a Prolog program to implement the family tree and demonstrate the
    family relationship.
    male(joy).
    male(sam).
    male(john).
    male(bob).
    male(jane).
    female(lisa).
    female(mary).
    female(susan).
    female(anisa).

    parent(sam,joy).
    parent(sam,lisa).
    parent(mary,joy).
    parent(mary,lisa).
    parent(bob,jane).
    parent(anisa,jane).
    parent(john,sam).
    parent(susan,sam).
    parent(john,bob).
    parent(susan,bob).

    father(F,C):-
    male(F),
    parent(F,C).

    mother(M,C):-
    female(M),
    parent(M,C).

    sibling(S1,S2):-
    parent(P,S1),
    parent(P,S2),
    S1\=S2.

    brother(B,P):-
    male(B),
    sibling(B,P).

    sister(S,P):-
    female(S),
    sibling(S,P).

    grandparent(Gp,Gc):-
    parent(Gp,P),
    parent(P,Gc).

    wife(W,H):-
    female(W),
    parent(H,C),
    parent(W,C),
    H\=W.
    husband(H,W):-
    male(H),
    parent(H,C),
    parent(W,C),
    H\=W.

    cousin(P1,P2):-
    parent(Parent1,P1),
    parent(Parent2,P2),
    sibling(Parent1,Parent2),
    P1\=P2.

    9. Write a Prolog program to implement knowledge representation using


    frames with appropriate examples.
    frame(john, [
    [name, 'John Doe'],
    [age, 30],
    [gender, male],
    [occupation, engineer]
    ]).

    frame(jane, [
    [name, 'Jane Smith'],
    [age, 28],
    [gender, female],
    [occupation, doctor]
    ]).

    frame(car1, [
    [make, toyota],
    [model, 'Corolla'],
    [year, 2018],
    [color, blue]
    ]).

    frame(car2, [
    [make, honda],
    [model, 'Civic'],
    [year, 2020],
    [color, red]
    ]).

    get_frame_property(Frame, Property, Value) :-


    frame(Frame, Properties),
    member([Property, Value], Properties).

    % Example queries:
    % Get the name of John
    % ?- get_frame_property(john, name, Name).
    %
    % Get the color of car2
    % ?- get_frame_property(car2, color, Color).
    10. Write a Prolog Program to implement conc(L1,L2,L3) where appended with
    L1 to get the resulted L3.
    conc([], L, L).
    conc([X1|L1], L2, [X1|L3]) :-
    append(L1,L2,L3).

    11. Write a Prolog program to implement reverse(L,R) where List Li is a


    reversed list.
    reverse(L,R):-
    accReverse(L,[],R).

    accReverse([H|T],A,R):-
    accReverse(T,[H|A],R).
    accReverse([],A,A).
    12. Write a Prolog program to generate a parse tree of given sentences
    assuming the grammar required for parsing.
    % Defining the grammar rules.
    sentence(Tree) --> noun_phrase(NP), verb_phrase(VP), {Tree = [NP,
    VP]}.
    noun_phrase(Tree) --> determiner(Det), noun(N), {Tree = np(Det, N)}.
    verb_phrase(Tree) --> verb(V), noun_phrase(NP), {Tree = vp(V, NP)}.

    % Lexical rules.
    determiner(the) --> [the].
    determiner(a) --> [a].
    noun(cat) --> [cat].
    noun(dog) --> [dog].
    verb(chased) --> [chased].
    verb(ate) --> [ate].

    % Example query to generate a parse tree


    % ?- phrase(sentence(Tree), [the, cat, chased, a, dog]).

    13. Write a Prolog program to recognize context free grammar a n b n .


    % Define the grammar rules.
    s --> [].
    s --> [a], s, [b].

    % Define the recognizer.


    recognize(S) :-
    phrase(s, S).

    You might also like