n queens problem

Angol

Főnév

n queens problem (tsz. n queens problems)

(informatika) A N Queens Problem (N királynő problémája) egy klasszikus kombinatorikus keresési probléma, amelyet gyakran használnak algoritmusok, mesterséges intelligencia, constraint programming, és backtracking technikák tanítására és demonstrálására.

🧩 Probléma leírása

Feladat: Helyezz el N darab királynőt egy N×N-es sakktáblán úgy, hogy egyik se üthesse a másikat.

A sakktáblán a királynő bárhova léphet vízszintesen, függőlegesen, vagy átlósan, bármilyen irányban. Tehát a cél olyan elrendezés, hogy:

Ne legyen két királynő ugyanabban a sorban
Ne legyen két királynő ugyanabban az oszlopban
Ne legyen két királynő ugyanazon az átlón

📐 Matematikai modell

Tegyük fel, hogy minden oszlopba csak egy királynőt teszünk → elég csak a sor pozíciót tárolni minden oszlophoz.

Reprezentáció:

Legyen ${\textstyle Q=[q_{1},q_{2},...,q_{n}]}$ , ahol ${\textstyle q_{i}\in \{1,...,n\}}$ a sor indexe az ${\textstyle i}$ . oszlopban.

Korlátozások:

${\textstyle q_{i}\neq q_{j}}$ — különböző sorban legyenek.
${\textstyle |q_{i}-q_{j}|\neq |i-j|}$ — ne legyenek egy átlón.

🧠 Megoldási módszerek

1. Backtracking (visszalépéses keresés)

Rekurzívan helyezünk el királynőket oszloponként, és csak akkor folytatjuk, ha az aktuális részmegoldás nem ellentmondásos.

def is_safe(queen, row, col):
    for c in range(col):
        r = queen[c]
        if r == row or abs(r - row) == abs(c - col):
            return False
    return True

def solve_n_queens(n):
    def backtrack(col):
        if col == n:
            solutions.append(queen[:])
            return
        for row in range(n):
            if is_safe(queen, row, col):
                queen[col] = row
                backtrack(col + 1)
    solutions = []
    queen = [-1] * n
    backtrack(0)
    return solutions

2. Constraint Programming (pl. MiniZinc)

MiniZinc modell:

int: n;

array[1..n] of var 1..n: q;

constraint
  forall(i, j in 1..n where i < j)(
    q[i] != q[j] /\
    abs(q[i] - q[j]) != abs(i - j)
  );

solve satisfy;

output ["\(q)"];

📊 Megoldások száma

Az érvényes elrendezések száma nagyon gyorsan nő:

N	Megoldások száma
1	1
2	0
3	0
4	2
5	10
6	4
7	40
8	92
9	352
10	724
11	2 680
12	14 200+

♟️ Megjelenítés példa (N=4)

Példa egy megoldásra (Q a királynő):

. Q . .
. . . Q
Q . . .
. . Q .

Reprezentációként ez: [2, 4, 1, 3]

💡 Heurisztikák és optimalizálás

Minimum Remaining Value: válaszd azt az oszlopot, amelyikhez a legkevesebb sorlehetőség maradt.
Forward checking: kizárja azokat a lehetőségeket, amelyek biztosan konfliktushoz vezetnének.
Simulated annealing, genetikus algoritmus, Dancing Links (DLX) – nagyobb N-re hatékonyabb.

🧮 Bónusz: Python kirajzolás

def print_solution(solution):
    n = len(solution)
    for i in range(n):
        row = ["Q" if solution[i] == j else "." for j in range(n)]
        print(" ".join(row))
    print()

# Példa használat:
sols = solve_n_queens(4)
for s in sols:
    print_solution(s)

🧾 Összefoglalás

Fogalom	Leírás
Probléma	Helyezz el N királynőt N×N táblára, hogy ne üssék egymást
Modell	Oszloponként egy változó, érték: sor
Korlátozások	különböző sorban, különböző átlón
Megoldások	Rekurzió, backtracking, constraint programming
Használat	AI algoritmusok, constraint solvers, CSP bemutatása

További információk

n queens problem - Szótár.net (en-hu)
n queens problem - Sztaki (en-hu)
n queens problem - Merriam–Webster
n queens problem - Cambridge
n queens problem - WordNet
n queens problem - Яндекс (en-ru)
n queens problem - Google (en-hu)
n queens problem - Wikidata
n queens problem - Wikipédia (angol)