Belajar Menyelesaikan 8 Teka-teki di Python

Membangun pemecah 8 teka-teki 

8-puzzle adalah varian dari 15-puzzle. Bisa di cek di https://en.wikipedia.org/wiki/15_puzzle. Teka-teki tersebut disajikan secara acak grid dan tujuan Anda adalah mengembalikannya ke konfigurasi asli yang dipesan. Anda bisa memainkan untuk membiasakan diri dengannya di http://mypuzzle.org/sliding.

Disini akan menggunakan algoritma A * untuk menyelesaikan masalah ini. Ini adalah algoritma yang digunakan untuk mencari jalur ke solusi dalam grafik. Algoritma ini merupakan gabungan dari algoritma Dijkstra dan pencarian terbaik pertama. Alih-alih menebak secara membabi buta ke mana harus pergi selanjutnya, A * algoritma memilih salah satu yang terlihat paling menjanjikan. Di setiap node, kami membuat daftar semua kemungkinan dan kemudian pilih satu dengan biaya minimal yang dibutuhkan untuk mencapai tujuan. 

Mari kita lihat bagaimana mendefinisikan fungsi biaya. Pada setiap node, kita perlu menghitung biayanya. Ini cost pada dasarnya adalah jumlah dari dua biaya - biaya pertama adalah biaya untuk sampai ke node saat ini dan biaya kedua adalah biaya untuk mencapai tujuan dari node saat ini.

Kami menggunakan penjumlahan ini sebagai heuristik kami. Seperti yang bisa kita lihat, biaya kedua pada dasarnya adalah memperkirakan itu tidak sempurna. Jika ini sempurna, maka algoritma A * akan menemukan solusinya segera. Tapi biasanya tidak demikian. Butuh beberapa waktu untuk menemukan jalan terbaik menuju solusi.

Tetapi A * sangat efektif dalam menemukan jalur yang optimal dan merupakan salah satu yang paling populer teknik di luar sana.

Mari gunakan algoritma A * untuk membangun pemecah 8 teka-teki. Ini adalah varian dari solusi yang diberikan di perpustakaan simpleai. 

1. Buat file Python baru dan ketik kode berikut:

from simpleai.search import astar, SearchProblem

# Class containing methods to solve the puzzle

class PuzzleSolver(SearchProblem):

# Action method to get the list of the possible

# numbers that can be moved in to the empty space

def actions(self, cur_state):

rows = string_to_list(cur_state)

row_empty, col_empty = get_location(rows, 'e')

actions = []

if row_empty > 0:

actions.append(rows[row_empty - 1][col_empty])

if row_empty < 2:

actions.append(rows[row_empty + 1][col_empty])

if col_empty > 0:

actions.append(rows[row_empty][col_empty - 1])

if col_empty < 2:

actions.append(rows[row_empty][col_empty + 1])

return actions

# Return the resulting state after moving a piece to the empty space

def result(self, state, action):

rows = string_to_list(state)

row_empty, col_empty = get_location(rows, 'e')

row_new, col_new = get_location(rows, action)

rows[row_empty][col_empty], rows[row_new][col_new] = \

rows[row_new][col_new], rows[row_empty][col_empty]

return list_to_string(rows)

# Returns true if a state is the goal state

def is_goal(self, state):

return state == GOAL

# Returns an estimate of the distance from a state to

# the goal using the manhattan distance

def heuristic(self, state):

rows = string_to_list(state)

distance = 0

for number in '12345678e':

row_new, col_new = get_location(rows, number)

row_new_goal, col_new_goal = goal_positions[number]

distance += abs(row_new - row_new_goal) + abs(col_new - col_new_goal)

return distance

# Convert list to string

def list_to_string(input_list):

return '\n'.join(['-'.join(x) for x in input_list])

# Convert string to list

def string_to_list(input_string):

return [x.split('-') for x in input_string.split('\n')]

# Find the 2D location of the input element

def get_location(rows, input_element):

for i, row in enumerate(rows):

for j, item in enumerate(row):

if item == input_element:

return i, j

# Final result that we want to achieve

GOAL = '''1-2-3

4-5-6

7-8-e'''

# Starting point

INITIAL = '''1-e-2

6-3-4

7-5-8'''

# Create a cache for the goal position of each piece

goal_positions = {}

rows_goal = string_to_list(GOAL)

for number in '12345678e':

goal_positions[number] = get_location(rows_goal, number)

# Create the solver object

result = astar(PuzzleSolver(INITIAL))

# Print the results

for i, (action, state) in enumerate(result.path()):

print()

if action == None:

print('Initial configuration')

elif i == len(result.path()) - 1:

print('After moving', action, 'into the empty space. Goal achieved!')

else:

print('After moving', action, 'into the empty space')

print(state

 2. Hasil output akan nampak pada terminal;

 

 

Referensi:

• Prateek Joshi. 2017. Artificial Intelligence with Python-Build real-world Artificial Intelligence applications with Python to intelligently interact with the world around you. Birmingham, Mumbai.