Программа собирающая пятнашки (3x3)

@Sirkor · Регистрация: 15.12.2014

Студворк — интернет-сервис помощи студентам

Вот собственно код

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import pprint
pp = pprint.PrettyPrinter(indent=4)
 
def puzz_astar(start, end):
    """
    A* algorithm
    """
    front = [[heuristic_2(start), start]]
    print(front)
    expanded = []
 
    expanded_nodes = 0
 
    while front:
        i = 0
        for j in range(1, len(front)):
            if front[i][0] > front[j][0]:
                i = j
        path = front[i]
        front = front[:i] + front[i + 1:]
        endnode = path[-1]
        if endnode == end:
            break
        if endnode in expanded: continue
        for k in moves(endnode):
            if k in expanded: continue
            newpath = [path[0] + abs(heuristic_2(k) - heuristic_2(endnode))] + path[1:] + [k]
            front.append(newpath)
            expanded.append(endnode)
        expanded_nodes += 1
 
    print ("Expanded nodes:", expanded_nodes)
    print ("Solution:")
    pp.pprint(path)
 
 
def moves(mat):
    """
    Returns a list of all possible moves
    """
    output = []
    m = eval(mat)
    i = 0
    while 0 not in m[i]: i += 1
    j = m[i].index(0)  #blank space (zero)
 
    if i > 0:
        m[i][j], m[i - 1][j] = m[i - 1][j], m[i][j]  #move up
        output.append(str(m))
        m[i][j], m[i - 1][j] = m[i - 1][j], m[i][j]
 
    if i < 2:
        m[i][j], m[i + 1][j] = m[i + 1][j], m[i][j]  #move down
        output.append(str(m))
        m[i][j], m[i + 1][j] = m[i + 1][j], m[i][j]
 
    if j > 0:
        m[i][j], m[i][j - 1] = m[i][j - 1], m[i][j]  #move left
        output.append(str(m))
        m[i][j], m[i][j - 1] = m[i][j - 1], m[i][j]
 
    if j < 2:
        m[i][j], m[i][j + 1] = m[i][j + 1], m[i][j]  #move right
        output.append(str(m))
        m[i][j], m[i][j + 1] = m[i][j + 1], m[i][j]
 
    return output
 
 
def heuristic_2(puzz):
    """
    Manhattan distance
    """
    distance = 0
    m = eval(puzz)
    for i in range(4):
        for j in range(4):
            if m[i][j] == 0: distance += 2-i + 2-j 
            distance += abs((i - m[i][j] / 3)) + abs((j - m[i][j] % 3))
    return distance
 
def manhattan_distance(puzz, end):
    """
    Manhettan distance heuristic
    """
    m = eval(puzz)
    a = eval(end)
    lst = []
    result = 0
 
    for x in range(3):
        for y in range(3):
            if a[x][y] == 0:
                continue
            lst.append([[x, y], a[x][y]])
 
    for i in range(3):
        for j in range(3):
            if m[i][j] == 0:
                continue
            for s in lst:
                if s[1] == m[i][j]:
                    x = s[0][0]
                    y = s[0][1]
 
            result += abs(i - x) + abs(j - y)
    return result
 
if __name__ == '__main__':
 
    puzzle = str([[1,2,7],[3,4,6],[0,8,5]])
    end = str([[1,2,3],[4,5,6],[7,8,0]])
 
    puzz_astar(puzzle, end)

И вот что он выдаёт
Traceback (most recent call last):
File "C:\Python34\пятнашки(2).py", line 114, in <module>
puzz_astar(puzzle, end)
File "C:\Python34\пятнашки(2).py", line 8, in puzz_astar
front = [[heuristic_2(start), start]]
File "C:\Python34\пятнашки(2).py", line 78, in heuristic_2
if m[i][j] == 0: distance += 2-i + 2-j
IndexError: list index out of range
Не могу разобраться в чём ошибка

Jabbson · 06.11.2015, 21:20

в том, что range(4) дает вам 0 1 2 3 - четыре элемента, а в листе который вы перебираете - 3.

Python
1
2
for i in range(4):
    for j in range(4):

@Sirkor · 06.11.2015, 21:39 **[ТС]**

Спасибо, проглядел, заработало, но неверно

Добавлено через 13 минут
Всё исправлено, работающая версия выглядит так, тему можно закрывать

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import pprint
pp = pprint.PrettyPrinter(indent=4)
 
