Cara Bermain dan Menang Sudoku - Menggunakan Matematika dan Pembelajaran Mesin untuk Memecahkan Setiap Puzzle Sudoku

Sudoku (dan pendahulunya) telah dimainkan selama lebih dari seratus tahun. Ketika pertama kali keluar, orang harus benar-benar memecahkan teka-teki hanya dengan menggunakan pikiran mereka. Sekarang kami memiliki komputer! (Oke, jadi kebanyakan orang masih menggunakan pikiran mereka ...)

Di artikel ini, Anda akan belajar cara bermain dan memenangkan Sudoku. Namun yang lebih penting, Anda akan belajar cara menggunakan pembelajaran mesin untuk menyelesaikan setiap teka-teki Sudoku dengan mudah. Siapa yang perlu berpikir ketika Anda bisa membiarkan komputer berpikir untuk Anda. ?

Peter Norvig mengembangkan program elegan menggunakan Python untuk memenangkan sudoku menggunakan propagasi dan pencarian batasan. Solusi Norvig dianggap klasik dan sering digunakan saat orang mengembangkan kode mereka sendiri untuk bermain Sudoku. Setelah meninjau Sudoku dan beberapa strategi, saya akan memecah kode Norvig selangkah demi selangkah sehingga Anda dapat memahami cara kerjanya.

Apa itu Sudoku?

Sudoku adalah teka-teki penempatan angka dan ada beberapa jenis yang berbeda. Artikel ini tentang jenis yang paling populer.

Tujuannya adalah untuk mengisi kisi berukuran 9x9 dengan angka (1-9) sehingga setiap kolom, baris, dan masing-masing dari sembilan subkisi 3x3 (juga disebut kotak) semuanya berisi setiap digit dari 1 sampai 9. Teka-teki dimulai dengan beberapa nomor sudah ada di grid dan terserah Anda untuk mengisi nomor lainnya.

Pada gambar di bawah ini dari permainan Sudoku, angka yang berada di kotak biru yang disorot tidak boleh berada di kotak kuning mana pun yang sesuai dengan kolom, baris, dan kotak 3x3.

Bagaimana mengatasi Sudoku

Saat memecahkan teka-teki Sudoku, Anda harus terus-menerus melakukan dua hal. Hal pertama yang harus Anda lakukan adalah menghilangkan angka dari baris, kolom, dan kotak (subkisi 3x3). Hal kedua yang harus Anda lakukan adalah mencari calon tunggal.

Dalam contoh di bawah ini, kemungkinan angka untuk setiap kotak dicatat dengan font yang lebih kecil. Jumlah yang mungkin ditentukan dengan menghilangkan semua digit yang muncul di kolom, baris, atau kotak yang sama. Kebanyakan orang akan menentukan nomor yang mungkin untuk satu kotak pada satu waktu, bukan untuk kotak penuh.

Setelah Anda menghilangkan angka, Anda bisa mencari kandidat tunggal. Itu berarti mencari kuadrat yang hanya bisa menjadi satu angka yang mungkin. Dalam contoh di bawah ini, dua kotak yang disorot kuning harus berisi 1 dan 8 karena semua digit lainnya telah dihilangkan karena sudah muncul di kolom, baris, atau kotak persegi.

Sekarang setelah dua kotak yang disorot dengan warna kuning diketahui, itu menghilangkan lebih banyak kemungkinan dari kotak lain. Sekarang Anda tahu bahwa persegi yang disorot dengan warna biru haruslah 7.

Jika Anda terus mencari kandidat tunggal dan kemudian menghilangkan opsi dari kotak lain, Anda pada akhirnya dapat mencapai titik di mana tidak ada lagi kandidat tunggal.

Pada titik ini, Anda dapat mencari solusi yang mungkin untuk persegi yang angkanya hanya dalam satu kotak dalam kotak, baris, atau kolom. Dalam contoh di bawah ini, kita dapat menentukan bahwa solusi untuk persegi yang disorot dengan warna biru haruslah 6 karena angka 6 tidak muncul di persegi lain di dalam kotak kuning.

