fork download
copy 
  1. from collections import defaultdict, deque
  2. import heapq
  3.  
  4. # Class representing the board configuration
  5. class ChessBoard:
  6.     def __init__(self):
  7.         self.piece_positions = {}
  8.  
  9.     def get_piece_at(self, row, col):
  10.         for piece, position in self.piece_positions.items():
  11.             if position == (row, col):
  12.                 return piece
  13.         return ' '
  14.  
  15.     def display(self):
  16.         print("-" * 33)
  17.         for i in range(8):
  18.             row_display = '| '
  19.             for j in range(8):
  20.                 row_display += self.get_piece_at(i, j) + ' | '
  21.             print(row_display)
  22.             print("-" * 33)
  23.  
  24.     def duplicate(self):
  25.         new_board = ChessBoard()
  26.         new_board.piece_positions = self.piece_positions.copy()
  27.         return new_board
  28.  
  29. def count_connected_pieces(board):
  30.     connected_count = 0
  31.     visited = [[False]*8 for _ in range(8)]
  32.     queue = deque()
  33.     queue.append(board.piece_positions['J'])
  34.  
  35.     while queue:
  36.         row, col = queue.popleft()
  37.         if visited[row][col]:
  38.             continue
  39.         visited[row][col] = True
  40.         piece = board.get_piece_at(row, col)
  41.         if piece == ' ':
  42.             continue
  43.         connected_count += 1
  44.         for d_row, d_col in zip(knight_row_moves, knight_col_moves):
  45.             new_row, new_col = row + d_row, col + d_col
  46.             if 0 <= new_row < 8 and 0 <= new_col < 8 and not visited[new_row][new_col]:
  47.                 queue.append((new_row, new_col))
  48.     return connected_count
  49.  
  50. def bfs_search(board):
  51.     print("Algorithm: Breadth-First Search:")
  52.     queue = deque([(board, [])])
  53.     visited = set()
  54.     visited.add(tuple(board.piece_positions.items()))
  55.     expanded_states = 0
  56.  
  57.     while queue:
  58.         current_board, moves = queue.popleft()
  59.         expanded_states += 1
  60.         if count_connected_pieces(current_board) == 6:
  61.             print("One of the goal states:")
  62.             current_board.display()
  63.             print("Solution:")
  64.             for move in moves:
  65.                 print(move)
  66.             print("Number of expanded states:", expanded_states)
  67.             return
  68.  
  69.         for piece, (row, col) in current_board.piece_positions.items():
  70.             for direction_index, (d_row, d_col) in enumerate(zip(move_row_changes, move_col_changes)):
  71.                 new_row, new_col = row + d_row, col + d_col
  72.                 if 0 <= new_row < 8 and 0 <= new_col < 8:
  73.                     new_board = current_board.duplicate()
  74.                     new_board.piece_positions[piece] = (new_row, new_col)
  75.                     new_moves = moves + [f"Move {piece} {directions[direction_index]}"]
  76.                     if tuple(new_board.piece_positions.items()) not in visited:
  77.                         visited.add(tuple(new_board.piece_positions.items()))
  78.                         queue.append((new_board, new_moves))
  79.  
  80. def a_star_search(board):
  81.     print("Algorithm: A* Search:")
  82.     priority_queue = []
  83.     count = 0
  84.     expanded_states = 0
  85.     heapq.heappush(priority_queue, (5, count, board, []))
  86.     visited = set()
  87.     visited.add(tuple(board.piece_positions.items()))
  88.  
  89.     while priority_queue:
  90.         estimated_cost, _, current_board, moves = heapq.heappop(priority_queue)
  91.         expanded_states += 1
  92.         if estimated_cost == 0:
  93.             print("One of the goal states:")
  94.             current_board.display()
  95.             print("Solution:")
  96.             for move in moves:
  97.                 print(move)
  98.             print("Number of expanded states:", expanded_states)
  99.             return
  100.  
  101.         for piece, (row, col) in current_board.piece_positions.items():
  102.             for direction_index, (d_row, d_col) in enumerate(zip(move_row_changes, move_col_changes)):
  103.                 new_row, new_col = row + d_row, col + d_col
  104.                 if 0 <= new_row < 8 and 0 <= new_col < 8:
  105.                     count += 1
  106.                     new_board = current_board.duplicate()
  107.                     new_board.piece_positions[piece] = (new_row, new_col)
  108.                     new_moves = moves + [f"Move {piece} {directions[direction_index]}"]
  109.                     if tuple(new_board.piece_positions.items()) not in visited:
  110.                         visited.add(tuple(new_board.piece_positions.items()))
  111.                         h_n = 6 - count_connected_pieces(current_board)
  112.                         heapq.heappush(priority_queue, (h_n, count, new_board, new_moves))
  113.  
  114. # Moves configuration
  115. knight_row_moves = [1, 2, -1, -2, -1, 2, 1, -2]
  116. knight_col_moves = [2, 1, 2, 1, -2, -1, -2, -1]
  117. move_row_changes = [1, -1, 0, 0]
  118. move_col_changes = [0, 0, 1, -1]
  119. directions = ["Down", "Up", "Right", "Left"]
  120.  
  121. # Initialize and run
  122. initial_board = ChessBoard()
  123. initial_board.piece_positions['J'] = (1, 1)
  124. initial_board.piece_positions['A'] = (2, 2)
  125. initial_board.piece_positions['F'] = (4, 1)
  126. initial_board.piece_positions['R'] = (2, 4)
  127. initial_board.piece_positions['O'] = (5, 4)
  128. initial_board.piece_positions['M'] = (6, 7)
  129.  
  130. print("Student name: Jafar Omar\n" +
  131.                 "The six first unique  letters are: J A F R O M\n");
  132. bfs_search(initial_board)
  133. a_star_search(initial_board)
  134.  
Success #stdin #stdout 0.14s 16312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Student name: Jafar Omar
The six first unique  letters are: J A F R O M

Algorithm: Breadth-First Search:
One of the goal states:
---------------------------------
|   | J |   |   |   |   |   |   | 
---------------------------------
|   |   |   |   |   |   |   |   | 
---------------------------------
|   |   | A |   |   |   |   |   | 
---------------------------------
|   |   |   |   | R |   |   |   | 
---------------------------------
|   | F |   |   |   |   |   |   | 
---------------------------------
|   |   |   |   |   | O |   |   | 
---------------------------------
|   |   |   |   |   |   |   | M | 
---------------------------------
|   |   |   |   |   |   |   |   | 
---------------------------------
Solution:
Move J Up
Move R Down
Move O Right
Number of expanded states: 689
Algorithm: A* Search:
One of the goal states:
---------------------------------
|   | J |   |   |   |   |   |   | 
---------------------------------
|   |   |   |   |   |   |   |   | 
---------------------------------
|   |   | A |   |   |   |   |   | 
---------------------------------
|   |   |   |   |   |   |   |   | 
---------------------------------
|   | F |   | R |   |   |   |   | 
---------------------------------
|   |   |   |   | O |   |   |   | 
---------------------------------
|   |   |   |   |   |   | M |   | 
---------------------------------
|   |   |   |   |   |   |   |   | 
---------------------------------
Solution:
Move J Up
Move R Down
Move R Left
Move M Left
Move R Down
Number of expanded states: 37
https://ideone.com/obOdx6
language:
Python 3 (python  3.9.5)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!