# ====== CSP: Map Coloring (Backtracking + MRV + Forward Checking) ======
# Tujuan: warnai peta (graf) sehingga tetangga tidak punya warna yang sama.

from collections import defaultdict, deque

# 1) Definisikan graf peta (contoh Australia, 7 region)
regions = ["WA","NT","SA","Q","NSW","V","T"]
adj = {
    "WA":["NT","SA"],
    "NT":["WA","SA","Q"],
    "SA":["WA","NT","Q","NSW","V"],
    "Q":["NT","SA","NSW"],
    "NSW":["Q","SA","V"],
    "V":["SA","NSW"],
    "T":[],
}
colors = ["Red","Green","Blue"]

# 2) Domain awal: semua region bisa pakai semua warna
initial_domains = {r:set(colors) for r in regions}

# 3) Heuristik MRV (Minimum Remaining Values)

def select_unassigned_var(assignment, domains):
    candidates = [v for v in regions if v not in assignment]
    # pilih variabel dengan domain tersisa paling kecil (MRV)
    return min(candidates, key=lambda v: len(domains[v]))

# 4) Konsistensi biner: tetangga ≠ warna yang sama

def consistent(var, val, assignment):
    for n in adj[var]:
        if n in assignment and assignment[n] == val:
            return False
    return True

# 5) Forward checking: pangkas domain tetangga

def forward_check(var, val, domains):
    removed = []
    for n in adj[var]:
        if val in domains[n]:
            domains[n] = domains[n].copy()
            domains[n].discard(val)
            removed.append((n,val))
            if not domains[n]:
                return False, removed
    return True, removed

# 6) Backtracking search

def backtrack(assignment, domains):
    if len(assignment) == len(regions):
        return assignment
    var = select_unassigned_var(assignment, domains)
    for val in list(domains[var]):
        if consistent(var, val, assignment):
            assignment[var] = val
            # Simpan snapshot domain
            snapshot = {v:domains[v].copy() for v in regions}
            ok, removed = forward_check(var, val, domains)
            if ok:
                result = backtrack(assignment, domains)
                if result:
                    return result
            # rollback
            assignment.pop(var, None)
            domains = snapshot
    return None

solution = backtrack({}, {v:set(colors) for v in regions})
print("Solusi:", solution)

Coba tambahkan warna ke-4 atau rapatkan constraint (tambah adjacency). Amati dampak pada kecepatan.

# ====== CSP: Sudoku 9x9 (Backtracking + MRV + Forward Checking + AC-3) ======
# Gunakan format string 81 karakter: '0' atau '.' untuk kosong

from collections import defaultdict, deque

rows = "ABCDEFGHI"
cols = "123456789"

def cross(A,B):
    return [a+b for a in A for b in B]

cells = cross(rows, cols)
row_units = [cross(r, cols) for r in rows]
col_units = [cross(rows, c) for c in cols]
box_units = [cross(rs, cs) for rs in ("ABC","DEF","GHI") for cs in ("123","456","789")]
unitlist = row_units + col_units + box_units
units = {s:[u for u in unitlist if s in u] for s in cells}
peers = {s:set(sum(units[s],[]))-set([s]) for s in cells}

# Parser

def parse_grid(grid):
    values = {s:set("123456789") for s in cells}
    for s,ch in zip(cells, grid):
        if ch in "123456789":
            if not assign(values, s, ch):
                return False
    return values

# Assign dan Eliminate

def assign(values, s, d):
    other = values[s]-set(d)
    return all(eliminate(values, s, d2) for d2 in other)

def eliminate(values, s, d):
    if d not in values[s]:
        return values
    values[s].remove(d)
    if len(values[s]) == 0:
        return False
    elif len(values[s]) == 1:
        d2 = next(iter(values[s]))
        for s2 in peers[s]:
            if not eliminate(values, s2, d2):
                return False
    for u in units[s]:
        dplaces = [s for s in u if d in values[s]]
        if len(dplaces) == 0:
            return False
        elif len(dplaces) == 1:
            if not assign(values, dplaces[0], d):
                return False
    return values

# AC-3 (Arc Consistency)

def ac3(values):
    queue = deque([(s,t) for s in cells for t in peers[s]])
    while queue:
        (xi,xj) = queue.popleft()
        if revise(values, xi, xj):
            if len(values[xi])==0:
                return False
            for xk in peers[xi]-{xj}:
                queue.append((xk, xi))
    return values

def revise(values, xi, xj):
    revised = False
    if len(values[xi])>1:
        for d in set(values[xi]):
            if values[xj]=={d}:
                values[xi].remove(d)
                revised = True
    return revised

# MRV + Backtracking

def is_solved(values):
    return all(len(values[s])==1 for s in cells)

def select_unassigned_var(values):
    unsettled = [s for s in cells if len(values[s])>1]
    return min(unsettled, key=lambda s: len(values[s])) if unsettled else None


def search(values):
    if values is False:
        return False
    if is_solved(values):
        return values
    s = select_unassigned_var(values)
    for d in list(values[s]):
        values_copy = {k:set(v) for k,v in values.items()}
        res = assign(values_copy, s, d)
        if res is not False:
            ac3(res)
            attempt = search(res)
            if attempt:
                return attempt
    return False

# Contoh Sudoku (mudah)
grid = "530070000600195000098000060800060003400803001700020006060000280000419005000080079"
values = parse_grid(grid)
ac3(values)
sol = search(values)

# Cetak
if sol:
    print("Solved!")
    for r in rows:
        print(" ".join(next(iter(sol[r+c])) for c in cols))
else:
    print("No solution.")

Ganti grid dengan Sudoku lain (format 81-char). Uji pengaruh AC-3 terhadap jumlah percabangan.

# ====== Kuis 5 (cek mandiri) ======
qs=[
  ("Komponen CSP yang benar adalah...",{"a":"Variabel, domain, constraint","b":"Data, model, loss","c":"Neuron, bobot, aktivasi","d":"State, operator, reward"},"a"),
  ("Forward checking berfungsi untuk...",{"a":"Mencari jalur terpendek","b":"Memotong domain tetangga setelah assignment","c":"Mengurutkan variabel berdasarkan frekuensi","d":"Mengukur akurasi model"},"b"),
  ("AC-3 memastikan...",{"a":"Semua solusi unik","b":"Semua arc konsisten (domain terpangkas sesuai constraint)","c":"Selalu selesai tanpa backtracking","d":"Heuristik minimal"},"b"),
]
print('Kunci jawaban:')
for i,(_,__,ans) in enumerate(qs,1):
    print(f'Q{i}: {ans}')