8 Puzzle in Artificial Intelligence... Python language.....Modify your program so you can easily change board size. Change hard coded size 3 to a variable BOARD_SIZE.Test your 8puzzle for multiple initial states (use random_shuffle to create initial states) with board size = 3 and with board size = 4

goal_board = [1,2,3,4,5,6,7,8," "] board = [7,2,4,5," ",6,8,3,1] board1 = [1,2,3," ",5,6,4,7,8] board2 = [8,4,6,3,1,7,2,5," "]

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

def get_possible_actions(board): # return a list of possible actions # actions are "Left", "Right", "Up", "Down" # eg) ["Left","Up"] actions = [] empty_index = board.index(" ") r = empty_index // 3 c = empty_index % 3 if r < 2: actions.append("Down") if r > 0: actions.append("Up") if c < 2: actions.append("Right") if c > 0: actions.append("Left") return actions

def update_board(board,action): # make change to the board after taking the given action # if action == "Up", then swap empty slot with Up guy. # if action == "Left", then swap empty with Left guy. empty_index = board.index(" ") if action == "Up": switch_index = empty_index - 3 elif action == "Down": switch_index = empty_index + 3 elif action == "Left": switch_index = empty_index - 1 else: # action == "Right" switch_index = empty_index + 1 # swap between the two positions board[empty_index], board[switch_index] = board[switch_index], board[empty_index]

import random def random_shuffle(board, move_cnt): for i in range(move_cnt): update_board(board, random.choice(get_possible_actions(board))) def random_search(board): loop_cnt = 0 while board != goal_board: action = random.choice(get_possible_actions(board)) update_board(board, action) #show_board(board) loop_cnt += 1 show_board(board) print("Done in {} steps".format(loop_cnt))

def BFS(board): # Breadth First Search # node is (cost, board, parent) visited_states = set() root_node = (0,board,None) frontier = [root_node] loop_cnt = 0 num_created_successors = 0 while frontier != []: loop_cnt += 1 node = frontier.pop(0) if node[1] == goal_board: show_solution(node) print(loop_cnt, num_created_successors, len(visited_states)) return # generate next states (successors) successors = expand(node[1]) num_created_successors += len(successors) # for each successors, turn it to a node and add it to frontier for suc in successors: if tuple(suc) not in visited_states: visited_states.add(tuple(suc)) new_node = (node[0]+1,suc,node) frontier.append(new_node)

def DFS(board): # Depth First Search # node is (cost, board, parent) visited_states = set() root_node = (0,board,None) frontier = [root_node] loop_cnt = 0 num_created_successors = 0 while frontier != []: loop_cnt += 1 node = frontier.pop(0) if node[1] == goal_board: show_solution(node) print(loop_cnt, num_created_successors, len(visited_states)) return # generate next states (successors) successors = expand(node[1]) num_created_successors += len(successors) # for each successors, turn it to a node and add it to frontier for suc in successors: if tuple(suc) not in visited_states: visited_states.add(tuple(suc)) new_node = (node[0]+1,suc,node) frontier.insert(0,new_node)

def DFS_limited(board, max_depth): # Similar to DFS but doesn't go deeper beyond max_depth.

# visited_states need to keep cost for each state. # eg) visited_states = {} # set of (k,v) pairs. k is tuple(board), v is cost # if a generated states is in the visited_states, but if it has smaller cost # then still add a node of the board while updating the cost in visited_states. # It is possible to fail to find solution. Return False when it fails, True when succeed. pass

def DFS_iterative_deepening(initial_state): # Call DFS_limited multiple times until it succeed. # Begin with max_depth = 1 and increase it by one # Refer to the pseudo code in page 89 of the textbook. pass def show_solution(node): path = [node[1]] while node[2] != None: node = node[2] path.append(node[1]) path.reverse() print("Solution sequences...") if len(path) < 100: for b in path: show_board(b) print("Solution in {} steps".format(len(path)-1))

def show_solution2(node): # this is solely for AStar path = [node[3]] while node[4] != None: node = node[4] path.append(node[3]) path.reverse() print("Solution sequences...") if len(path) < 100: for b in path: show_board(b) print("Solution in {} steps".format(len(path)-1)) def expand(board): # Given a board, return a list of next states # eg) expand([1,2,3,4,5,6," ",7,8]) returns # [ [1,2,3," ",5,6,4,7,8], [1,2,3,4,5,6,7," ",8] ] successors = [] actions = get_possible_actions(board) for act in actions: new_board = board[:] update_board(new_board,act) successors.append(new_board) return successors

def heuristic(board): # return number of tiles in the wrong place count = 0 for i in range(len(board)): if board[i] != goal_board[i]: count += 1 return count

from heapq import * import time def AStar(board): # A Star search # node is (f=g+h, h, time.perf_counter() ,board, parent) visited_states = {} g = 0 h = heuristic(board) root_node = (g+h,h,time.perf_counter(),board,None) frontier = [root_node] loop_cnt = 0 num_created_successors = 0 while frontier != []: loop_cnt += 1 node = heappop(frontier) if node[3] == goal_board: show_solution2(node) print(loop_cnt, num_created_successors, len(visited_states)) return # generate next states (successors) successors = expand(node[3]) num_created_successors += len(successors) # for each successors, turn it to a node and add it to frontier for suc in successors: h = heuristic(suc) g = node[0] - node[1] + 1 # node[0] is parent's g+h, node[1] is parent's h if tuple(suc) not in visited_states or g+h < visited_states[tuple(suc)]: visited_states[tuple(suc)] = g+h new_node = (g+h,h,time.perf_counter(),suc,node) heappush(frontier, new_node)

##print(heuristic([1,2,3,4,5,6," ",7,8])) ##print(heuristic([8,4,6,3,1,7,2,5," "]))

#show_board(goal_board) #show_board(board) #show_board(goal_board) #print(get_possible_actions(goal_board)) #board1 = goal_board #random_shuffle(board1,100) #show_board(board1)

BFS(board2) #DFS(board1) AStar(board2)

#print(expand(board1)) #random_search(board1) #print(get_possible_actions(board1)) #update_board(board1,"Up") #show_board(board1)