Skip to content

Instantly share code, notes, and snippets.

@rusty-snake

rusty-snake/chess_8_queens.py

Last active July 2, 2019 09:44
Show Gist options
  • Save rusty-snake/57e38f1f5e85148d4d826f13771e0345 to your computer and use it in GitHub Desktop.
Save rusty-snake/57e38f1f5e85148d4d826f13771e0345 to your computer and use it in GitHub Desktop.
Download ZIP
python script to solve the Eight queens puzzle
Raw
chess_8_queens.py
#!/usr/bin/env python3
# MIT License
#
# Copyright (c) 2018 rusty-snake (https://github.com/rusty-snake) <print_hello_world+License@protonmail.com>
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in all
# copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.
from sys import argv
import getopt
schachbrett_out = """\
+--+--+--+--+--+--+--+--+
H|H1|H2|H3|H4|H5|H6|H7|H8|
+--+--+--+--+--+--+--+--+
G|G1|G2|G3|G4|G5|G6|G7|G8|
+--+--+--+--+--+--+--+--+
F|F1|F2|F3|F4|F5|F6|F7|F8|
+--+--+--+--+--+--+--+--+
E|E1|E2|E3|E4|E5|E6|E7|E8|
+--+--+--+--+--+--+--+--+
D|D1|D2|D3|D4|D5|D6|D7|D8|
+--+--+--+--+--+--+--+--+
C|C1|C2|C3|C4|C5|C6|C7|C8|
+--+--+--+--+--+--+--+--+
B|B1|B2|B3|B4|B5|B6|B7|B8|
+--+--+--+--+--+--+--+--+
A|A1|A2|A3|A4|A5|A6|A7|A8|
+--+--+--+--+--+--+--+--+
"""
# 0 frei
# 1 dame
# 2 blockiert
# 3 dame nach rechts
schach_feld = {
"A": [
[1, 0, 0],
[2, 0, 0],
[3, 0, 0],
[4, 0, 0],
[5, 0, 0],
[6, 0, 0],
[7, 0, 0],
[8, 0, 0]
],
"B": [
[1, 0, 0],
[2, 0, 0],
[3, 0, 0],
[4, 0, 0],
[5, 0, 0],
[6, 0, 0],
[7, 0, 0],
[8, 0, 0]
],
"C": [
[1, 0, 0],
[2, 0, 0],
[3, 0, 0],
[4, 0, 0],
[5, 0, 0],
[6, 0, 0],
[7, 0, 0],
[8, 0, 0]
],
"D": [
[1, 0, 0],
[2, 0, 0],
[3, 0, 0],
[4, 0, 0],
[5, 0, 0],
[6, 0, 0],
[7, 0, 0],
[8, 0, 0]
],
"E": [
[1, 0, 0],
[2, 0, 0],
[3, 0, 0],
[4, 0, 0],
[5, 0, 0],
[6, 0, 0],
[7, 0, 0],
[8, 0, 0]
],
"F": [
[1, 0, 0],
[2, 0, 0],
[3, 0, 0],
[4, 0, 0],
[5, 0, 0],
[6, 0, 0],
[7, 0, 0],
[8, 0, 0]
],
"G": [
[1, 0, 0],
[2, 0, 0],
[3, 0, 0],
[4, 0, 0],
[5, 0, 0],
[6, 0, 0],
[7, 0, 0],
[8, 0, 0]
],
"H": [
[1, 0, 0],
[2, 0, 0],
[3, 0, 0],
[4, 0, 0],
[5, 0, 0],
[6, 0, 0],
[7, 0, 0],
[8, 0, 0]
]
}
class Main:
def __init__(self):
# unused
self.correct_schachbretts = []
self.temp_schach_out = None
def make_pos(self):
pass
def schachbrett_write(self):
pass
def schachbrett_read(self):
pass
def find_next_free_feld(self, reihe):
spalte = 0
for schachbrett_spalte in schach_feld[reihe]:
if schachbrett_spalte[1] == 0:
spalte = schachbrett_spalte[0]
break
return spalte
def reihen_abstand(self, reihe1, reihe2):
buchstabe_zu_zahl = {
"A": 1,
"B": 2,
"C": 3,
"D": 4,
"E": 5,
"F": 6,
"G": 7,
"H": 8
}
zahl1 = buchstabe_zu_zahl[reihe1]
zahl2 = buchstabe_zu_zahl[reihe2]
if zahl1 > zahl2:
return zahl1 - zahl2
elif zahl1 < zahl2:
return zahl2 - zahl1
def update_block_status_reihe(self, reihe):
for feld in schach_feld[reihe]:
if feld[1] in (1, 3):
continue
else:
if feld[2] == 0:
schach_feld[reihe][feld[0] - 1][1] = 0
else:
schach_feld[reihe][feld[0] - 1][1] = 2
def update_all(self):
self.update_block_status_reihe("A")
self.update_block_status_reihe("B")
self.update_block_status_reihe("C")
self.update_block_status_reihe("D")
self.update_block_status_reihe("E")
self.update_block_status_reihe("F")
self.update_block_status_reihe("G")
self.update_block_status_reihe("H")
def add_dame(self, pos):
reihe = pos[0]
spalte = int(pos[1])
for feld in schach_feld[reihe]:
if feld[0] == spalte:
schach_feld[reihe][feld[0] - 1][1] = 1
else:
schach_feld[reihe][feld[0] - 1][2] += 1
for schachbrett_reihe in schach_feld:
abstand = self.reihen_abstand(reihe, schachbrett_reihe)
if schachbrett_reihe == reihe:
continue
for feld in schach_feld[schachbrett_reihe]:
if feld[0] == spalte:
schach_feld[schachbrett_reihe][feld[0] - 1][2] += 1
elif feld[0] == spalte - abstand or feld[0] == spalte + abstand:
schach_feld[schachbrett_reihe][feld[0] - 1][2] += 1
self.update_all()
def rm_dame(self, pos):
reihe = pos[0]
spalte = int(pos[1])
for feld in schach_feld[reihe]:
if feld[0] == spalte:
schach_feld[reihe][feld[0] - 1][1] = 0
else:
schach_feld[reihe][feld[0] - 1][2] -= 1
for schachbrett_reihe in schach_feld:
abstand = self.reihen_abstand(reihe, schachbrett_reihe)
if schachbrett_reihe == reihe:
continue
for feld in schach_feld[schachbrett_reihe]:
if feld[0] == spalte:
schach_feld[schachbrett_reihe][feld[0] - 1][2] -= 1
elif feld[0] == spalte - abstand or feld[0] == spalte + abstand:
schach_feld[schachbrett_reihe][feld[0] - 1][2] -= 1
self.update_all()
def find_dame(self, reihe):
spalte = 0
for feld in schach_feld[reihe]:
if feld[1] == 1:
spalte = feld[0]
break
return spalte
def reset_temp_schach_out(self):
self.temp_schach_out = None
def set_temp_schach_out(self):
self.temp_schach_out = schachbrett_out
def set_feld_schachbrett_out(self, pos,
dame=False, dame_rechts=False, blocked=False,
block_number=" "):
if dame is True:
self.temp_schach_out = self.temp_schach_out.replace(pos, "()")
elif dame_rechts is True:
if not numbers:
block_number = ">"
self.temp_schach_out = self.temp_schach_out.replace(
pos, ">" + block_number)
elif blocked is True:
if not numbers:
block_number = " "
self.temp_schach_out = self.temp_schach_out.replace(
pos, block_number)
else:
self.temp_schach_out = self.temp_schach_out.replace(pos, " ")
def print_no_correct_schachbrett(self):
pass
def clear_reihe(self, reihe):
self.print_no_correct_schachbrett()
for feld in schach_feld[reihe]:
schach_feld[reihe][feld[0] - 1][1] = 0
self.update_block_status_reihe(reihe)
def dame_nach_rechts(self, reihe):
now_spalte = self.find_dame(reihe)
if not now_spalte == 0:
self.rm_dame(reihe + str(now_spalte))
schach_feld[reihe][now_spalte - 1][1] = 3
spalte = self.find_next_free_feld(reihe)
if spalte == 0:
self.clear_reihe(reihe)
return False
else:
self.add_dame(reihe + str(spalte))
return True
def print_schachbrett(self):
self.set_temp_schach_out()
for reihe in schach_feld:
for feld in schach_feld[reihe]:
if feld[1] == 1:
self.set_feld_schachbrett_out(
reihe + str(feld[0]), dame=True)
else:
self.set_feld_schachbrett_out(reihe + str(feld[0]))
print(schachfeld_prefix + self.temp_schach_out)
self.reset_temp_schach_out()
def save_schachbrett(self):
self.correct_schachbretts.append(schach_feld.copy())
def exec_h(self):
erfolg = self.dame_nach_rechts("H")
if erfolg is True:
self.save_schachbrett()
self.print_schachbrett()
now_spalte = self.find_dame("H")
if not now_spalte == 0:
self.rm_dame("H" + str(now_spalte))
self.clear_reihe("H")
return "G"
else:
return "G"
def exec_g(self):
erfolg = self.dame_nach_rechts("G")
if erfolg is True:
return "H"
else:
return "F"
def exec_f(self):
erfolg = self.dame_nach_rechts("F")
if erfolg is True:
return "G"
else:
return "E"
def exec_e(self):
erfolg = self.dame_nach_rechts("E")
if erfolg is True:
return "F"
else:
return "D"
def exec_d(self):
erfolg = self.dame_nach_rechts("D")
if erfolg is True:
return "E"
else:
return "C"
def exec_c(self):
erfolg = self.dame_nach_rechts("C")
if erfolg is True:
return "D"
else:
return "B"
def exec_b(self):
erfolg = self.dame_nach_rechts("B")
if erfolg is True:
return "C"
else:
return "A"
def exec_a(self):
erfolg = self.dame_nach_rechts("A")
if erfolg is True:
return "B"
else:
return True
def main_loop(self):
next_exec = "A"
while True:
if next_exec == "A":
next_exec = self.exec_a()
elif next_exec == "B":
next_exec = self.exec_b()
elif next_exec == "C":
next_exec = self.exec_c()
elif next_exec == "D":
next_exec = self.exec_d()
elif next_exec == "E":
next_exec = self.exec_e()
elif next_exec == "F":
next_exec = self.exec_f()
elif next_exec == "G":
next_exec = self.exec_g()
elif next_exec == "H":
next_exec = self.exec_h()
elif next_exec is True:
break
def execute(self):
self.main_loop()
class MainDebug(Main):
def print_no_correct_schachbrett(self):
self.set_temp_schach_out()
for reihe in schach_feld:
for feld in schach_feld[reihe]:
if feld[1] == 1:
self.set_feld_schachbrett_out(
reihe + str(feld[0]), dame=True)
elif feld[1] == 3:
self.set_feld_schachbrett_out(
reihe + str(feld[0]), dame_rechts=True,
block_number=str(feld[2]))
elif feld[1] == 2:
self.set_feld_schachbrett_out(
reihe + str(feld[0]), blocked=True,
block_number=" " + str(feld[2]))
else:
self.set_feld_schachbrett_out(reihe + str(feld[0]))
print(self.temp_schach_out)
self.reset_temp_schach_out()
args, no_getopt_args = getopt.getopt(argv[1:], "anb", [])
debug = False
numbers = False
schachfeld_prefix = ""
for opt, value in args:
if opt in ("-a"):
debug = True
elif opt in ("-n"):
numbers = True
elif opt in ("-b"):
schachfeld_prefix = "\nNEXT\n\n"
if debug:
mache_ergebnis = MainDebug()
else:
mache_ergebnis = Main()
mache_ergebnis.execute()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment