Sudoku (și predecesorii săi) a fost jucat de peste o sută de ani. Când a ieșit pentru prima dată, oamenii au trebuit să rezolve puzzle-urile folosindu-și doar mintea. Acum avem calculatoare! (Bine, deci majoritatea oamenilor încă își folosesc mintea …)

În acest articol, veți învăța cum să jucați și să câștigați Sudoku. Dar, mai important, veți învăța cum să folosiți învățarea automată pentru a rezolva cu ușurință fiecare puzzle Sudoku. Cine are nevoie să se gândească când poți lăsa computerul să gândească pentru tine. ?

Peter Norvig a dezvoltat un program elegant folosind Python pentru a câștiga sudoku folosind propagarea și căutarea constrângerilor. Soluția Norvig este considerată un clasic și este adesea menționată atunci când oamenii își dezvoltă propriul cod pentru a juca Sudoku. După ce am analizat Sudoku și câteva strategii, voi defalca codul Norvig pas cu pas, astfel încât să puteți înțelege cum funcționează.

Ce este Sudoku?

Sudoku este un puzzle de plasare a numărului și există câteva tipuri diferite. Acest articol este despre cel mai popular tip.

Obiectivul este de a umple o grilă 9×9 cu cifre (1-9) astfel încât fiecare coloană, rând și fiecare dintre cele nouă subgrile 3×3 (numite și casete) să conțină fiecare cifră de la 1 la 9. Puzzle-urile încep cu unele numere deja în grilă și depinde de dvs. să completați celelalte numere.

În imaginea de mai jos dintr-un joc Sudoku, numărul care ar trebui să meargă în pătratul evidențiat albastru nu poate fi în niciunul dintre pătratele galbene corespunzătoare coloanei, rândului și casetei 3×3.

Cum sa joci si sa castigi Sudoku Folosirea matematicii

Cum se rezolvă Sudoku

Când rezolvați un puzzle Sudoku, ar trebui să faceți în mod constant două lucruri. Primul lucru pe care trebuie să-l faceți este să eliminați numerele din rânduri, coloane și casete (subgrile 3×3). Al doilea lucru pe care ar trebui să-l faci este să cauți un singur candidat.

În exemplul de mai jos, numerele posibile pentru fiecare pătrat sunt notate cu un font mai mic. Numerele posibile au fost determinate prin eliminarea tuturor cifrelor care apar în aceeași coloană, rând sau casetă. Majoritatea oamenilor vor stabili numărul posibil pentru o singură cutie, în loc de grila completă.

1612105991 461 Cum sa joci si sa castigi Sudoku Folosirea matematicii

După ce eliminați numerele, puteți căuta candidați singuri. Aceasta înseamnă să găsiți un pătrat care poate fi doar un număr posibil. În exemplul de mai jos, cele două pătrate evidențiate galben trebuie să conțină 1 și 8 deoarece toate celelalte cifre au fost eliminate deoarece apar deja în coloana, rândul sau caseta pătratului.

1612105991 824 Cum sa joci si sa castigi Sudoku Folosirea matematicii

Acum, când sunt cunoscute cele două pătrate evidențiate în galben, acest lucru elimină mai multe posibilități din alte pătrate. Acum știți că pătratul evidențiat în albastru trebuie să fie 7.

1612105991 37 Cum sa joci si sa castigi Sudoku Folosirea matematicii

Dacă continuați să găsiți candidații singuri și apoi să eliminați opțiunile din alte pătrate, puteți ajunge în cele din urmă la punctul în care nu mai există candidați singuri.

1612105991 539 Cum sa joci si sa castigi Sudoku Folosirea matematicii

În acest moment puteți căuta soluții posibile la pătrate în care numărul este doar într-un singur pătrat dintr-o cutie, rând sau coloană. În exemplul de mai jos putem determina că soluția la pătratul evidențiat în albastru trebuie să fie 6, deoarece numărul 6 nu apare în niciun alt pătrat din caseta galbenă.

1612105991 3 Cum sa joci si sa castigi Sudoku Folosirea matematicii

Uneori, placa va ajunge la o stare în care se pare că fiecare pătrat nerezolvat ar putea avea valori multiple. Asta înseamnă că există mai multe căi pe care le-ai putea alege și nu este evident care cale va duce la rezolvarea puzzle-ului.

