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: 15627

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

 

Other Interesting Articles in Artificial Intelligence:


 
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!