eight queens puzzle
Főnév
eight queens puzzle (tsz. eight queens puzzles)
A Eight Queens Puzzle (magyarul: 8 királynő feladvány) a N Queens Problem speciális esete, ahol N = 8, azaz a feladat az, hogy 8 darab királynőt helyezzünk el egy 8×8-as sakktáblán úgy, hogy egyik se üssön a másikat.
🧩 Feladat pontos megfogalmazása
Cél: Olyan elrendezést találni, ahol:
- Egy sorban legfeljebb egy királynő van,
- Egy oszlopban legfeljebb egy királynő van,
- Egy átlón (mindkét irányban) legfeljebb egy királynő van.
📐 Probléma reprezentáció
- A sakktábla 8 sorból és 8 oszlopból áll.
- Minden királynőt egyedi oszlopba helyezünk → elég azt tárolni, melyik sorban van a királynő minden oszlophoz.
Például a következő lista:
[0, 4, 7, 5, 2, 6, 1, 3]
azt jelenti, hogy:
- az első oszlopban a királynő az 1. sorban van (0-indexelve),
- a másodikban az 5. sorban,
- … stb.
🧠 Megoldási módszer – Backtracking
A klasszikus megoldási technika a visszalépéses keresés (backtracking), ahol rekurzívan próbálunk elhelyezni királynőket soronként úgy, hogy az aktuális részmegoldás nem ütközik korábbi királynőkkel.
💻 Python példa
def is_safe(queens, row, col):
for c in range(col):
r = queens[c]
if r == row or abs(r - row) == abs(c - col):
return False
return True
def solve_8_queens():
def backtrack(col):
if col == 8:
solutions.append(queens[:])
return
for row in range(8):
if is_safe(queens, row, col):
queens[col] = row
backtrack(col + 1)
solutions = []
queens = [-1] * 8
backtrack(0)
return solutions
solutions = solve_8_queens()
print(f"Total solutions: {len(solutions)}")
📊 Megoldások száma
- Az összes lehetséges megoldás száma: 92.
- Ha tükörképeket és elforgatásokat nem számolunk külön, akkor 12 alapmegoldás van.
♟️ Kirajzolás (szövegesen)
def print_board(sol):
for row in sol:
line = ['.'] * 8
line[row] = 'Q'
print(" ".join(line))
print()
# Az első megoldás kirajzolása
print_board(solutions[0])
Példa kimenet:
Q . . . . . . . . . . . Q . . . . . . . . . . Q . . . . . Q . . . . Q . . . . . . . . . . . Q . . Q . . . . . . . . . Q . . . .
🧮 További módszerek
- Constraint programming (pl. MiniZinc vagy Google OR-Tools)
- Heurisztikus keresés (pl. Hill Climbing)
- Genetikus algoritmus
- Bitmasking technika (nagyon hatékony programozási trükk nagyobb N-re)
📌 Összefoglalás
| Tulajdonság | Érték |
|---|---|
| Tábla mérete | 8 × 8 |
| Királynők száma | 8 |
| Teljes megoldások | 92 |
| Egyedi (nem szimmetrikus) | 12 |
| Klasszikus megoldás | Backtracking algoritmus |
| Használati terület | Keresési algoritmusok, constraint programming, mesterséges intelligencia oktatása |
- eight queens puzzle - Szótár.net (en-hu)
- eight queens puzzle - Sztaki (en-hu)
- eight queens puzzle - Merriam–Webster
- eight queens puzzle - Cambridge
- eight queens puzzle - WordNet
- eight queens puzzle - Яндекс (en-ru)
- eight queens puzzle - Google (en-hu)
- eight queens puzzle - Wikidata
- eight queens puzzle - Wikipédia (angol)