Python :: Aufgabe #111
1 Lösung
Schach I: Königsmarsch
Fortgeschrittener - Python
von hollst
- 26.06.2016 um 13:44 Uhr
Wir betrachten eine Schachstellung mit einem weißen König auf a1 (linke untere Ecke) und einem schwarzen König auf c3. Weiter sind keine Figuren auf dem Brett. Die Stellung ist natürlich remis und völlig uninteresant für einen Schachspieler. Wir wollen die Stellung allerdings auch nicht weiterspielen, sondern uns die Frage stellen, wieviele unterschiedliche Wege gibt es für den weißen König, um zur rechten oberen Ecke zu gelangen (h8). Der schwarze König dient dabei nur als Hindernis und bleibt bei dem weißen Königsmarsch auf c3 stehen.
Folgende zwei Randbedingungen: 1) die weißen Königszüge seien Regelkonform, d. h. (z. B.) zwischen weißem und schwarzem König muss stets ein Feld frei sei, u. z. sowohl in diagonaler, horizontaler und vertikaler Richtung. 2) auf seinem Weg zur oberen rechten Ecke darf der weiße König kein Feld betreten, das er bereits einmal betreten hatte (dies würde zu zirkularen Wegen führen mit möglicherweise unendlich vielen Schritten, das sei verboten).
Versuche bitte nicht sofort mit dem 8 x 8 Schachbrett zu beginnen, sondern mit einem kleineren mit 5 x 5 Feldern. Eine mögliche Lösung für diesen Fall ist im Bild dargestellt. Gehe dann zu einem Schachbrett mit 6 x 6 Felder über und erst zum Schluss, wenn du genügend Rechenzeit zur Verfügung hast, zu dem 8 x 8 Felder Brett.
Folgende zwei Randbedingungen: 1) die weißen Königszüge seien Regelkonform, d. h. (z. B.) zwischen weißem und schwarzem König muss stets ein Feld frei sei, u. z. sowohl in diagonaler, horizontaler und vertikaler Richtung. 2) auf seinem Weg zur oberen rechten Ecke darf der weiße König kein Feld betreten, das er bereits einmal betreten hatte (dies würde zu zirkularen Wegen führen mit möglicherweise unendlich vielen Schritten, das sei verboten).
Versuche bitte nicht sofort mit dem 8 x 8 Schachbrett zu beginnen, sondern mit einem kleineren mit 5 x 5 Feldern. Eine mögliche Lösung für diesen Fall ist im Bild dargestellt. Gehe dann zu einem Schachbrett mit 6 x 6 Felder über und erst zum Schluss, wenn du genügend Rechenzeit zur Verfügung hast, zu dem 8 x 8 Felder Brett.
Lösungen:
Python-Code
# VERY SLOW: Only works fast for 5x5
# len(kingsmarch())
# this is 6x6 and slow
# len(kingsmarch(target=[5,5], max_x=6, max_y = 6))
def around(pos,max_x = 5, max_y = 5) :
ret = []
for i in range(-1,2):
for j in range(-1,2):
if i!=0 or j!= 0 :
if pos[0] + i < max_x and pos[1] + j < max_y and pos[0] + i > -1 and pos[1] + j > -1 :
ret.append([pos[0]+i, pos[1] +j])
return ret
def search(target, pos, path, blocked_fields, solutions, max_x, max_y) :
for move in around(pos, max_x, max_y):
if move in blocked_fields or move in path:
continue
new_path = list(path)
new_path.append(move)
if move == target :
solutions.append(new_path)
break
else :
search(target, move, new_path, blocked_fields, solutions, max_x, max_y)
return solutions
# white king, black king, target loc, x,y
def kingsmarch(wk = [0,0], bk = [2,2], target= [4,4], max_x = 5, max_y = 5) :
blocked_fields = around(bk)
pos = wk
path = [wk]
return search(target, pos, path, blocked_fields, [], max_x, max_y)