8-queen.py

'''
Implementing arranging of BFS of 8 queen
'''

BOARD_SIZE =3 
goal_state =[1,2,3,4,5,6,7,8," "]
state1 =[1,2,3,4,5,6,7," ",8]
state2= [1,2," ",5,6,3,4,7,8]

def BFS(initial_state):
    #node(cost, node , parent)
    visited_states= set()
    root_node=(0,initial_state,None)
    frontier=[root_node]
    loop_cnt=0
    num_generated_nodes=0
    while frontier!=[]:
        loop_cnt+=1
        node= frontier.pop(0)
        if node[1]== goal_state:
            show_solution(node)
            print()
            print("loop_cnt num_generated_nodes len(visited_states)" )
            print(loop_cnt, num_generated_nodes,len(visited_states))
            return
        successors= expand(node[1])
        for succ in successors:
            if tuple(succ) not in visited_states:
                visited_states.add(tuple(succ))
                new_node= (node[0] +1 , succ,node)
                frontier.append(new_node)
            num_generated_nodes+=1
    


def expand(state):
    successors=[]
    for action in get_possible_actions(state):
        new_state =state[:]
        update_state(new_state,action)
        successors.append(new_state)
    return successors

def show_state(state):
    for i in range(len(state)):
        print(state[i],end=" ")
        if i% 3 == 2:
            print()
    print()

def update_state(state,action):
    blank_index= state.index(" ")
    if action=="Left":
        switch_index= blank_index-1
    elif action== "Right":
        switch_index= blank_index +1
    elif action=="Down":
        switch_index= blank_index +3
    elif action=="Up":
        switch_index= blank_index -3
    state[blank_index],state[switch_index]= state[switch_index],state[blank_index]
    

def get_possible_actions(state):
    actions=[]
    blank_index= state.index(" ")
    r=blank_index //3
    c=blank_index % 3
    if r>0:
        actions.append("Up")
    if r<2:
        actions.append("Down")
    if c>0:
        actions.append("Left")
    if c<2:
        actions.append("Right")
    return actions
    
def show_solution(node):
    path = [node[1]]
    while node[2]:
        node = node[2]
        path.append(node[1])
    path.reverse()
    print("solution is...")
    if len(path)<10:
        for s in path:
            show_state(s)
    print("Finished in  {} steps".format(len(path)-1))
    
BFS(state2)