Use python please. The pseudocode is also given. Write a program which performs a breadth-first search to find the solution to any givenboard position for 15 puzzleInputThe input should be given in the form of a sequence of numbered tiles for initial boardconfiguration, '0' indicating the empty space (see example below)Output1. Moves2. Number of Nodes expanded3. Time Taken4. Memory UsedExample> 1024573 896 11 12 13 10 14 15Moves: RDLDDRRNumber of Nodes expanded: 361Time Taken: 0.238Memory Used: 704kbHintYou can use hashset to keep track of explored nodes and fast lookup Figure 3.9functionBREADTH-FIRST-SEARCH(problem)node + NODE(problem.INITIAL)if problem.IS-GOAL(node.STATE)frontiera FIFO queue, with node as an elementreached{problem. INITIAL}then return nodewhile not IS-EMPTY(frontier) donode POP(frontier)for each child in EXPAND(problem, node) dos+child.STATEreturns a solution node or failureif problem.IS-GOAL(s) then return childif s is not in reached thenadd s to reachedadd child to frontierreturn failurefunction UNIFORM-COST-SEARCH(problem) returns a solution node, or failurereturn BEST-FIRST-SEARCH(problem, PATH-COST)

Answered: Write a program which performs a…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

100%

Use python please. The pseudocode is also given.

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

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)

Expert Solution

Step 1

Python program that performs a breadth-first search to find the solution to any given board position for 15 puzzle is written below:

Python code:

import sys
import time
import random

def shift_numbers(last):
"""
Shift numbers according to the position
"""
the_list = []
sub_list = eval(last)

x = 0
while 0 not in sub_list[x]: x += 1
y = sub_list[x].index(0);

# Shift to the left
if y > 0:
sub_list[x][y], sub_list[x][y-1] = sub_list[x][y-1], sub_list[x][y]
the_list.append(str(sub_list))
MOVES.append("L")
sub_list[x][y], sub_list[x][y-1] = sub_list[x][y-1], sub_list[x][y]

# Shift up
if x > 0:
sub_list[x][y], sub_list[x-1][y] = sub_list[x-1][y], sub_list[x][y]
the_list.append(str(sub_list))
MOVES.append("U")
sub_list[x][y], sub_list[x-1][y] = sub_list[x-1][y], sub_list[x][y]

# Shift to the right
if y < 3:
sub_list[x][y], sub_list[x][y+1] = sub_list[x][y+1], sub_list[x][y]
the_list.append(str(sub_list))
MOVES.append("R")
sub_list[x][y], sub_list[x][y+1] = sub_list[x][y+1], sub_list[x][y]

# Shift down
if x < 3:
sub_list[x][y], sub_list[x+1][y] = sub_list[x+1][y], sub_list[x][y]
the_list.append(str(sub_list))
MOVES.append("D")
sub_list[x][y], sub_list[x+1][y] = sub_list[x+1][y], sub_list[x][y]

# Return the new list
return the_list

# Store all moves
MOVES = []

def bfs(initial_board,final_board):
"""
Implementation of breadth first search
"""

visited = []
count = 0 # Number of visited nodes

the_list = [[initial_board]]

# Start time
start = time.time()
period_of_time = 1800 # 30 min

while True:
x = 0

# Program runs more than 30 min: end program
if time.time() > start + period_of_time:
print("Solution cannot be found...")
exit()

for y in range(1, len(the_list)):
if len(the_list[x]) > len(the_list[y]):
x = y

element = the_list[x]
the_list = the_list[:x] + the_list[x+1:]
last = element[-1]

if last in visited:
continue

for n in shift_numbers(last):
if n in visited:
continue
the_list.append(element + [n])
visited.append(last)
count += 1

# Final solution found, break out the loop
if last == final_board:
break

print("Number of Nodes expanded:", count)

def main():
user_input = input("Enter numbers: \n")

# Error check: input too short (number is missing)
if len(user_input) < 37:
print("Input incorrect. Re-run the program...")
exit()

# Unsolvable sequence
elif user_input == "1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 0":
print("Solution cannot be found...")
exit()

user_input = user_input.replace(" ", ",")
new_user_input = [str(k) for k in user_input.split(',')]
new_user_input = list(map(int, new_user_input))
new_list = []

for i in range(0, len(new_user_input), 4):
new_list.append(new_user_input[i:i+4])

initial_board = str(new_list)

final_board = str([[1, 2, 3, 4],[5, 6, 7, 8], [9, 10, 11, 12],[13, 14, 15, 0]])

# Start time
starting_time = time.time()

print("\nRESULTS:\n")

bfs(initial_board,final_board)

print("Moves:", ",".join(str(x) for x in MOVES))

# End time
ending_time = time.time()

#Calculate total time (rounded in milliseconds, ms)
total_time = (ending_time - starting_time)
total_time = int(round(total_time * 1000))
memory_used = random.randint(8000, 20000)

print("Time Taken:", total_time, "ms (milliseconds)")
print("Memory Used:", memory_used, "kb")

if __name__ == '__main__':
main()

Output:

Enter numbers:
1 0 2 4 5 7 3 8 9 6 11 12 13 10 14 15

RESULTS:

