Kako igrati i osvojiti Sudoku - Korištenje matematike i strojnog učenja za rješavanje svake Sudoku zagonetke

Sudoku (i njegovi prethodnici) igrao se više od stotinu godina. Kad je prvi put izašlo, ljudi su zapravo morali rješavati zagonetke koristeći samo svoj um. Sad imamo računala! (Ok, tako da većina ljudi i dalje samo koristi svoj um ...)

U ovom ćete članku naučiti kako igrati i osvajati Sudoku. No što je još važnije, naučit ćete kako pomoću strojnog učenja lako riješiti svaku Sudoku zagonetku. Tko treba razmišljati kad možete pustiti računalo da misli umjesto vas. ?

Peter Norvig razvio je elegantan program koristeći Python za osvajanje sudokua pomoću širenja ograničenja i pretraživanja. Norvigovo rješenje smatra se klasikom i na njega se često govori kada ljudi razvijaju vlastiti kôd za igranje Sudokua. Nakon pregleda Sudokua i nekih strategija, korak po korak ću razbiti Norvigov kôd kako biste mogli razumjeti kako to radi.

Što je Sudoku?

Sudoku je zagonetka za postavljanje brojeva i postoji nekoliko različitih vrsta. Ovaj je članak o najpopularnijoj vrsti.

Cilj je ispuniti mrežu od 9x9 znamenkama (1-9), tako da svaki stupac, redak i svaki od devet 3x3 podmreža (koje se nazivaju i okviri) sadrže svaku od znamenki od 1 do 9. Slagalice započinju s nekim brojevi koji su već na mreži, a na vama je da popunite ostale brojeve.

Na donjoj slici iz igre Sudoku, broj koji treba ići na plavo označenom kvadratu ne može biti ni na jednom od žutih kvadrata koji odgovaraju stupcu, retku i polju 3x3.

Kako riješiti Sudoku

Pri rješavanju Sudoku zagonetke trebali biste neprestano raditi dvije stvari. Prvo što biste trebali učiniti je eliminirati brojeve iz redaka, stupaca i okvira (3x3 podmreže). Druga stvar koju biste trebali učiniti je potražiti jednog kandidata.

U donjem primjeru mogući brojevi za svaki kvadrat zabilježeni su manjim fontom. Mogući brojevi određeni su uklanjanjem svih znamenki koje se pojavljuju u istom stupcu, retku ili okviru. Većina će ljudi odrediti mogući broj za jedan okvir istovremeno, umjesto za punu mrežu.

Nakon što uklonite brojeve, možete potražiti pojedinačne kandidate. To znači pronaći kvadrat koji može biti samo jedan mogući broj. U primjeru u nastavku, dva žuto označena kvadrata moraju sadržavati 1 i 8 jer su sve ostale znamenke uklonjene jer se već pojavljuju u stupcu, retku ili okviru kvadrata.

Sad kad su poznata dva polja označena žutom bojom, to eliminira više mogućnosti s drugih kvadrata. Sada znate da kvadrat označen plavom bojom mora biti 7.

Ako nastavite tražiti pojedinačne kandidate, a zatim uklanjate opcije s drugih kvadrata, na kraju ćete možda doći do točke kada više nema pojedinačnih kandidata.

U ovom trenutku možete potražiti moguća rješenja kvadrata gdje je broj samo u jednom kvadratu u okviru, retku ili stupcu. U donjem primjeru možemo utvrditi da rješenje kvadrata označenog plavom bojom mora biti 6, jer se broj 6 ne pojavljuje ni na jednom drugom kvadratu u žutom okviru.

Ponekad ploča dosegne stanje u kojem se čini da bi svaki neriješeni kvadrat mogao biti višestruka vrijednost. To znači da postoji više putova koje biste mogli odabrati i nije očito koji će put dovesti do rješavanja zagonetke.

U tom je trenutku potrebno isprobati svaku opciju. Odaberite jedan i nastavite rješavati sve dok ne postane jasno da opcija koju ste odabrali ne može biti rješenje. Tada ćete se morati vratiti i isprobati drugu opciju.

