Naprogramujte algoritmus dynamického programovania

• riešenie puzzle.
• logistický problém - školský rozvrh.

Naprogramujte jednoduchý šachový (dámový) automat

Naprogramujte piškôrky

Praktické cvičenie: Generátor všetkých riešení N-kráľovien

Zadanie

Implementujte funkciu:

def solve_n_queens(n):
    pass

Funkcia má nájsť všetky riešenia problému N-kráľovien pomocou backtrackingu.

Riešenie reprezentujte ako zoznam dĺžky n, kde:

solution[col] = row

napríklad:

[1, 3, 0, 2]

znamená:

• v stĺpci 0 je kráľovná v riadku 1
• v stĺpci 1 je kráľovná v riadku 3
• atď.

Funkcia vráti zoznam všetkých riešení:

[
    [1, 3, 0, 2],
    [2, 0, 3, 1]
]

---

Požiadavky

Implementujte pomocné funkcie:

def is_safe(board, row, col):
    pass

a

def solve_n_queens(n):
    pass

Použite:

• rekurziu
• backtracking
• kontrolu stĺpcov a diagonál

---

Príklady

Príklad 1

solve_n_queens(1)

Výsledok:

[[0]]

---

Príklad 2

solve_n_queens(4)

Výsledok:

[
    [1, 3, 0, 2],
    [2, 0, 3, 1]
]

Poradie riešení nie je dôležité.

---

Automatické hodnotenie

Testovať sa môže:

Počet riešení

assert len(solve_n_queens(1)) == 1
assert len(solve_n_queens(4)) == 2
assert len(solve_n_queens(5)) == 10
assert len(solve_n_queens(6)) == 4

Validita riešení

Pre každé riešenie:

for solution in solve_n_queens(n):
    assert len(solution) == n

    for c1 in range(n):
        for c2 in range(c1 + 1, n):
            assert solution[c1] != solution[c2]
            assert abs(solution[c1] - solution[c2]) != abs(c1 - c2)

---

Bonus (+2 body)

Implementujte funkciu:

def count_n_queens(n):
    pass

ktorá vráti iba počet riešení bez ich ukladania do zoznamu.

Príklad:

count_n_queens(8)
# 92

---

Prečo je toto zadanie vhodné

• Priamo nadväzuje na prednášku (8 kráľovien).

• Študenti musia pochopiť:

  • čiastkové riešenie,
  • kontrolu obmedzení,
  • rekurziu,
  • backtracking.
• Dá sa automaticky hodnotiť bez kontroly výstupu na obrazovku.
• Existujú jednoznačné testy pre správnosť aj efektivitu.
• Bonus prirodzene vedie k diskusii o pamäťovej a časovej zložitosti.

Previous Post Next Post