Contoh Implementasi Teka-Teki dengan BFS dalam Python

 

python code

___________________________________________________________________________________

from collections import deque

# Fungsi untuk memindahkan posisi
def move_blank(puzzle, move):
    new_puzzle = puzzle[:]
    blank_pos = new_puzzle.index(0)
    swap_pos = blank_pos + move
    if swap_pos >= 0 and swap_pos < len(new_puzzle):
        new_puzzle[blank_pos], new_puzzle[swap_pos] = new_puzzle[swap_pos], new_puzzle[blank_pos]
    return new_puzzle

# Fungsi BFS untuk mencari solusi
def bfs(start, goal):
    queue = deque([(start, [])])
    visited = set()

    while queue:
        puzzle, moves = queue.popleft()
        if puzzle == goal:
            return moves

        if tuple(puzzle) in visited:
            continue
        visited.add(tuple(puzzle))

        # Cek semua kemungkinan gerakan
        moves_list = [-1, 1, -3, 3]  # Gerakan: kiri, kanan, atas, bawah
        for move in moves_list:
            new_puzzle = move_blank(puzzle, move)
            queue.append((new_puzzle, moves + [move]))

    return None

# Puzzle mulai dan tujuan
start_puzzle = [1, 2, 3, 4, 5, 6, 7, 8, 0]
goal_puzzle = [1, 2, 3, 4, 5, 6, 7, 8, 0]

# Menemukan solusi
solution = bfs(start_puzzle, goal_puzzle)
print("Solusi ditemukan dengan langkah:", solution)

Penjelasan Algoritma BFS:

• Breadth-First Search (BFS) digunakan untuk menemukan solusi dengan mengunjungi semua keadaan puzzle secara berurutan, dimulai dari keadaan awal, dan memeriksa kemungkinan gerakan secara level per level.
• Algoritma ini mencari solusi dengan jumlah langkah minimum.