import random import math import time import psutil import os from collections import deque class Board: def __init__(self,tiles): self.size = int(math.sqrt(len(tiles))) # defining length/width of the board self.tiles = tiles def execute_action(self,action): new_tiles = self.tiles[:] empty_index = new_tiles.index('0') if action=='l': if empty_index%self.size>0: new_tiles[empty_index-1],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index-1] if action=='r': if empty_index%self.size<(self.size-1): new_tiles[empty_index+1],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index+1] if action=='u': if empty_index-self.size>=0: new_tiles[empty_index-self.size],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index-self.size] if action=='d': if empty_index+self.size < self.size*self.size: new_tiles[empty_index+self.size],new_tiles[empty_index] = new_tiles[empty_index],new_tiles[empty_index+self.size] return Board(new_tiles) class Node: def __init__(self,state,parent,action): self.state = state self.parent = parent self.action = action def __repr__(self): return str(self.state.tiles) def __eq__(self,other): return self.state.tiles == other.state.tiles def generate_puzzle(size): numbers = list(range(size*size)) random.shuffle(numbers) return Node(Board(numbers),None,None) def get_children(parent_node): children = [] actions = ['l','r','u','d'] # left,right, up , down ; actions define direction of movement of empty tile for action in actions: child_state = parent_node.state.execute_action(action) child_node = Node(child_state,parent_node,action) children.append(child_node) return children def find_path(node): path = [] while(node.parent is not None): path.append(node.action) node = node.parent path.reverse() return path def run_bfs(root_node): start_time = time.time() frontier = deque([root_node]) explored = [] count=0 while(len(frontier)>0): cur_node = frontier.popleft() count+=1 explored.append(cur_node) if(goal_test(cur_node.state.tiles)): path = find_path(cur_node) end_time = time.time() return path,count,(end_time-start_time) for child in get_children(cur_node): if child in explored: continue else: frontier.append(child) print("frontier empty") return False def main(): process = psutil.Process(os.getpid()) initial_memory = process.memory_info().rss / 1024.0 initial = str(input("initial configuration: ")) initial_list = initial.split(" ") root = Node(Board(initial_list),None,None) print(run_bfs(root)) final_memory = process.memory_info().rss / 1024.0 print(str(final_memory-initial_memory)+" KB") def goal_test(cur_tiles): return cur_tiles == ['1','2','3','4','5','6','7','8','9','10','11','12','13','14','15','0'] if __name__=="__main__": main() This is working code i need the final solution in the format Moves: RDLDDRR Number of Nodes expanded: 361 TIme Taken: 0.238 Memory Used: 704kb
Number of Nodes expanded: 361
TIme Taken: 0.238
Memory Used: 704kb
![Write a program which performs a breadth-first search to find the solution to any given
board position for 15 puzzle
Input
The input should be given in the form of a sequence of numbered tiles for initial board
configuration, '0' indicating the empty space (see example below)
Output
1. Moves
2. Number of Nodes expanded
3. Time Taken
4. Memory Used
Example
> 1024573 896 11 12 13 10 14 15
Moves: RDLDDRR
Number of Nodes expanded: 361
Time Taken: 0.238
Memory Used: 704kb
Hint
You can use hashset to keep track of explored nodes and fast lookup](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F672bf286-8abe-4b07-9ca1-0d5b2612956c%2F5e6662ca-7378-4bac-8312-7e8d9ec3dd20%2Fwxe2bu_processed.png&w=3840&q=75)
![Figure 3.9
function
BREADTH-FIRST-SEARCH(problem)
node + NODE(problem.INITIAL)
if problem.IS-GOAL(node.STATE)
frontiera FIFO queue, with node as an element
reached{problem. INITIAL}
then return node
while not IS-EMPTY(frontier) do
node POP(frontier)
for each child in EXPAND(problem, node) do
s+child.STATE
returns a solution node or failure
if problem.IS-GOAL(s) then return child
if s is not in reached then
add s to reached
add child to frontier
return failure
function UNIFORM-COST-SEARCH(problem) returns a solution node, or failure
return BEST-FIRST-SEARCH(problem, PATH-COST)](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F672bf286-8abe-4b07-9ca1-0d5b2612956c%2F5e6662ca-7378-4bac-8312-7e8d9ec3dd20%2Fhzhu53i_processed.png&w=3840&q=75)
![](/static/compass_v2/shared-icons/check-mark.png)
Algorithm:
The algorithm for the given program can be summarized as follows:
-
Initialization: Initialize the state of the problem by defining a class "Board" which takes a list of tiles as input and calculates the size of the board based on the length of the list.
-
Node Definition: Define a class "Node" which represents the node in the search tree. A node consists of state, parent, and previous action.
-
Generate Puzzle: Create a random puzzle by generating a list of numbers from 0 to (size*size) - 1 and shuffle the list.
-
Get Children: Given a parent node, this function generates its children by simulating the four possible actions (left, right, up, down) on the empty tile.
-
Find Path: Given a node, this function backtracks from the node to the root node to find the solution path.
-
BFS Function: The function "run_bfs" implements the breadth-first search algorithm. It takes the root node as input and returns the solution path, the number of nodes expanded, and the total time taken. The function uses a deque to implement the frontier, a list to keep track of explored nodes, and the "get_children" function to generate children from the parent node.
-
Main Function: The main function takes input from the console, calls the "run_bfs" function to solve the puzzle, and shows the output.
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 4 images
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
![Computer Networking: A Top-Down Approach (7th Edi…](https://www.bartleby.com/isbn_cover_images/9780133594140/9780133594140_smallCoverImage.gif)
![Computer Organization and Design MIPS Edition, Fi…](https://www.bartleby.com/isbn_cover_images/9780124077263/9780124077263_smallCoverImage.gif)
![Network+ Guide to Networks (MindTap Course List)](https://www.bartleby.com/isbn_cover_images/9781337569330/9781337569330_smallCoverImage.gif)
![Computer Networking: A Top-Down Approach (7th Edi…](https://www.bartleby.com/isbn_cover_images/9780133594140/9780133594140_smallCoverImage.gif)
![Computer Organization and Design MIPS Edition, Fi…](https://www.bartleby.com/isbn_cover_images/9780124077263/9780124077263_smallCoverImage.gif)
![Network+ Guide to Networks (MindTap Course List)](https://www.bartleby.com/isbn_cover_images/9781337569330/9781337569330_smallCoverImage.gif)
![Concepts of Database Management](https://www.bartleby.com/isbn_cover_images/9781337093422/9781337093422_smallCoverImage.gif)
![Prelude to Programming](https://www.bartleby.com/isbn_cover_images/9780133750423/9780133750423_smallCoverImage.jpg)
![Sc Business Data Communications and Networking, T…](https://www.bartleby.com/isbn_cover_images/9781119368830/9781119368830_smallCoverImage.gif)