Question

Python Question:

Johnny has some difficulty memorizing the small prime numbers. So, his computer science teacher has asked him to play with the following puzzle game frequently. The puzzle is a 3x3 board consisting of numbers from 1 to 9. The objective of the puzzle is to swap the tiles until the following final state is reached:

1 2 3

4 5 6

7 8 9

At each step, Johnny may swap two adjacent tiles if their sum is a prime number. Two tiles are considered adjacent if they have a common edge. Help Johnny to figure out whether the given 3-by-3 board can reach the goal state or not. Define a function `solve_puzzle` that takes an 3-by-3 numpy array (i.e., an ndarray) as its only argument and returns Python Boolean that is True if and only if the given 3-by-3 board can reach the goal state. Hint: You can start from the goal state, walk through all the possible states and save them into a global variable. You function just need to judge if the given state is inside the possible states or not.

Answer 1

Ans:

# Source Code:

import numpy as np

swaps = [(0,1),(1,2),(3,4),(4,5),(6,7),(7,8),(0,3),(1,4),(2,5),(3,6),(4,7),(5,8)]
primes = (2,3,5,7,11,13,17)
goal_states = set()

def swap(x,s):
X_copy = list(x)
X_copy[s[0]],X_copy[s[1]] = X_copy[s[1]],X_copy[s[0]]
return tuple(X_copy)

def solve_puzzle(matrix):
matrix.resize(9,)
matrix = tuple(matrix)
if(len(goal_states)==0):
init_goal_states()
if(matrix in goal_states):
return True
return False
  

  
def init_goal_states():
board = (1,2,3,4,5,6,7,8,9)
goal_states.add(board)
bfs = [board]
for board in bfs:
for a,b in swaps:
if board[a]+board[b] in primes:
newboard = swap(board, (a,b))
if newboard not in goal_states:
goal_states.add(newboard)
bfs.append(newboard)

  
mat = np.array([[2, 1, 3],[4, 6, 5],[7, 9, 8]])
if(solve_puzzle(mat)):
print("yes")
else:
print("no")

// Screenshot: refer to the screenshot for indentation

// Here is the screenshot with comments for better understanding of the code

// If you have any query do ask in the comments section.

// If you found the answer helpful do give a Thumbs Up!!