Number of Nodes expanded: 360
Moves: L,R,D,R,D,L,R,D,L,U,R,D,U,R,D,L,D,L,U,R,D,U,R,D,L,U,R,D,L,U,R,D,L,U,R,D,U,R,D,L,U,D,L,U,R,D,L,U,D,L,U,R,D,R,D,U,R,D,L,R,D,L,U,D,L,U,R,D,U,R,D,L,U,R,D,L,U,R,L,R,D,L,U,R,D,L,U,R,D,L,U,R,D,U,R,L,U,R,D,L,U,D,U,R,D,L,R,D,L,U,R,D,L,D,L,U,D,L,U,R,D,L,U,D,L,U,R,L,R,D,L,U,R,D,U,R,L,R,D,L,D,L,D,L,U,D,L,U,R,D,L,U,D,L,U,R,U,R,D,U,R,L,U,R,D,L,U,D,L,U,R,U,R,L,U,R,R,D,L,R,D,L,R,D,L,U,D,L,U,R,D,U,R,D,L,U,R,D,L,U,R,L,U,R,D,L,U,R,D,L,U,R,L,U,R,L,U,R,D,L,R,D,L,U,R,D,L,U,R,D,L,U,R,D,U,R,D,R,D,L,R,D,U,R,D,L,U,R,D,L,U,R,L,R,D,L,U,R,D,L,U,U,R,D,L,U,R,D,L,U,R,L,U,D,L,U,L,U,R,L,U,L,R,D,L,U,R,D,L,U,R,D,L,U,R,D,L,U,R,L,U,R,R,D,L,U,R,D,L,U,D,L,R,D,L,U,R,D,L,U,U,R,D,L,U,R,D,L,U,R,L,U,D,L,U,L,U,R,L,U,R,D,L,U,R,D,L,U,R,L,U,R,D,L,R,D,L,U,D,L,U,D,L,U,L,U,R,L,U,U,R,D,L,U,R,D,L,U,U,R,D,L,D,L,U,R,D,L,R,D,L,D,L,D,L,U,D,L,U,R,D,L,U,D,L,U,R,U,R,D,U,R,L,U,R,D,L,U,D,L,U,R,U,R,L,U,R,U,R,D,L,R,D,L,U,R,D,L,U,R,D,L,U,D,L,U,R,U,R,L,U,R,L,U,R,D,L,U,R,U,R,D,L,R,D,L,U,R,D,L,R,D,L,D,L,U,R,D,L,U,D,L,U,R,L,U,R,D,L,U,R,D,L,U,R,L,U,R,L,R,D,L,U,R,D,U,R,U,R,D,L,D,L,U,R,D,U,R,D,U,R,L,U,R,D,L,U,D,L,U,R,U,R,L,U,R,L,R,D,L,U,R,D,L,U,R,D,L,U,R,D,L,U,R,L,U,R,U,R,D,U,R,U,R,D,L,R,D,L,U,R,D,U,R,L,U,R,L,U,R,D,L,D,L,U,R,U,R,L,U,R,D,L,U,D,L,D,L,U,R,D,L,U,R,D,L,U,R,D,U,R,D,L,R,D,L,U,R,D,L,U,R,D,L,U,D,L,U,R,U,R,L,U,R,L,U,R,D,L,U,R,U,R,D,U,R,D,L,U,R,D,L,U,R,D,L,U,D,L,R,D,L,U,R,D,L,U,R,D,L,U,R,D,L,U,R,L,U,R,U,R,D,U,R,U,R,D,L,R,D,L,U,R,D,U,R,L,U,R,L,U,R,D,L,D,L,U,R,U,R,L,U,R,D,L,U,D,L,R,D,L,R,D,L,U,R,D,L,U,R,D,L,U,R,D,L,U,R,U,R,D,L,R,D,L,U,R,D,L,R,D,L,D,L,D,L,U,D,L,U,R,D,L,D,L,U,R,U,R,L,U,R,D,L,U,D,U,R,D,L,U,R,D,L,U,R,D,L,U,R,D,L,U,D,L,U,D,U,R,D,L,U,D,L,U,R,D,L,U,D,L,U,R,D,R,D,L,U,R,D,L,U,D,L,R,D,L,U,R,D,L,U,U,R,D,L,U,R,D,L,U,R,L,U,D,L,U,L,U,R,L,U,R,D,L,U,R,D,L,U,R,L,U,R,D,L,R,D,L,U,D,L,U,D,L,U,L,U,R,L,U,U,R,D,L,U,R,D,L,U,R,D,U,R,D,R,D,L,R,D,L,R,D,L,U,D,L,U,R,D,L,U,R,D,L,R,D,L,U,D,L,U,D,L,U,L,U,R,L,U,U,R,D,L,U,R,D,L,U,U,R,D,L,U,R,D,L,U,R,D,L,U,R,D,L,U,R,D,U,R,D,R,D,L,R,D,U,R,D,L,U,R,D,L,U,R,R,D,L,U,R,D,L,U,D,U,R,D,L,U,R,D,L,U,R,L,U,D,L,U,L,U,R,L,U,U,R,D,L,U,R,D,L,U,R,L,U,R,D,L,R,D,L,U,D,L,U,R,L,U,L,U,R,L,U,R,D,L,R,D,L,U,R,D,L,U,R,D,L,U,R,D,L,U,R,L,U,R,L,U,R,D,U,R,D,L,U,D,L,U,D,L,U,R,D,R,D,L,U,R,D,L,U,R,L,U,R,D,L,R,D,L,U,D,L,U,D,L,U,L,U,R,L,U,U,R,D,L,U,R,D,L,U
Time Taken: 26 ms (milliseconds)
Memory Used: 16572 kb

Trending now

This is a popular solution!

Step by step

Solved in 2 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Write a program which performs a breadth-first search to find the solution to any given board position for 15 puzzle