În acel moment este necesar să încercați fiecare opțiune. Alegeți una și continuați să rezolvați până când devine clar că opțiunea pe care ați ales-o nu poate fi o soluție. Apoi va trebui să faceți o retrogradare și să încercați o altă opțiune.

Acest tip de căutare poate fi realizat cu ușurință cu un computer folosind un arbore de căutare binar. Când există opțiunea a două numere diferite pentru a rezolva un pătrat, este necesar să se împartă în două posibilități diferite. Un arbore de căutare binară va permite unui algoritm să coboare pe o ramură de opțiuni, apoi să încerce o altă ramură de opțiuni.

1612105991 141 Cum sa joci si sa castigi Sudoku Folosirea matematicii
Reprezentarea arborelui de căutare binară

Acum vom vedea codul Python care poate rezolva puzzle-uri Sudoku folosind o metodă similară cu ceea ce tocmai a fost descris.

Programul lui Peter Norvig pentru a câștiga Sudoku

Peter Norvig a explicat abordarea sa de a rezolva Sudoku și codul pe care l-a folosit în articolul său Rezolvarea fiecărui puzzle Sudoku.

Unii ar putea găsi explicația lui puțin greu de urmat, în special începătorii. Voi descompune lucrurile, astfel încât să fie mai ușor de înțeles cum funcționează codul Norvig.

În acest articol, codul Python 2 al Norvig a fost actualizat la Python 3. (conversia Python 3 de către Naoki Shibuya.) Voi examina codul câteva rânduri la rând, dar puteți vedea codul complet la sfârșitul acestui articol. Pentru unii oameni, poate fi util să se uite peste codul complet înainte de a citi mai departe.

În primul rând, vom acoperi configurarea de bază și notația. Iată cum Norvig descrie notația de bază pe care o folosește în codul său:

Un puzzle Sudoku este un grilă de 81 de pătrate; majoritatea entuziaștilor etichetează coloanele 1-9, rândurile AI și numesc o colecție de nouă pătrate (coloană, rând sau casetă) unitate iar pătratele care împart o unitate colegi.

Iată numele pătratelor:

 A1 A2 A3| A4 A5 A6| A7 A8 A9
 B1 B2 B3| B4 B5 B6| B7 B8 B9
 C1 C2 C3| C4 C5 C6| C7 C8 C9
---------+---------+---------
 D1 D2 D3| D4 D5 D6| D7 D8 D9
 E1 E2 E3| E4 E5 E6| E7 E8 E9
 F1 F2 F3| F4 F5 F6| F7 F8 F9
---------+---------+---------
 G1 G2 G3| G4 G5 G6| G7 G8 G9
 H1 H2 H3| H4 H5 H6| H7 H8 H9
 I1 I2 I3| I4 I5 I6| I7 I8 I9

Norvig definește cifrele, rândurile și coloanele ca șiruri:

digits="123456789"
rows="ABCDEFGHI"
cols     = digits

Veți observa asta cols este setat la egal digits. Deși au aceeași valoare, reprezintă lucruri diferite. digits variabila reprezintă cifrele care intră într-un pătrat pentru a rezolva puzzle-ul. cols variabila reprezintă numele coloanelor din grilă.

Pătratele sunt, de asemenea, definite ca șiruri, dar șirurile sunt create cu o funcție:

def cross(A, B):
    "Cross product of elements in A and elements in B."
    return [a+b for a in A for b in B]

squares  = cross(rows, cols)

Partea de returnare a cross funcție ( [a+b for a in A for b in B]) este doar un mod fantezist de a scrie acest cod:

squares = []
for a in rows:
    for b in cols:
        squares.append(a+b)

squares variabila este acum egală cu o listă cu toate numele pătratelor.

['A1', 'A2', 'A3', 'A4', 'A5', 'A6', 'A7', 'A8', 'A9', 'B1', 'B2', 'B3', 'B4', 'B5', 'B6', 'B7', 'B8', 'B9', 'C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9', 'D1', 'D2', 'D3', 'D4', 'D5', 'D6', 'D7', 'D8', 'D9', 'E1', 'E2', 'E3', 'E4', 'E5', 'E6', 'E7', 'E8', 'E9', 'F1', 'F2', 'F3', 'F4', 'F5', 'F6', 'F7', 'F8', 'F9', 'G1', 'G2', 'G3', 'G4', 'G5', 'G6', 'G7', 'G8', 'G9', 'H1', 'H2', 'H3', 'H4', 'H5', 'H6', 'H7', 'H8', 'H9', 'I1', 'I2', 'I3', 'I4', 'I5', 'I6', 'I7', 'I8', 'I9']

