Logo 
Search:

Artificial Intelligence Articles

Submit Article
Home » Articles » Artificial Intelligence » ProLogRSS Feeds

Prolog program of 8-puzzle using heuristic function % with best first search technique

Posted By: Milind Mishra     Category: Artificial Intelligence     Views: 18839

Prolog program of 8-puzzle using heuristic function % with best first search technique.

Code for Prolog program of 8-puzzle using heuristic function % with best first search technique in Artificial Intelligence

domains
    value, row, col, gval, hval, pval, sval, parent, nodeno = integer
    nodevalue=ndval(value,row,col)
    nodelist=nodevalue*
    loclist=value*
    poslist=posval(loclist,value)
    nodestruct=ndstruct(nodelist,value,value,value,value)
    hvallist=nodestruct*
    
database
    opennodeinfo(nodelist,value,value,value,value).
    closenodeinfo(nodelist,value,value,value,value).
    bestnodeinfo(nodelist,value,value,value,value).
    nvalue(value,row,col).
    rowcolCounter(value).
    nodeNo(value).
    currParent(value).

predicates
    displayPuzzle.
    displayNodeList(nodelist).
    calHvalue(nodelist,value).
    calPvalue(nodelist,value).
    getNodeInfo(nodevalue,value,row,col).
    finalnode(nodelist,hval).
    pvalue(value, poslist).
    findStepsFar(value,poslist,value).
    memberOfLocList(value,loclist).
    moveLeft.
    moveRight.
    moveUp.
    moveDown.
    findValue(row,col,value).
    findBlank(row,col).
    setNewPos(value,row,col).
    setCurrNode(nodelist).
    emptyCurrNode.
    genNodeList(nodelist,nodelist). 
    genHvalList(hvallist,hvallist).
    input.
    performSearch.
    processCurrNode.
    checkInOpen(nodelist,value).
    checkInClose(nodelist,value).
    bubblesort(hvallist,hvallist).
    swap(hvallist,hvallist).
    insertSortedList(hvallist).