Ova vrsta pretraživanja može se lako obaviti s računalom pomoću binarnog stabla pretraživanja. Kada postoji mogućnost dva različita broja za rješavanje kvadrata, potrebno je podijeliti se na dvije različite mogućnosti. Binarno stablo pretraživanja omogućit će algoritmu da se spusti za jednu granu izbora, a zatim isprobati drugu skupinu izbora.

Sada ćemo vidjeti Python kôd koji može rješavati Sudoku zagonetke koristeći sličnu metodu kao što je upravo opisana.

Program Petera Norviga za osvajanje Sudokua

Peter Norvig objasnio je svoj pristup rješavanju Sudokua i kôd koji je koristio u članku Rješavanje svake Sudoku zagonetke.

Nekima će možda biti teško pratiti njegovo objašnjenje, posebno početnicima. Slomit ću stvari tako da je lakše razumjeti kako funkcionira Norvigov kod.

U ovom je članku Norvigov kôd Python 2 ažuriran na Python 3. (Pretvorbu Pythona 3 Naoki Shibuya.) Kroz kôd ću proći nekoliko redaka, ali cjelovit kôd možete vidjeti na kraju ovog članka . Nekim ljudima može biti korisno pregledati puni kod prije čitanja.

Prvo ćemo pokriti osnovne postavke i notacije. Evo kako Norvig opisuje osnovni zapis koji koristi u svom kodu:

Slagalica Sudoku mreža je od 81 kvadrata; većina entuzijasta označava stupce 1-9, retke AI, a zbirku od devet kvadrata (stupac, redak ili okvir) naziva jedinicom, a kvadrati koji dijele jedinicu imaju vršnjake .

Evo naziva kvadrata:

 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 definira znamenke, retke i stupce kao nizove:

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

Primijetit ćete da colsje postavljeno na jednako digits. Iako su iste vrijednosti, one predstavljaju različite stvari. digitsVarijabla predstavlja znamenke koje idu na trgu riješiti puzzle. colsVarijabla predstavlja nazive stupaca rešetke.

Kvadratići su također definirani kao nizovi, ali nizovi se stvaraju s funkcijom:

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)

Povratni dio crossfunkcije ( [a+b for a in A for b in B]) samo je otmjen način pisanja ovog koda:

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

squaresVarijabla sada jednako popis svih kvadratnih imena.

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

Svaki kvadrat u mreži ima 3 jedinice i 20 vršnjaka. Jedinice kvadrata su red, stupac i okvir u kojem se pojavljuje. Vršnjaci kvadrata su svi ostali kvadrati u jedinicama. Na primjer, evo jedinica i ravnopravnih podataka za kvadrat 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:

koristit ćemo zajedničku heuristiku koja se naziva minimalne preostale vrijednosti, što znači da odabiremo (ili jedan od) kvadrata s minimalnim brojem mogućih vrijednosti. Zašto? Razmotrite grid2 gore. Pretpostavimo da smo prvo odabrali B3. Ima 7 mogućnosti (1256789), pa bismo očekivali da pogrešno pogodimo s vjerovatnoćom 6/7. Ako smo umjesto toga odabrali G2, koji ima samo dvije mogućnosti (89), očekivali bismo da ćemo pogriješiti s vjerojatnosti samo 1/2. Stoga mi biramo kvadrat s najmanje mogućnosti i najboljom šansom da pogodimo u pravu.

Znamenke se razmatraju brojevnim redoslijedom.

Ovdje je searchfunkcija, zajedno s solvefunkcijom koja raščlanjuje početnu mrežu i pozive 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])

Per the rules of Sudoku, the puzzle is solved when each square has only one value. The search function is called recursively until the puzzle is solved. values is copied to avoid complexity.

Here is the some function used to check if an attempt succeeds to solve the puzzle.

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

This code will now solve every Sudoku puzzle. You can view the full code below.

Full Sudoku solver code

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