Fiecare pătrat din grilă are 3 unități și 20 de colegi. Unitățile unui pătrat sunt rândul, coloana și caseta în care apare. Colegii unui pătrat sunt toate celelalte pătrate din unități. De exemplu, iată unitățile și colegii pentru pătratul C2:

1612105991 781 Cum sa joci si sa castigi Sudoku Folosirea matematicii

Toate unitățile pentru fiecare pătrat sunt create folosind cross funcționează cu următorul cod:

unitlist = ([cross(rows, c) for c in cols] +
            [cross(r, cols) for r in rows] +
            [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])

În Python un dicționar este o colecție de perechi de valori cheie. Următoarele linii de cod creează dicționare care folosesc numele pătratelor ca chei și cele trei unități sau 20 de colegi ca valori.

units = dict((s, [u for u in unitlist if s in u]) 
             for s in squares)
peers = dict((s, set(sum(units[s],[]))-set([s]))
             for s in squares)

Acum, cele 3 unități ale „C2” pot fi accesate cu units['C2'] și va da următorul rezultat:

[['A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2'], ['C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'], ['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3']]

În continuare, vom avea nevoie de două reprezentări ale grilei complete de joc Sudoku. Un format textual numit grid va fi starea inițială a puzzle-ului.

O altă reprezentare a grilei va fi, de asemenea, necesară pentru a descrie intern starea actuală a unui puzzle. Acesta va urmări toate valorile posibile rămase pentru fiecare pătrat și va fi denumit values.

Similar cu units și peers, values va fi un dicționar cu pătrate drept chei. Valoarea fiecărei taste va fi un șir de cifre care sunt cifrele posibile pentru pătrat. Dacă cifra a fost dată în puzzle sau a fost descoperită, va exista doar o cifră în cheie. De exemplu, dacă există o grilă în care A1 este 6 și A2 este gol, values ar arăta ca. {'A1': '6', 'A2': '123456789', ...}.

Funcții de analiză a grilei și valorile grilei

parse_grid funcția (codul de mai jos) convertește grila într-un dicționar de valori posibile. grid este puzzle-ul Sukou dat. grid_values funcția extrage valorile importante care sunt cifre, 0, și .. În values dicționar, pătratele sunt cheile și cifrele date în grilă sunt valorile.

Pentru fiecare pătrat cu o valoare dată, assign funcția este utilizată pentru a atribui valoarea pătratului și a elimina valoarea de la colegi. assign funcția este acoperită în curând. Dacă ceva nu merge bine, funcția returnează False.

Iată codul pentru parse_grid și grid_values funcții.

def parse_grid(grid):
    """Convert grid to a dict of possible values, {square: digits}, or
    return False if a contradiction is detected."""
    ## To start, every square can be any digit; then assign values from the grid.
    values = dict((s, digits) for s in squares)
    for s,d in grid_values(grid).items():
        if d in digits and not assign(values, s, d):
            return False ## (Fail if we can't assign d to square s.)
    return values

def grid_values(grid):
    "Convert grid into a dict of {square: char} with '0' or '.' for empties."
    chars = [c for c in grid if c in digits or c in '0.']
    assert len(chars) == 81
    return dict(zip(squares, chars))

Propagarea constrângerii

Valorile inițiale pentru pătrate vor fi fie cifre specifice (1-9), fie o valoare goală. Putem aplica constrângeri fiecărui pătrat și putem elimina valori imposibile.

Norvig folosește două strategii pentru a ajuta la determinarea valorilor corecte pentru pătrate (care corespund strategiilor de mai sus):

(1) Dacă un pătrat are o singură valoare posibilă, atunci eliminați acea valoare de la colegii pătratului.
(2) Dacă o unitate are un singur loc posibil pentru o valoare, atunci puneți valoarea acolo.

Un exemplu al primei strategii este că, dacă știm că A1 are o valoare de 5, atunci 5 poate fi eliminat din toți cei 20 de colegi.

Iată un exemplu al celei de-a doua strategii: dacă se poate determina că niciunul dintre A1 până la A8 nu conține 9 ca valoare posibilă, atunci putem fi siguri că A9 are o valoare de 9, deoarece 9 trebuie să apară undeva în unitate.

De fiecare dată când un pătrat este actualizat, acesta va provoca posibile actualizări pentru toți colegii săi. Acest proces va continua și se numește propagarea constrângerii.

Atribuiți funcția

assign(values, s, d) funcția se numește în interiorul parse_grid funcţie. Returnează valorile actualizate. Acceptă trei argumente: values, s, și d.

Tine minte, values este un dicționar care asociază fiecare pătrat la toate valorile cifrei posibile pentru acel pătrat. s este pătratul căruia îi atribuim o valoare și d este valoarea care trebuie atribuită pătratului. La inceput d provine din puzzle-ul dat pe care îl rezolvăm.

Apelează funcția eliminate(values, s, d) pentru a elimina fiecare valoare din s cu excepția d.

Dacă există o contradicție, cum ar fi două pătrate cărora li se atribuie același număr, funcția de eliminare va întoarce False.

def assign(values, s, d):
    """Eliminate all the other values (except d) from values[s] and propagate.
    Return values, except return False if a contradiction is detected."""
    other_values = values[s].replace(d, '')
    if all(eliminate(values, s, d2) for d2 in other_values):
        return values
    else:
        return False

Eliminați funcția

Am văzut că assign funcția apelează eliminate funcţie. Funcția de eliminare se numește astfel: eliminate(values, s, d2) for d2 in other_values)

eliminate funcția va elimina valorile despre care știm că nu pot fi o soluție folosind cele două strategii menționate mai sus. Prima strategie este aceea când există o singură valoare potențială pentru s, acea valoare este eliminată de la colegii din s. A doua strategie este aceea că atunci când există o singură locație care are o valoare d poate merge, acea valoare este eliminată de la toți colegii.

Iată funcția completă:

def eliminate(values, s, d):
    """Eliminate d from values[s]; propagate when values or places <= 2.
    Return values, except return False if a contradiction is detected."""
    if d not in values[s]:
        return values ## Already eliminated
    values[s] = values[s].replace(d,'')
    ## (1) If a square s is reduced to one value d2, then eliminate d2 from the peers.
    if len(values[s]) == 0:
        return False ## Contradiction: removed last value
    elif len(values[s]) == 1:
        d2 = values[s]
        if not all(eliminate(values, s2, d2) for s2 in peers[s]):
            return False
    ## (2) If a unit u is reduced to only one place for a value d, then put it there.
    for u in units[s]:
        dplaces = [s for s in u if d in values[s]]
        if len(dplaces) == 0:
            return False ## Contradiction: no place for this value
        elif len(dplaces) == 1:
        # d can only be in one place in unit; assign it there
            if not assign(values, dplaces[0], d):
                return False
    return values

Funcția de afișare

display funcția va afișa rezultatul după apel parse_grid.

def display(values):
    "Display these values as a 2-D grid."
    width = 1+max(len(values[s]) for s in squares)
    line="+".join(['-'*(width*3)]*3)
    for r in rows:
        print(''.join(values[r+c].center(width)+('|' if c in '36' else '') for c in cols))
        if r in 'CF': 
            print(line)
    print()

Iată un exemplu de cum va arăta grila după apelarea funcției de afișare după analizarea unei grile care este un puzzle greu.

1612105991 34 Cum sa joci si sa castigi Sudoku Folosirea matematicii

Veți observa că multe dintre pătrate au multiple valori potențiale, în timp ce unele sunt complet rezolvate. Această grilă de mai sus este rezultatul aplicării de către cele două strategii de sus. Dar, după cum puteți vedea, acele strategii nu sunt suficiente pentru a rezolva complet puzzle-ul.

Există multe modalități de a rezolva o problemă Sukoku, dar unele sunt mult mai eficiente decât altele. Norvig sugerează un anumit tip de algoritm de căutare.

Există câteva lucruri pe care le face algoritmul de căutare. În primul rând, se asigură că nu s-a găsit deja nicio soluție sau contriție. Apoi, alege un pătrat neumplut și ia în considerare toate valorile care sunt încă posibile. În cele din urmă, unul câte unul, încearcă să atribuie pătratului fiecare valoare și caută din poziția rezultată.

Ordinea variabilă este utilizată pentru a alege careul pătrat să înceapă explorarea. Iată cum îl descrie Norvig:

vom folosi o euristică comună numită valori minime rămase, ceea ce înseamnă că alegem pătratul (sau unul dintre) cu numărul minim de valori posibile. De ce? Luați în considerare grila2 de mai sus. Să presupunem că am ales mai întâi B3. Are 7 posibilități (1256789), așa că ne-am aștepta să ghicim greșit cu probabilitatea 6/7. Dacă în schimb am ales G2, care are doar 2 posibilități (89), ne-am aștepta să ne înșelăm cu probabilitatea doar 1/2. Astfel alegem pătratul cu cele mai puține posibilități și cele mai mari șanse de a ghici corect.

Cifrele sunt considerate în ordine numerică.

Aici este search funcție, împreună cu solve funcție care analizează grila inițială și apelurile search.

def solve(grid): return search(parse_grid(grid))

def search(values):
    "Using depth-first search and propagation, try all possible values."
    if values is False:
        return False ## Failed earlier
    if all(len(values[s]) == 1 for s in squares): 
        return values ## Solved!
    ## Chose the unfilled square s with the fewest possibilities
    n,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
    return some(search(assign(values.copy(), s, d)) 
        for d in values[s])

Conform regulilor Sudoku, puzzle-ul este rezolvat când fiecare pătrat are o singură valoare. search funcția se numește recursiv până când puzzle-ul este rezolvat. values este copiat pentru a evita complexitatea.

Aici este some funcție utilizată pentru a verifica dacă o încercare reușește să rezolve puzzle-ul.

def some(seq):
    "Return some element of seq that is true."
    for e in seq:
        if e: return e
    return False

Acest cod va rezolva acum fiecare puzzle Sudoku. Puteți vizualiza codul complet mai jos.

Cod complet de rezolvare Sudoku

def cross(A, B):
    "Cross product of elements in A and elements in B."
    return [a+b for a in A for b in B]

digits="123456789"
rows="ABCDEFGHI"
cols     = digits
squares  = cross(rows, cols)
unitlist = ([cross(rows, c) for c in cols] +
            [cross(r, cols) for r in rows] +
            [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])
units = dict((s, [u for u in unitlist if s in u]) 
             for s in squares)
peers = dict((s, set(sum(units[s],[]))-set([s]))
             for s in squares)

def parse_grid(grid):
    """Convert grid to a dict of possible values, {square: digits}, or
    return False if a contradiction is detected."""
    ## To start, every square can be any digit; then assign values from the grid.
    values = dict((s, digits) for s in squares)
    for s,d in grid_values(grid).items():
        if d in digits and not assign(values, s, d):
            return False ## (Fail if we can't assign d to square s.)
    return values

def grid_values(grid):
    "Convert grid into a dict of {square: char} with '0' or '.' for empties."
    chars = [c for c in grid if c in digits or c in '0.']
    assert len(chars) == 81
    return dict(zip(squares, chars))

def assign(values, s, d):
    """Eliminate all the other values (except d) from values[s] and propagate.
    Return values, except return False if a contradiction is detected."""
    other_values = values[s].replace(d, '')
    if all(eliminate(values, s, d2) for d2 in other_values):
        return values
    else:
        return False

def eliminate(values, s, d):
    """Eliminate d from values[s]; propagate when values or places <= 2.
    Return values, except return False if a contradiction is detected."""
    if d not in values[s]:
        return values ## Already eliminated
    values[s] = values[s].replace(d,'')
    ## (1) If a square s is reduced to one value d2, then eliminate d2 from the peers.
    if len(values[s]) == 0:
        return False ## Contradiction: removed last value
    elif len(values[s]) == 1:
        d2 = values[s]
        if not all(eliminate(values, s2, d2) for s2 in peers[s]):
            return False
    ## (2) If a unit u is reduced to only one place for a value d, then put it there.
    for u in units[s]:
        dplaces = [s for s in u if d in values[s]]
        if len(dplaces) == 0:
            return False ## Contradiction: no place for this value
        elif len(dplaces) == 1:
            # d can only be in one place in unit; assign it there
            if not assign(values, dplaces[0], d):
                return False
    return values

def solve(grid): return search(parse_grid(grid))

def search(values):
    "Using depth-first search and propagation, try all possible values."
    if values is False:
        return False ## Failed earlier
    if all(len(values[s]) == 1 for s in squares): 
        return values ## Solved!
    ## Chose the unfilled square s with the fewest possibilities
    n,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
    return some(search(assign(values.copy(), s, d)) 
        for d in values[s])

def some(seq):
    "Return some element of seq that is true."
    for e in seq:
        if e: return e
    return False