Как се играе и печели судоку - Използване на математика и машинно обучение за решаване на всеки пъзел судоку

Судоку (и неговите предшественици) се играе повече от сто години. Когато излезе за първи път, хората всъщност трябваше да решават пъзелите, използвайки само умовете си. Сега имаме компютри! (Добре, така че повечето хора все още използват умовете си ...)

В тази статия ще научите как да играете и да печелите Судоку. Но по-важното е, че ще научите как да използвате машинно обучение, за да решавате лесно всеки пъзел на Судоку. Кой се нуждае от мислене, когато можете да оставите компютъра да мисли вместо вас. ?

Питър Норвиг разработи елегантна програма, използвайки Python, за да спечели судоку, използвайки разпространение на ограничения и търсене. Решението на Norvig се счита за класика и често се споменава, когато хората разработват свой собствен код, за да играят судоку. След като прегледах Sudoku и някои стратегии, ще разбия стъпка по стъпка кода на Norvig, за да можете да разберете как работи.

Какво е судоку?

Судоку е пъзел за поставяне на числа и има няколко различни типа. Тази статия е за най-популярния тип.

Целта е да се запълни 9x9 решетка с цифри (1-9), така че всяка колона, ред и всяка от деветте 3x3 подрешетки (наричани още кутии) да съдържат всяка от цифрите от 1 до 9. Пъзелите започват с някои номера, които вече са в мрежата и от вас зависи да попълните останалите числа.

На изображението по-долу от игра Судоку, числото, което трябва да отиде в синьо маркирания квадрат, не може да бъде в нито един от жълтите квадратчета, съответстващи на колоната, реда и полето 3x3.

Как да решим судоку

Когато решавате пъзел судоку, трябва постоянно да правите две неща. Първото нещо, което трябва да направите, е да премахнете числата от редове, колони и полета (3x3 подрешетки). Второто нещо, което трябва да направите, е да потърсите един-единствен кандидат.

В примера по-долу възможните числа за всеки квадрат са отбелязани с по-малък шрифт. Възможните числа бяха определени чрез премахване на всички цифри, които се срещат в една и съща колона, ред или поле. Повечето хора ще определят възможния брой за една кутия наведнъж, вместо за пълната мрежа.

След като премахнете числата, можете да търсите единични кандидати. Това означава да се намери квадрат, който може да бъде само едно възможно число. В примера по-долу двата жълто маркирани квадрата трябва да съдържат 1 и 8, защото всички останали цифри са премахнати, тъй като вече се появяват в колоната, реда или полето на квадрата.

Сега, когато двата квадрата, подчертани в жълто, са известни, това елиминира повече възможности от други квадрати. Сега знаете, че квадратът, подчертан в синьо, трябва да е 7.

Ако продължавате да намирате отделните кандидати и след това елиминирате опции от други квадрати, в крайна сметка може да стигнете до точката, в която няма повече единични кандидати.

На този етап можете да потърсите възможни решения на квадрати, където числото е само в един квадрат в поле, ред или колона. В примера по-долу можем да определим, че решението на квадрата, подчертан в синьо, трябва да бъде 6, тъй като числото 6 не се среща в нито един друг квадрат в жълтото поле.

Понякога дъската ще достигне състояние, при което изглежда, че всеки неразрешен квадрат потенциално може да бъде множество стойности. Това означава, че има множество пътища, които можете да изберете и не е очевидно кой път ще доведе до решаване на пъзела.

В този момент е необходимо да опитате всяка опция. Изберете един и продължете да решавате, докато стане ясно, че избраната от вас опция не може да бъде решение. След това ще трябва да се върнете назад и да опитате друга опция.

Този тип търсене може лесно да се извърши с компютър, използвайки двоично дърво за търсене. Когато има опция за две различни числа за решаване на квадрат, е необходимо да се разпределят в две различни възможности. Двоично дърво за търсене ще позволи на алгоритъм да слезе по един клон на избора и след това да изпробва различен избор.

Сега ще видим кода на Python, който може да решава пъзели Sudoku, използвайки метод, подобен на току-що описания.

Програмата на Питър Норвиг за спечелване на судоку

Питър Норвиг обясни своя подход към решаването на судоку и кода, който използва в статията си „Решаване на всеки пъзел за судоку“.

Някои може да намерят неговото обяснение малко трудно за следване, особено начинаещи. Ще разбия нещата, за да е по-лесно да разбера как работи кодът на Norvig.

В тази статия кодът на Python 2 на Norvig е актуализиран до Python 3. (Преобразуване на Python 3 от Naoki Shibuya.) Ще прегледам кода по няколко реда наведнъж, но можете да видите пълния код в края на тази статия . За някои хора може да е полезно да прегледат пълния код, преди да прочетат.

Първо ще разгледаме основната настройка и нотация. Ето как Norvig описва основните обозначения, които използва в кода си:

Пъзелът Судоку е решетка от 81 квадрата; по-голямата част от ентусиастите обозначават колоните 1-9, редовете AI и наричат ​​колекция от девет квадрата (колона, ред или кутия) единица и квадратите, които споделят единица, на връстниците .

Ето имената на квадратите:

 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 определя цифрите, редовете и колоните като низове:

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

Ще забележите, че colsе настроено на равно digits. Докато те са една и съща стойност, те представляват различни неща. В digitsпроменливата представлява цифрите, които отиват в квадрат, за да решите пъзела. В colsпроменлива представлява имената на колоните на мрежата.

Квадратите също се определят като низове, но низовете се създават с функция:

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)

Връщащата част на crossфункцията ( [a+b for a in A for b in B]) е просто изискан начин за писане на този код:

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

В squaresпроменливата сега се равнява на списък на всички квадратни имена.

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

Всеки квадрат в мрежата има 3 единици и 20 връстници. Единиците на квадрат са редът, колоната и полето, в което се появява. Връстниците на квадрат са всички останали квадрати в единиците. Например, тук са мерните единици и връстници за квадрата 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:

ще използваме обща евристика, наречена минимални оставащи стойности, което означава, че избираме (или една от) квадратурата с минималния брой възможни стойности. Защо? Помислете за grid2 по-горе. Да предположим, че първо сме избрали B3. Той има 7 възможности (1256789), така че очакваме да предположим грешка с вероятност 6/7. Ако вместо това сме избрали G2, който има само 2 възможности (89), бихме очаквали да сгрешим с вероятност само 1/2. По този начин ние избираме квадрата с най-малко възможности и най-голям шанс да познаем правилно.

Цифрите се разглеждат в числов ред.

Тук е searchфункцията, заедно с solveфункцията, която анализира първоначалната мрежа и извиква 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