clauses

    finalnode([ndval(1,0,0),ndval(2,0,1),ndval(3,0,2),ndval(8,1,0),
        ndval(0,1,1),ndval(4,1,2),ndval(7,2,0),ndval(6,2,1),
        ndval(5,2,2)],0).

    pvalue(1,posval([0],0)).
    pvalue(1,posval([1,3],1)).
    pvalue(1,posval([2,6,4],2)).
    pvalue(1,posval([7,5],3)).
    pvalue(1,posval([8],4)).

    pvalue(2,posval([1],0)).
    pvalue(2,posval([0,2,4],1)).
    pvalue(2,posval([3,5,7],2)).
    pvalue(2,posval([6,8],3)).

    pvalue(3,posval([2],0)).
    pvalue(3,posval([1,5],1)).
    pvalue(3,posval([0,4,8],2)).
    pvalue(3,posval([3,7],3)).
    pvalue(3,posval([6],4)).

    pvalue(4,posval([5],0)).
    pvalue(4,posval([2,4,8],1)).
    pvalue(4,posval([1,3,7],2)).
    pvalue(4,posval([0,6],3)).

    pvalue(5,posval([8],0)).
    pvalue(5,posval([5,7],1)).
    pvalue(5,posval([2,4,6],2)).
    pvalue(5,posval([1,3],3)).
    pvalue(5,posval([0],4)).

    pvalue(6,posval([7],0)).
    pvalue(6,posval([4,6,8],1)).
    pvalue(6,posval([1,3,5],2)).
    pvalue(6,posval([0,2],3)).

    pvalue(7,posval([6],0)).
    pvalue(7,posval([3,7],1)).
    pvalue(7,posval([0,4,8],2)).
    pvalue(7,posval([1,5],3)).
    pvalue(7,posval([2],4)).

    pvalue(8,posval([3],0)).
    pvalue(8,posval([0,4,6],1)).
    pvalue(8,posval([1,5,7],2)).
    pvalue(8,posval([2,8],3)).

    pvalue(0,posval([4],0)).
    pvalue(0,posval([1,3,5,7],1)).
    pvalue(0,posval([0,2,6,8],2)).

    input:-
        assert(opennodeinfo([ndval(2,0,0),ndval(1,0,1),
            ndval(6,0,2),ndval(4,1,0),ndval(0,1,1),
            ndval(8,1,2),ndval(7,2,0),ndval(5,2,1),
            ndval(3,2,2)],0,0,0,0)),
        assert(rowcolCounter(8)),
        assert(nodeNo(1)),
        assert(currParent(0)).

    displayPuzzle:-
        genNodeList([],Nodelist),
        bestnodeinfo(Nodelist,Hval,Gval,Parent,Nodeno),
        displayNodeList(Nodelist),
        write("h(n) : ",Hval),nl,
        write("g(n) : ",Gval),nl,
        write("parent(n) : ",Parent),nl,
        write("nodno(n) : ",Nodeno).

    displayNodeList([]).
    displayNodeList([ndval(Value1,_,_),ndval(Value2,_,_),ndval(Value3,_,_)|Tail]):-
        write(Value1," "), write(Value2," "), write(Value3," "),nl,
        displayNodeList(Tail).

    getNodeInfo(ndval(Value,Row,Col),Value,Row,Col).

    emptyCurrNode:-
        retractall(nvalue(_,_,_)).
        
    setCurrNode([]):- !.
    setCurrNode([ndval(Value,Row,Col)|Tail]):-
        assert(nvalue(Value,Row,Col)),
        setCurrNode(Tail).
        
    calHvalue(NodeList,Hval):-
        calPvalue(NodeList,Pval),
        Hval=Pval.

    calPvalue([],0):- !.
    calPvalue([Head|Tail],Pval):-
        getNodeInfo(Head,Value,Row,Col),
        CurrPos=(Row*3)+Col,
        pvalue(Value,PosList),
        findStepsFar(CurrPos,PosList,Steps),
        calPvalue(Tail,NewPval),
        Pval=Steps+NewPval.

    findStepsFar(CurrPos,posval(LocList,Steps),Steps):-
        memberOfLocList(CurrPos,LocList).

    memberOfLocList(CurrPos,[CurrPos|_]) :- !.
    memberOfLocList(CurrPos,[_|Rest]):-
        memberOfLocList(CurrPos,Rest).

    moveLeft:-
        findBlank(Row,Col),
        Col>0,
        NewCol=Col-1,
        findValue(Row,NewCol,Value),
        setNewPos(Value,Row,Col),
        setNewPos(0,Row,NewCol),
        write("\nleft successor"),
        processCurrNode,
        setNewPos(0,Row,Col),
        setNewPos(Value,Row,NewCol),!.
    moveLeft.

    moveRight:-
        findBlank(Row,Col),
        Col<2,
        NewCol=Col+1,
        findValue(Row,NewCol,Value),!,
        setNewPos(Value,Row,Col),
        setNewPos(0,Row,NewCol),
        write("\nright successor"),
        processCurrNode,
        setNewPos(0,Row,Col),
        setNewPos(Value,Row,NewCol),!.
    moveRight.

    moveUp:-
        findBlank(Row,Col),
        Row>0,
        NewRow=Row-1,
        findValue(NewRow,Col,Value),
        setNewPos(Value,Row,Col),
        setNewPos(0,NewRow,Col),
        write("\nup successor"),
        processCurrNode,
        setNewPos(0,Row,Col),
        setNewPos(Value,NewRow,Col),!.
    moveUp.

    moveDown:-
        findBlank(Row,Col),
        Row<2,
        NewRow=Row+1,
        findValue(NewRow,Col,Value),
        setNewPos(Value,Row,Col),
        SetNewPos(0,NewRow,Col),
        write("\ndown successor"),
        processCurrNode,
        setNewPos(0,Row,Col),
        setNewPos(Value,NewRow,Col),!.
    moveDown.
    
    processCurrNode:-
        genNodeList([],Nodelist),
        checkInOpen(Nodelist,Oval),
        Oval=1,
        checkInClose(Nodelist,Cval),
        Cval=1,
        calHvalue(Nodelist,Hval),
        currParent(Parent),
        Gval=Parent+1,
        nodeNo(Nodeno),
        NewNodeno=Nodeno+1,
        retract(nodeNo(Nodeno)),
        assert(nodeNo(NewNodeno)),
        assert(opennodeinfo(Nodelist,Hval,Gval,Parent,Nodeno)),
        nl,displayNodeList(Nodelist), write("Parent : ",Parent," Nodeno : ",Nodeno),
        readchar(_),
        genHvalList([],HvalList),
        bubblesort(HvalList,SortedList),
        insertSortedList(SortedList).
    processCurrNode.

    checkInOpen(Nodelist,Oval):-
        Oval=1,
        not(opennodeinfo(Nodelist,_,_,_,_)),!.
    checkInOpen(Nodelist,Oval):-
        opennodeinfo(Nodelist,_,_,_,_),
        Oval=0.
    
    checkInClose(Nodelist,Cval):-
        Cval=1,
        not(closenodeinfo(Nodelist,_,_,_,_)),!.
    checkInClose(Nodelist,Cval):-
        closenodeinfo(Nodelist,_,_,_,_),
        Cval=0.
    
    findValue(Row,Col,Value):-
        nvalue(Value,Row,Col).
        
    findBlank(Row,Col):-
        nvalue(0,Row,Col).
    
    setNewPos(Value,Row,Col):-
        retract(nvalue(_,Row,Col)),
        assert(nvalue(Value,Row,Col)).
    
    genNodeList(L,NodeList):- 
        rowcolCounter(Cnt), 
        Cnt>=0, 
        NewCnt=Cnt-1, 
        retract(rowcolCounter(Cnt)), 
        assert(rowcolCounter(NewCnt)),
        Row=Cnt div 3, 
        Col=Cnt mod 3, 
        nvalue(Value,Row,Col), 
        NewList=[ ndval(Value,Row,Col) | L ],!,
        genNodeList(NewList,NodeList).
    genNodeList(NodeList,NodeList):-
        rowcolCounter(Cnt),
        retract(rowcolCounter(Cnt)), 
        assert(rowcolCounter(8)),!.
    
    genHvalList(L,Hvallist):-
        retract(opennodeinfo(Nodelist,Hval,Gval,Parent,Nodeno)),
        Newlist=[ndstruct(Nodelist,Hval,Gval,Parent,Nodeno)|L],
        genHvalList(Newlist,Hvallist).
    genHvalList(Hvallist,Hvallist):- !.
    
    insertSortedList([ndstruct(Nodelist,Hval,Gval,Parent,Nodeno)|Tail]):-
        assert(opennodeinfo(Nodelist,Hval,Gval,Parent,Nodeno)),
        insertSortedList(Tail).
    insertSortedList([]) :- !.
    
    performSearch:-
        retract(bestnodeinfo(_,_,_,_,_)),
        opennodeinfo(Nodelist,Hval,Gval,Parent,Nodeno),
        Hval<> 0,
        retract(currParent(_)),
        assert(currParent(Nodeno)),
        assert(bestnodeinfo(Nodelist,Hval,Gval,Parent,Nodeno)),
        emptyCurrNode,
        setCurrNode(Nodelist),
        write("\ncurrent best node\n"),
        displayNodeList(Nodelist),
        write("h(n) : ",Hval),nl,
        write("g(n) : ",Gval),nl,
        write("parent(n) : ",Parent),nl,
        write("nodno(n) : ",Nodeno),
        readchar(_),
        assert(closenodeinfo(Nodelist,Hval,Gval,Parent,Nodeno)),
        retract(opennodeinfo(Nodelist,Hval,Gval,Parent,Nodeno)),
        moveLeft,
        moveUp, 
        moveRight, 
        moveDown,
        performSearch.
    performSearch.