def puzz_astar(start, end):
    """
    A* algorithm
    """
    front = [[heuristic_2(start), start]]
    print(front)
    expanded = []
 
    expanded_nodes = 0
 
    while front:
        i = 0
        for j in range(1, len(front)):
            if front[i][0] > front[j][0]:
                i = j
        path = front[i]
        front = front[:i] + front[i + 1:]
        endnode = path[-1]
        if endnode == end:
            break
        if endnode in expanded: continue
        for k in moves(endnode):
            if k in expanded: continue
            newpath = [path[0] + abs(heuristic_2(k) - heuristic_2(endnode))] + path[1:] + [k]
            front.append(newpath)
            expanded.append(endnode)
        expanded_nodes += 1
 
    print ("Количество действий:", expanded_nodes)
    print ("Решение:")
    pp.pprint(path)
 
 
def moves(mat):
    """
    Returns a list of all possible moves
    """
    output = []
    m = eval(mat)
    i = 0
    while 0 not in m[i]: i += 1
    j = m[i].index(0)  #blank space (zero)
 
    if i > 0:
        m[i][j], m[i - 1][j] = m[i - 1][j], m[i][j]  #move up
        output.append(str(m))
        m[i][j], m[i - 1][j] = m[i - 1][j], m[i][j]
 
    if i < 2:
        m[i][j], m[i + 1][j] = m[i + 1][j], m[i][j]  #move down
        output.append(str(m))
        m[i][j], m[i + 1][j] = m[i + 1][j], m[i][j]
 
    if j > 0:
        m[i][j], m[i][j - 1] = m[i][j - 1], m[i][j]  #move left
        output.append(str(m))
        m[i][j], m[i][j - 1] = m[i][j - 1], m[i][j]
 
    if j < 2:
        m[i][j], m[i][j + 1] = m[i][j + 1], m[i][j]  #move right
        output.append(str(m))
        m[i][j], m[i][j + 1] = m[i][j + 1], m[i][j]
 
    return output
 
 
def heuristic_2(puzz):
    """
    Manhattan distance
    """
    distance = 0
    m = eval(puzz)
    for i in range(3):
        for j in range(3):
            if m[i][j] == 0: distance += 2-i + 2-j 
            distance += abs((i - m[i][j] / 3)) + abs((j - m[i][j] % 3))
    return distance
 
def manhattan_distance(puzz, end):
    """
    Manhettan distance heuristic
    """
    m = eval(puzz)
    a = eval(end)
    lst = []
    result = 0
 
    for x in range(3):
        for y in range(3):
            if a[x][y] == 0:
                continue
            lst.append([[x, y], a[x][y]])
 
    for i in range(3):
        for j in range(3):
            if m[i][j] == 0:
                continue
            for s in lst:
                if s[1] == m[i][j]:
                    x = s[0][0]
                    y = s[0][1]
 
            result += abs(i - x) + abs(j - y)
    return result
 
if __name__ == '__main__':
 
    puzzle = str([[1,2,3],[4,5,6],[0,7,8]])
    end = str([[1,2,3],[4,5,6],[7,8,0]])
 
    puzz_astar(puzzle, end)

@rnboy · 14.12.2022, 12:16

Доброго дня. Решал похожую задачу в целях обучения, попутно разбираясь с А* и эвристиками, использовал некоторые моменты из этого решения, опустив спорные вещи типа eval.
Не могу понять пару вещей, исключительно чтобы разобраться до конца.
Для чего мы в сумму эвристик добавляем разность новой точки и последней(текущей)?В своем коде просто просуммировал путь до точки и эвристику новой точки и это работает, возможно есть какойто скрытый смысл который я не понял, но все проверки работа прошла?Речь об этом

Python
1
newpath = [path[0] + abs(heuristic_2(k) - heuristic_2(endnode))]...

В моем решении заменил на это:

Python
1
newnow = [now[0] +  heuristic_2(k)]...

и это работает, но возможно есть случаи которые я не расмотрел?
И второй вопрос, хотя ответ я думаю знаю, зачем две функции для подсчета эвристик(манх. расстояния) если используется только одна? Я так подозреваю что это черновой неиспользуемый код, но опять же если чего-то не понял, поправьте пожалуйста.

Новые блоги и статьи Все статьи Все блоги /
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .
Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .