Sådan spiller og vinder du Sudoku - Brug af matematik og maskinlæring til at løse ethvert Sudoku-puslespil

Sudoku (og dets forgængere) er blevet spillet i over hundrede år. Da det først kom ud, måtte folk faktisk løse gåderne ved kun at bruge deres sind. Nu har vi computere! (Ok, så de fleste bruger stadig bare deres sind ...)

I denne artikel lærer du at spille og vinde Sudoku. Men vigtigere er det, at du lærer, hvordan du bruger maskinlæring til let at løse ethvert Sudoku-puslespil. Hvem har brug for at tænke, når du kan lade computeren tænke for dig. ?

Peter Norvig udviklede et elegant program ved hjælp af Python for at vinde sudoku ved hjælp af begrænsningspropagation og søgning. Norvigs løsning betragtes som en klassiker og omtales ofte, når folk udvikler deres egen kode for at spille Sudoku. Efter at have gennemgået Sudoku og nogle strategier, vil jeg nedbryde Norvigs kode trin for trin, så du kan forstå, hvordan det fungerer.

Hvad er Sudoku?

Sudoku er et nummerplaceringspuslespil, og der er et par forskellige typer. Denne artikel handler om den mest populære type.

Målet er at udfylde et 9x9 gitter med cifre (1-9), så hver kolonne, række og hvert af de ni 3x3 underordninger (også kaldet felter) alle indeholder hvert af cifrene fra 1 til 9. Gåderne starter med nogle numre, der allerede er på nettet, og det er op til dig at udfylde de andre numre.

På billedet nedenfor fra et Sudoku-spil kan antallet, der skal gå i den blå fremhævede firkant, ikke være i nogen af ​​de gule firkanter, der svarer til kolonne-, række- og 3x3-feltet.

Sådan løses Sudoku

Når du løser et Sudoku-puslespil, skal du konstant gøre to ting. Den første ting, du skal gøre, er at fjerne tal fra rækker, kolonner og felter (3x3 subgrids). Den anden ting du skal gøre er at lede efter en enkelt kandidat.

I eksemplet nedenfor er de mulige tal for hver firkant noteret med en mindre skrifttype. De mulige tal blev bestemt ved at fjerne alle cifre, der findes i samme kolonne, række eller felt. De fleste mennesker bestemmer det mulige antal for en kasse ad gangen i stedet for for det fulde gitter.

Når du har fjernet antallet, kan du se efter enkeltkandidater. Det betyder at finde en firkant, der kun kan være et muligt tal. I eksemplet nedenfor skal de to gule fremhævede firkanter indeholde 1 og 8, fordi alle de andre cifre er blevet fjernet, da de allerede vises i firkantens kolonne, række eller felt.

Nu hvor de to firkanter markeret med gult er kendt, eliminerer det flere muligheder fra andre firkanter. Nu ved du, at firkanten fremhævet med blåt skal være 7.

Hvis du fortsætter med at finde de enkelte kandidater og derefter fjerne muligheder fra andre firkanter, kan du til sidst nå det punkt, hvor der ikke er flere enkeltkandidater.

På dette tidspunkt kan du se efter mulige løsninger på firkanter, hvor antallet kun er i en enkelt firkant i en boks, række eller kolonne. I eksemplet nedenfor kan vi bestemme, at løsningen på pladsen fremhævet med blåt skal være 6, da tallet 6 ikke forekommer i nogen anden firkant i den gule boks.

Nogle gange vil bestyrelsen nå en tilstand, hvor det ser ud til, at hvert uløst kvadrat potentielt kan være flere værdier. Det betyder, at der er flere stier, du kan vælge, og det er ikke indlysende, hvilken sti der fører til at løse puslespillet.

På det tidspunkt er det nødvendigt at prøve hver mulighed. Vælg en, og bliv ved med at løse, indtil det bliver klart, at den valgte mulighed ikke kan være en løsning. Du bliver derefter nødt til at gå tilbage og prøve en anden mulighed.

Denne type søgning kan let udføres med en computer ved hjælp af et binært søgetræ. Når der er mulighed for to forskellige tal til at løse en firkant, er det nødvendigt at udbrede i to forskellige muligheder. Et binært søgetræ giver en algoritme mulighed for at gå ned ad en gren af ​​valg og derefter prøve en anden række valg.

Nu skal vi se Python-kode, der kan løse Sudoku-gåder ved hjælp af en lignende metode til det, der netop blev beskrevet.

Peter Norvigs program for at vinde Sudoku

Peter Norvig forklarede sin tilgang til løsning af Sudoku og koden, han brugte i sin artikel Solving Every Sudoku Puzzle.

Nogle finder måske hans forklaring lidt svær at følge, især begyndere. Jeg vil nedbryde tingene, så det er lettere at forstå, hvordan Norvigs kode fungerer.

I denne artikel er Norvigs Python 2-kode blevet opdateret til Python 3. (Python 3-konvertering af Naoki Shibuya.) Jeg gennemgår koden et par linjer ad gangen, men du kan se den fulde kode i slutningen af ​​denne artikel . For nogle mennesker kan det være nyttigt at se over hele koden, før du læser videre.

Først dækker vi den grundlæggende opsætning og notation. Sådan beskriver Norvig den grundlæggende notation, som han bruger i sin kode:

Et Sudoku-puslespil er et gitter på 81 firkanter; flertallet af entusiaster markerer kolonnerne 1-9, rækken AI og kalder en samling på ni firkanter (kolonne, række eller boks) en enhed og kvadraterne, der deler en enhed, er ligestillede .

Her er navnene på firkanterne:

 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 definerer cifre, rækker og kolonner som strenge:

digits = '123456789' rows = 'ABCDEFGHI' cols = digits

You will notice that cols is set to equal digits. While they are the same value, the represent different things. The digits variable represents the digits that go in a square to solve the puzzle. The cols variable represents the names of the columns of the grid.

The squares are also defined as strings but the strings are created with a function:

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)

The return part of the cross function ( [a+b for a in A for b in B]) is just a fancy way of writing this code:

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

The squares variable now equals a list of all the square names.

['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']

Each square in the grid has 3 units and 20 peers. The units of a square are the row, column, and box that it appears in. The peers of a square are all the other squares in the units. For example, here are the units and peers for the square C2:

All the units for each square are created using the cross function with the following code:

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')])

In Python a dictionary is a collection of key value pairs. The following lines of code creates dictionaries that use the square names as the keys and the three units or 20 peers as the values.

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)

Now, the 3 units of ‘C2’ can be accessed with units['C2'] and will give the following result:

[['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']]

Next we'll need two representations of the full Sudoku playing grid. A textual format named grid will be the initial state of the puzzle.

Another representation of the grid will also be needed to internally describe the current state of a puzzle. It will keep track of all remaining possible values for each square and be named values.

Similar to units and peers, values will be a dictionary with squares as keys. The value of each key will be a string of digits that are the possible digits for the square. If the digit was given in the puzzle or has been figured out, there will only be one digit in the key. For example, if there is a grid where A1 is 6 and A2 is empty, values would look like {'A1': '6', 'A2': '123456789', ...}.

Parse Grid and Grid Values Functions

The parse_grid function (code below) converts the grid to a dictionary of possible values.  The grid is the given Sukou puzzle. The grid_values function extracts the important values which are digits, 0, and .. In the values dictionary, the squares are the keys and the given digits in the grid are the values.

For each square with a given value, the assign function is used to assign the value to the square and eliminate the value from the peers. The assign function is covered soon. If anything goes wrong, the function returns False.

Here is the code for the parse_grid and grid_values functions.

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))

Constraint Propagation

The initial values for the squares will be either specific digits (1-9) or an empty value. We can apply constraints to each square and eliminate values that are impossible.

Norvig uses two strategies to help determine the correct values for the squares (which correspond to the strategies above):

(1) If a square has only one possible value, then eliminate that value from the square's peers.

(2) If a unit has only one possible place for a value, then put the value there.

An example of the first strategy is that if we know that A1 has a value of 5, then 5 can be removed from all 20 of its peers.

Here is an example of the second strategy: if it can be determined that none of A1 through A8 contains 9 as a possible value, then we can be sure that A9 has a value of 9 since 9 must occur somewhere in the unit.

Every time a square is updated, it will cause possible updates to all its peers. This process will keep continuing and it is called constraint propagation.

Assign Function

The assign(values, s, d) function is called inside the parse_grid function. It returns the updated values. It accepts three arguments: values, s, and d.

Remember, values is a dictionary that associates each square to all possible digit values for that square. s is the square we are assigning a value to and d is the value that needs to be assigned to the square. At the start d comes from the given puzzle we are solving.

It calls the function eliminate(values, s, d) to eliminate every value from s except d.

If there is a contradiction, such as two squares being assigned the same number, the eliminate function will return 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

Eliminate Function

We saw that the assign function calls the eliminate function. The eliminate function is called like this: eliminate(values, s, d2) for d2 in other_values)

The eliminate function will eliminate values that we know can't be a solution using the two strategies mentioned above. The first strategy is that when there is only one potential value for s, that value is removed from the peers of s. The second strategy is that when there is only one location that a value d can go, that value is removed from all the peers.

Here is the full function:

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

Display Function

The display function will display the result after calling 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()

Here is an example of what the grid will look like after calling the display function after parsing a grid that is a hard puzzle.

You will notice that many of the squares have multiple potential values, while some are completely solved. This grid above is the result of rote application of the two strategies from above. But as you can see, those strategies alone are not enough to completely solve the puzzle.

Search

There are many ways to solve a Sukoku problem but some are much more efficient than others. Norvig suggests a specific type of search algorithm.

There are a few things the search algorithm does. First, it makes sure that no solution or contrition have already been found. Then, it chooses an unfilled square and considers all values that are still possible. Finally, one at a time, it tries to assign the square each value, and searches from the resulting position.

Variable ordering is used to choose which square to start exploring. Here is how Norvig describes it:

Vi bruger en fælles heuristik kaldet minimum restværdier, hvilket betyder at vi vælger (eller en af) firkanten med det mindste antal mulige værdier. Hvorfor? Overvej grid2 ovenfor. Antag, at vi først valgte B3. Det har 7 muligheder (1256789), så vi forventer at gætte forkert med sandsynlighed 6/7. Hvis vi i stedet valgte G2, som kun har 2 muligheder (89), ville vi forvente at være forkert med sandsynligheden kun 1/2. Således vælger vi pladsen med færrest muligheder og den bedste chance for at gætte rigtigt.

Cifrene betragtes i numerisk rækkefølge.

Her er searchfunktionen sammen med den solvefunktion, der analyserer det oprindelige gitter og opkald 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])

I henhold til Sudoku-reglerne løses puslespillet, når hver firkant kun har en værdi. Den searchfunktion kaldes rekursivt indtil puslespillet er løst. valueskopieres for at undgå kompleksitet.

Her er den somefunktion, der bruges til at kontrollere, om et forsøg lykkes at løse gåden.

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

Denne kode løser nu ethvert Sudoku-puslespil. Du kan se den fulde kode nedenfor.

Fuld Sudoku-løsningskode

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  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