Як грати та вигравати судоку - за допомогою математики та машинного навчання розв’язуйте кожну головоломку судоку

Судоку (та його попередники) грали більше ста років. Коли він вперше з’явився, людям довелося насправді розгадувати головоломки, використовуючи лише свій розум. Тепер у нас є комп’ютери! (Гаразд, так що більшість людей все ще просто використовують свою думку ...)

У цій статті ви дізнаєтеся, як грати та вигравати судоку. Але що ще важливіше, ви дізнаєтесь, як за допомогою машинного навчання легко розгадати кожну головоломку Судоку. Кому потрібно думати, коли ви можете дозволити комп’ютеру думати за вас. ?

Пітер Норвіг розробив елегантну програму, використовуючи Python, щоб виграти судоку за допомогою поширення обмежень та пошуку. Рішення Norvig вважається класичним і часто згадується, коли люди розробляють власний код для гри в судоку. Ознайомившись із судоку та деякими стратегіями, я поетапно розберу код Norvig, щоб ви могли зрозуміти, як це працює.

Що таке судоку?

Судоку - це головоломка з розміщенням чисел, і існує кілька різних типів. Ця стаття про найпопулярніший тип.

Мета полягає в тому, щоб заповнити сітку 9x9 цифрами (1-9), щоб кожен стовпець, рядок та кожна з дев'яти підрешіток 3x3 (також звані полями) містили кожну з цифр від 1 до 9. Загадки починаються з деяких цифри, які вже є в сітці, а інші вам потрібно заповнити.

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

Як вирішити судоку

Вирішуючи головоломку судоку, ви повинні постійно робити дві речі. Перше, що вам слід зробити, це вилучити числа з рядків, стовпців та полів (підмережі 3x3). Друге, що вам слід зробити, - це шукати єдиного кандидата.

У наведеному нижче прикладі можливі цифри для кожного квадрата зазначені меншим шрифтом. Можливі числа визначали, виключаючи всі цифри, що трапляються в одному стовпці, рядку чи полі. Більшість людей визначатимуть можливу кількість по одному ящику за раз, а не по повній сітці.

Після вилучення цифр ви можете шукати одиноких кандидатів. Це означає знайти квадрат, який може бути лише одним із можливих чисел. У прикладі нижче два квадрати, виділені жовтим кольором, повинні містити 1 і 8, оскільки всі інші цифри були виключені, оскільки вони вже відображаються в стовпці, рядку або полі квадрата.

Тепер, коли два квадрати, виділені жовтим кольором, відомі, це виключає більше можливостей інших квадратів. Тепер ви знаєте, що квадрат, виділений синім кольором, повинен бути 7.

Якщо ви продовжуєте знаходити єдиних кандидатів, а потім виключаєте варіанти з інших квадратів, ви можете врешті-решт дійти до точки, коли більше не буде одиночних кандидатів.

На цьому етапі ви можете шукати можливі рішення квадратів, де число знаходиться лише в одному квадраті у полі, рядку або стовпці. У наведеному нижче прикладі ми можемо визначити, що рішення квадрата, виділеного синім кольором, має бути 6, оскільки число 6 не зустрічається ні в одному іншому квадраті в жовтому полі.

Іноді плата досягає стану, коли здається, що кожен нерозгаданий квадрат потенційно може мати кілька значень. Це означає, що ви можете вибрати кілька шляхів, і не очевидно, який шлях призведе до вирішення головоломки.

На той момент необхідно спробувати кожен варіант. Виберіть один і продовжуйте вирішувати, поки не стане зрозумілим, що обраний вами варіант не може бути рішенням. Потім вам доведеться відступити і спробувати інший варіант.

Цей тип пошуку можна легко здійснити за допомогою комп’ютера за допомогою двійкового дерева пошуку. Коли є два різних числа для розв’язання квадрата, необхідно виділити дві різні можливості. Бінарне дерево пошуку дозволить алгоритму спуститися на одну гілку, а потім спробувати іншу групу варіантів.

Зараз ми побачимо код Python, який може розгадати головоломки Судоку, використовуючи метод, подібний до щойно описаного.

Програма Пітера Норвіга на перемогу в судоку

Пітер Норвіг пояснив свій підхід до вирішення судоку та код, який він використав у своїй статті «Розв’язування кожної головоломки судоку».

Комусь може бути важко дотримуватися його пояснення, особливо новачкам. Я розберу все, щоб було легше зрозуміти, як працює код Norvig.

У цій статті код Norvig Python 2 оновлено до Python 3. (перетворення Python 3 Наокі Сібуя.) Я пройдуся по коду кілька рядків за раз, але повний код ви побачите в кінці цієї статті . Деяким людям може бути корисно переглянути повний код, перш ніж читати далі.

Спочатку ми розглянемо основні налаштування та позначення. Ось як Норвіг описує основні позначення, які він використовує у своєму коді:

Головоломка Судоку - це сітка з 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