Hogyan játszhatsz és nyerhetsz Sudoku-t - Matematika és gépi tanulás segítségével megoldhatsz minden Sudoku-rejtvényt

A Sudoku-t (és elődeit) több mint száz éve játszották. Amikor először megjelent, az embereknek csak a tudatukkal kellett megoldaniuk a rejtvényeket. Most már vannak számítógépeink! (Ok, így a legtöbb ember még mindig csak az eszét használja ...)

Ebben a cikkben megtudhatja, hogyan kell játszani és megnyerni a Sudokut. De ami még ennél is fontosabb, megtanulja, hogyan kell használni a gépi tanulást a Sudoku-rejtvények egyszerű megoldásához. Kinek kell gondolkodnia, amikor hagyhatja, hogy a számítógép helyettetek gondolkodjon. ?

Peter Norvig egy elegáns programot fejlesztett ki a Python segítségével a sudoku megnyerésére a kényszerterjesztés és a keresés segítségével. Norvig megoldását klasszikusnak tekintik, és gyakran hivatkoznak rá, amikor az emberek saját kódot fejlesztenek ki a Sudoku játékához. Miután áttekintettem a Sudoku-t és néhány stratégiát, lépésről lépésre lebontom Norvig kódját, hogy megértsétek a működését.

Mi a Sudoku?

A Sudoku egy számelhelyezési puzzle, és van néhány különböző típus. Ez a cikk a legnépszerűbb típusról szól.

A cél egy 9x9-es rács kitöltése számokkal (1–9) úgy, hogy minden oszlop, sor és a kilenc 3x3-as alrács (más néven doboz) mindegyike tartalmazza az egyes számjegyeket 1-től 9-ig. A rejtvények néhányal kezdődnek a rácson lévő számok, és rajtad múlik, hogy kitölti-e a többi számot.

Az alábbi képen, amely egy Sudoku játékból származik, a kék színnel kiemelt négyzetbe beírandó szám nem lehet az oszlopnak, a sornak és a 3x3 mezőnek megfelelő sárga négyzet egyikében sem.

Hogyan lehet megoldani a Sudoku-t

A Sudoku rejtvény megoldása során folyamatosan két dolgot kell tennie. Az első dolog, amit meg kell tennie, hogy törölje a számokat a sorokból, oszlopokból és dobozokból (3x3 részrács). A második dolog, amit meg kell tennie, az az, hogy egyetlen jelöltet keressen.

Az alábbi példában az egyes négyzetek lehetséges számai kisebb betűtípussal vannak feltüntetve. A lehetséges számokat az összes oszlopban, sorban vagy mezőben előforduló számjegyek kiküszöbölésével határoztuk meg. A legtöbb ember meghatározza a lehetséges számot egy-egy dobozhoz, a teljes rács helyett.

A számok kiküszöbölése után egyetlen jelöltet kereshet. Ez azt jelenti, hogy keressünk egy négyzetet, amely csak egy lehetséges szám lehet. Az alábbi példában a két sárga kiemelt négyzetnek tartalmaznia kell 1-et és 8-at, mert az összes többi számjegyet eltávolították, mivel már megjelennek a négyzet oszlopában, sorában vagy mezőjében.

Most, hogy a sárga színnel kiemelt két négyzet ismert, ez több lehetőséget kizár a többi négyzetből. Most már tudja, hogy a kék színnel kiemelt négyzetnek 7-nek kell lennie.

Ha folyamatosan megtalálja az egyedüli jelölteket, majd kiküszöböli az opciókat a többi mezőből, akkor eljuthat arra a pontra, hogy nincs többé egyetlen jelölt.

Ezen a ponton kereshet olyan megoldásokat olyan négyzetekre, ahol a szám csak egy négyzetben van egy mezőben, sorban vagy oszlopban. Az alábbi példában megállapíthatjuk, hogy a kék színnel kiemelt négyzet megoldásának 6-nak kell lennie, mivel a 6-os szám a sárga mező egyetlen más négyzetében sem fordul elő.

