Write program in Python.  Write a breadth-first search program to solve 15-puzzle problems in the same way as the 8-puzzle. Keep track of the number of nodes expanded and print that out along with the steps to solve the problem. Define the legal moves as "swap the blank with an adjacent tile," resulting in the blank's moving up, down, left, or right. Note that the ending state needs to be entered by the user, and not generated after the input of the starting states, basically same inputs and outs puts as below. A sample run should look like this:  Enter 15-puzzle starting state by rows (0 for blank):  1,2,3,4,5,6,7,8,9,10,0,11,13,14,15,12  Enter ending state by rows (0 for blank):  1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0 Solution: Start 1 2 3 4 5 6 7 8 9 10 0 11 13 14 15 12 Swap the blank Right 1 2 3 4 5 6 7 8 9 10 11 0 13 14 15 12 Down 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 

"Finished!"

A little more details for the input and output:

The input would be ask same as above, numbers between 1-15, 0(for blank) in any order, but then another promt asking user to give a end goal as to where they want the 0(for blank) to end up at:

Example Input (two promts asking user to enter random rows from 1-15 with a 0(for blank), then entering desired goal, for this example we want the 0 to be at the end of matrix with our matrix being sorted in order 1-15.):

 Enter 15-puzzle starting state by rows (0 for blank):  1,2,3,4,5,6,7,8,9,10,0,11,13,14,15,12 

So here we enter our 15 number 1-15 in mix order with 0(for blank between 10 and 11) Now we ask the user for end solution they want the matrix to look like:

Enter ending state by rows (0 for blank):  1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0 

Here we enter the desired goal we want and then the matrix will generate our solution to be as inputed above, basically trying to get the 0 to end as best as possible.

Basically the end goal would be to move the 0 to the end of matrix, while the matrix it self is sorted in increasing order 1-15. So if we enter a 0 between 1, 2, 3, 4, 5, 6, 7, 8, 0, 10, 9, 11, 12, 14, 13, 15. Then program would move things around to get 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0. This program needs to be done in Breath First Search.