Hallo liebe Community,
in Rahmen meines Informatik Labors, soll ich ein Programm schreiben, welches das Spiel Khun Pan lösen kann.
Es gibt mehrere Möglichkeiten um an die Lösung zu kommen, jedoch erscheint mir die Breitensuche als die Beste von denen.
Es ist eine interessante Aufgabenstellung, doch leider habe ich kaum mit Python gearbeitet.
Ich bin offen für Umsetzungsvorschläge und wäre dankbar für Hilfe beim Lösen dieses Problems.
Mit freundlichen Grüßen
Simon.
Spiele
-
- User
- Beiträge: 491
- Registriert: Mittwoch 13. November 2019, 08:38
Wie sieht dein Code aus? Was ist die konkrete Frage? Wo kommst du nicht weiter?
Als Einstieg bietet sich das offizielle Python-Tutorial an.
Als Einstieg bietet sich das offizielle Python-Tutorial an.
-
- User
- Beiträge: 6
- Registriert: Dienstag 17. November 2020, 19:04
Dieses Programm dient als Orientierung.
Dort sind gleich zwei Algorithmen untergebracht, einmal die Breitensuche und einmal A*, wobei A* nochmal zwei weitere Möglichkeiten aufweist.
Manhatten distance und counts the numbers of misplaced tiles.
http://www.khunpan.de/ ...hier ist der Link zum eigentlichen Spiel.
Ich habe es erst mit A* und der Manhatten distance versucht, jedoch brauchte ich viele Regeln wie ich die Steine bewegen darf und es war nicht der optimale Lösungsweg.
Es gibt darüber hinaus gleiche Steine, die keine feste Position haben und das erschwert das Ganze.
Ich habe mir ein Konzept zur Breitensuche überlegt, habe aber die Befürchtung, dass der Rechenaufwand unverhältnismäßig hoch wird, da es bei Khun Pan deutlich mehr Möglichkeiten gibt als im Beispiel.
Dort sind gleich zwei Algorithmen untergebracht, einmal die Breitensuche und einmal A*, wobei A* nochmal zwei weitere Möglichkeiten aufweist.
Manhatten distance und counts the numbers of misplaced tiles.
http://www.khunpan.de/ ...hier ist der Link zum eigentlichen Spiel.
Ich habe es erst mit A* und der Manhatten distance versucht, jedoch brauchte ich viele Regeln wie ich die Steine bewegen darf und es war nicht der optimale Lösungsweg.
Es gibt darüber hinaus gleiche Steine, die keine feste Position haben und das erschwert das Ganze.
Ich habe mir ein Konzept zur Breitensuche überlegt, habe aber die Befürchtung, dass der Rechenaufwand unverhältnismäßig hoch wird, da es bei Khun Pan deutlich mehr Möglichkeiten gibt als im Beispiel.
Code: Alles auswählen
## Quelle
## https://github.com/MilanPecov/15-Puzzle-Solvers
import pprint
pp = pprint.PrettyPrinter(indent=4)
def puzz_breadth_first(start,end):
"""
Breadth First algorithm
"""
front = [[puzzle]]
expanded = []
expanded_nodes=0
while front:
i = 0
for j in range(1, len(front)): #minimum
if len(front[i]) > len(front[j]):
i = j
path = front[i]
front = front[:i] + front[i+1:]
endnode = path[-1]
if endnode in expanded: continue
for k in moves(endnode):
if k in expanded: continue
front.append(path + [k])
expanded.append(endnode)
expanded_nodes += 1
if endnode == end: break
print ("Expanded nodes:", expanded_nodes)
print ("Solution:")
pp.pprint(path)
def puzz_astar(start,end):
"""
A* algorithm
"""
front = [[heuristic_2(start), start]] #optional: heuristic_1
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] + 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 < 3:
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 < 3:
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_1(puzz): #bracuht 2600 Schritt, sehr lange
"""
Counts the number of misplaced tiles
"""
misplaced = 0
compare = 0
m = eval(puzz)
for i in range(4):
for j in range(4):
if m[i][j] != compare:
misplaced += 1
compare += 1
return misplaced
def heuristic_2(puzz): #schneller als heuristic_1
"""
Manhattan distance
"""
distance = 0
m = eval(puzz)
for i in range(4):
for j in range(4):
if m[i][j] == 0: continue
distance += abs(i - (m[i][j]/4)) + abs(j - (m[i][j]%4));
return distance
if __name__ == '__main__':
puzzle = str([[1, 2, 6, 3],[4, 9, 5, 7], [8, 13, 11, 15],[12, 14, 0, 10]])
end = str([[0, 1, 2, 3],[4, 5, 6, 7], [8, 9, 10, 11],[12, 13, 14, 15]])
#puzz_astar(puzzle,end)
puzz_breadth_first(puzzle,end)
- __blackjack__
- User
- Beiträge: 13112
- Registriert: Samstag 2. Juni 2018, 10:21
- Wohnort: 127.0.0.1
- Kontaktdaten:
Breitensuche ist bei ≈100 Schritten bei der Lösung machbar, denke ich.
„All religions are the same: religion is basically guilt, with different holidays.” — Cathy Ladman