Terkadang papan akan mencapai keadaan di mana tampaknya setiap kotak yang tidak terpecahkan berpotensi menjadi beberapa nilai. Itu berarti ada beberapa jalur yang dapat Anda pilih dan tidak jelas jalur mana yang akan mengarah untuk memecahkan teka-teki tersebut.

Pada saat itu perlu untuk mencoba setiap opsi. Pilih satu dan terus selesaikan sampai jelas bahwa opsi yang Anda pilih tidak bisa menjadi solusi. Anda kemudian harus mundur dan mencoba opsi yang berbeda.

Jenis pencarian ini dapat dengan mudah dilakukan dengan komputer menggunakan pohon pencarian biner. Ketika ada opsi dari dua angka berbeda untuk menyelesaikan sebuah kuadrat, Anda perlu membagi dua kemungkinan yang berbeda. Pohon pencarian biner akan memungkinkan algoritme untuk turun ke satu cabang pilihan, dan kemudian mencoba berbagai pilihan.

Sekarang kita akan melihat kode Python yang dapat memecahkan teka-teki Sudoku menggunakan metode yang mirip dengan yang baru saja dijelaskan.

Program Peter Norvig untuk memenangkan Sudoku

Peter Norvig menjelaskan pendekatannya untuk memecahkan Sudoku dan kode yang dia gunakan dalam artikelnya Memecahkan Setiap Puzzle Sudoku.

Beberapa orang mungkin menganggap penjelasannya agak sulit diikuti, terutama pemula. Saya akan memecah semuanya sehingga lebih mudah untuk memahami cara kerja kode Norvig.

Pada artikel ini, kode Python 2 Norvig telah diperbarui menjadi Python 3. (Konversi Python 3 oleh Naoki Shibuya.) Saya akan membahas kode beberapa baris sekaligus tetapi Anda dapat melihat kode lengkapnya di akhir artikel ini . Bagi sebagian orang, mungkin berguna untuk melihat-lihat kode lengkap sebelum melanjutkan membaca.

Pertama, kita akan membahas pengaturan dan notasi dasar. Inilah cara Norvig menjelaskan notasi dasar yang dia gunakan dalam kodenya:

Teka-teki Sudoku adalah kotak yang terdiri dari 81 kotak; mayoritas peminat memberi label kolom 1-9, baris AI, dan menyebut kumpulan sembilan kotak (kolom, baris, atau kotak) sebagai unit dan kotak yang berbagi satu unit sebagai peer .

Berikut adalah nama-nama kotaknya:

 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 mendefinisikan digit, baris, dan kolom sebagai string:

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

Anda akan melihat bahwa colsdiatur ke sama digits. Meskipun nilainya sama, namun mewakili hal-hal yang berbeda. The digitsvariabel mewakili angka yang masuk di alun-alun untuk memecahkan teka-teki. The colsvariabel mewakili nama-nama kolom dari grid.

Kotak juga didefinisikan sebagai string tetapi string dibuat dengan fungsi:

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)

Bagian kembalian dari crossfunction ( [a+b for a in A for b in B]) hanyalah cara yang bagus untuk menulis kode ini:

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

The squaresvariabel sekarang sama daftar semua nama-nama persegi.

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

Setiap kotak di grid memiliki 3 unit dan 20 peer. Satuan persegi adalah baris, kolom, dan kotak di mana kotak tersebut muncul. Semua bagian dari persegi adalah semua persegi lain dalam satuan tersebut. Misalnya, berikut adalah unit dan peers untuk persegi 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:

kita akan menggunakan heuristik umum yang disebut nilai sisa minimum, yang berarti bahwa kita memilih (atau salah satu) kuadrat dengan jumlah minimum nilai yang mungkin. Mengapa? Pertimbangkan grid2 di atas. Misalkan kita memilih B3 dulu. Ini memiliki 7 kemungkinan (1256789), jadi kami berharap salah menebak dengan probabilitas 6/7. Jika sebaliknya kita memilih G2, yang hanya memiliki 2 kemungkinan (89), kita berharap salah dengan probabilitas hanya 1/2. Jadi, kami memilih kotak dengan kemungkinan paling sedikit dan peluang terbaik untuk menebak dengan benar.

Digit dianggap dalam urutan numerik.

Berikut adalah searchfungsinya, bersama dengan solvefungsi yang mengurai grid dan panggilan awal 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