Néha a tábla eléri azt az állapotot, ahol úgy tűnik, hogy minden megoldatlan négyzet több értéket is tartalmazhat. Ez azt jelenti, hogy több utat is választhat, és nem nyilvánvaló, melyik út vezet a rejtvény megoldásához.

Ezen a ponton ki kell próbálni az egyes lehetőségeket. Válasszon egyet, és folytassa a megoldást, amíg kiderül, hogy a választott opció nem lehet megoldás. Ezután vissza kell térnie és ki kell próbálnia egy másik lehetőséget.

Ez a fajta keresés könnyen elvégezhető számítógéppel egy bináris keresőfa segítségével. Ha négyzet megoldására két különböző szám közül lehet választani, akkor két különböző lehetőségre van szükség. A bináris keresési fa lehetővé teszi, hogy egy algoritmus lefelé haladjon a választások egyik ágán, majd egy másik választási lehetőséggel próbálkozzon.

Most olyan Python kódot fogunk látni, amely képes megoldani a Sudoku rejtvényeket az imént leírtakhoz hasonló módszerrel.

Peter Norvig programja a Sudoku elnyerésére

Peter Norvig a Sudoku rejtvények megoldása című cikkében elmagyarázta a Sudoku megoldásának megközelítését és az általa használt kódot.

Egyesek kissé nehezen követhetik a magyarázatát, főleg a kezdők. Bontom a dolgokat, így könnyebb megérteni, hogyan működik Norvig kódja.

Ebben a cikkben a Norvig Python 2 kódja Python 3-ra frissült (Pyoki 3 konverziót Naoki Shibuya végezte.) Végigmegyek a kódon, néhány sorban, de a teljes kódot a cikk végén láthatja. . Néhány ember számára hasznos lehet a teljes kód átnézése, mielőtt továbbolvasna.

Először kitérünk az alapbeállításra és a jelölésre. Norvig a következőképpen írja le az alapvető jelölést, amelyet a kódjában használ:

A Sudoku puzzle egy 81 négyzetből álló rács ; A rajongók többsége az 1–9. oszlopokat, az AI sorokat címkézi, és kilenc négyzetből (oszlopból, sorból vagy dobozból álló) álló gyűjteményt nevez egységnek, és az egységet megosztó négyzeteket társainak .

Itt vannak a négyzetek neve:

 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 a számokat, sorokat és oszlopokat karakterláncként határozza meg:

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

Észre fogja venni, hogy colsez egyenlőre van állítva digits. Míg ezek azonos értéket képviselnek, különböző dolgokat képviselnek. A digitsváltozó azokat a számjegyeket jelöli, amelyek négyzetben mennek a rejtvény megoldására. A colsváltozó a rács oszlopainak nevét jelöli.

A négyzeteket szintén karakterláncként definiálják, de a karakterláncokat egy függvénnyel hozzák létre:

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)

A crossfüggvény ( [a+b for a in A for b in B]) visszatérő része csak egy fantasztikus módja ennek a kódnak az írásakor:

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

A squaresváltozó most megegyezik az összes négyzetnév listájával.

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

A rács minden négyzetének 3 egysége és 20 társa van. A négyzet egységei azok a sorok, oszlopok és négyzetek, amelyekben megjelenik. A négyzet társai az egység többi négyzetét jelentik. Például itt vannak a C2 négyzet egységei és társai:

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:

minimális fennmaradó értéknek nevezett közös heurisztikát fogjuk használni, ami azt jelenti, hogy a négyzetet (vagy annak egyikét) választjuk a lehető legkisebb számú értékkel. Miért? Tekintsük a fenti rács2-et. Tegyük fel, hogy először a B3-at választottuk. 7 lehetősége van (1256789), ezért azt várnánk, hogy rosszul tippelünk a 6/7 valószínűséggel. Ha ehelyett a G2-t választjuk, amelynek csak 2 lehetősége van (89), akkor azt várnánk, hogy tévedünk, ha csak a valószínűsége 1/2. Így a legkevesebb lehetőséggel rendelkező négyzetet választjuk, és a legjobb találgatásra van esély.

A számjegyeket numerikus sorrendben vesszük figyelembe.

Itt van a searchfüggvény, valamint solvea kezdeti rácsot elemző és hívó függvény 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