bubblesort(List, Sorted) :- 
     swap(List, List1), !, 
     bubblesort(List1, Sorted). 

bubblesort(Sorted, Sorted). 

swap([ndstruct(A,X,B,C,D),ndstruct(E,Y,F,G,H)|Rest], [ndstruct(E,Y,F,G,H),ndstruct(A,X,B,C,D)|Rest]) :- X > Y.

swap([ndstruct(A,Z,B,C,D)|Rest], [ndstruct(A,Z,B,C,D)|Rest1]) :- swap(Rest, Rest1).

goal
    makewindow(1,2,3,"8-Puzzle Problem",0,0,25,80),
    input,
    opennodeinfo(Nodelist,_,_,_,_),
    calHvalue(Nodelist,Hval),
    nodeNo(Nodeno),
    NewNodeno=Nodeno+1,
    retract(nodeNo(Nodeno)),
    assert(nodeNo(NewNodeno)),
    retract(opennodeinfo(Nodelist,_,_,_,_)),
    assert(opennodeinfo(Nodelist,Hval,0,0,Nodeno)),
    assert(bestnodeinfo(Nodelist,Hval,0,0,Nodeno)),
    setCurrNode(Nodelist),
    emptyCurrNode,
    performSearch.
  
Share: 



Milind Mishra
Milind Mishra author of Prolog program of 8-puzzle using heuristic function % with best first search technique is from India.
 
View All Articles

 
Please enter your Comment

  • Comment should be atleast 30 Characters.
  • Please put code inside [Code] your code [/Code].

 
No Comment Found, Be the First to post comment!