Begreper & referanser

1bruk_mrv = 0  # @param 0..12bruk_fc = 0  # @param 0..13 4n = 14  # variabel = kolonne, verdi = rad5forsok = tilbake = 06 7 8def kolliderer(k1, r1, k2, r2):9    return r1 == r2 or abs(r1 - r2) == abs(k1 - k2)10 11 12def los(tilordning, domener):13    global forsok, tilbake14    if len(tilordning) == n:15        return tilordning16    ledige = [k for k in range(n) if k not in tilordning]17    lovlige = {k: [r for r in domener[k] if not any(kolliderer(k, r, j, s) for j, s in tilordning.items())]18               for k in ledige}19    k = min(ledige, key=lambda j: len(lovlige[j])) if bruk_mrv else ledige[0]20    for r in lovlige[k]:21        forsok += 122        nye = domener23        if bruk_fc:  # fjern verdier hos de ledige som kolliderer med k = r24            nye = {j: [s for s in domener[j] if not kolliderer(k, r, j, s)] for j in ledige if j != k}25            if any(not d for d in nye.values()):26                continue  # et domene ble tomt: forkast verdien27        svar = los({**tilordning, k: r}, nye)28        if svar:29            return svar30    tilbake += 1  # k gikk tom: tilbake til forrige variabel31    return None32 33 34svar = los({}, {k: list(range(1, n + 1)) for k in range(n)})35print(f"Løsning: {', '.join(str(svar[k]) for k in range(n))}" if svar else "Løsning: ingen")36print(f"Tilordninger forsøkt: {forsok}")37print(f"Tilbakesteg: {tilbake}")

Prøv: sett bruk_mrv til 1 og se at linja Tilordninger forsøkt: faller fra 1899 til 124, og sett så bare bruk_fc til 1 og se at Tilbakesteg: faller til under halvparten.

1import random2 3random.seed(4)4n = 8  # @param 4..405maks_steg = 100  # @param 10..10006 7rad = [random.randrange(n) for _ in range(n)]  # tilfeldig start: rad[k] i kolonne k8 9 10def konflikter(k, r):11    return sum(1 for j in range(n) if j != k and (rad[j] == r or abs(rad[j] - r) == abs(j - k)))12 13 14lost_etter = None15for steg in range(maks_steg + 1):16    i_konflikt = [k for k in range(n) if konflikter(k, rad[k]) > 0]17    if not i_konflikt:18        lost_etter = steg19        break20    if steg == maks_steg:21        break22    k = random.choice(i_konflikt)  # tilfeldig variabel i konflikt23    tall = [konflikter(k, r) for r in range(n)]24    rad[k] = random.choice([r for r in range(n) if tall[r] == min(tall)])  # likhet: tilfeldig25 26par = sum(1 for a in range(n) for b in range(a + 1, n) if rad[a] == rad[b] or abs(rad[a] - rad[b]) == b - a)27print(f"Løst etter steg: {lost_etter}" if lost_etter is not None else f"Løst etter steg: ikke løst innen {maks_steg} steg")28print(f"Konflikter igjen: {par}")

Prøv: øk n til 40 og se at linja Løst etter steg: fortsatt havner under 100, og senk maks_steg til 10 og se at Konflikter igjen: blir større enn 0.

1tilbakespor(tilordning, domener):2    hvis alle variabler har en verdi:3        returner tilordning4    x = velg_variabel(tilordning, domener)        # fast, MRV, MRV + grad5    for v i ordne_verdier(x, tilordning, domener): # fast eller LCV6        hvis v passer med alle tilordnede naboer:7            legg til x = v8            nye = utled(x, v, domener)              # ingenting, FC eller MAC9            hvis ingen domener i nye er tomme:10                svar = tilbakespor(tilordning, nye)11                hvis svar ikke er feil:12                    returner svar13            fjern x = v                             # prøv neste verdi14    returner feil                                   # tilbake til forrige valg

Tre valg styrer søket: hvilken variabel som tas, i hvilken rekkefølge verdiene prøves, og hvor mye som utledes etter hver tilordning. Strukturen er etter Russell & Norvig, slik den ligger i aimacode/aima-pseudocode (CC BY 4.0), oversatt og med egne navn.