Πώς να παίξετε και να κερδίσετε Sudoku - Χρησιμοποιώντας μαθηματικά και μηχανική εκμάθηση για να λύσετε κάθε παζλ Sudoku

Το Sudoku (και οι προκάτοχοί του) παίζεται για πάνω από εκατό χρόνια. Όταν βγήκε για πρώτη φορά, οι άνθρωποι έπρεπε να λύσουν τα παζλ χρησιμοποιώντας μόνο το μυαλό τους. Τώρα έχουμε υπολογιστές! (Εντάξει, έτσι οι περισσότεροι άνθρωποι εξακολουθούν να χρησιμοποιούν το μυαλό τους ...)

Σε αυτό το άρθρο, θα μάθετε πώς να παίζετε και να κερδίζετε Sudoku. Αλλά το πιο σημαντικό, θα μάθετε πώς να χρησιμοποιείτε τη μηχανική εκμάθηση για να λύσετε εύκολα κάθε παζλ Sudoku. Ποιος χρειάζεται να σκεφτεί πότε μπορείτε να αφήσετε τον υπολογιστή να σκεφτεί για εσάς. ;

Ο Peter Norvig ανέπτυξε ένα κομψό πρόγραμμα χρησιμοποιώντας το Python για να κερδίσει το sudoku χρησιμοποιώντας περιορισμό διάδοσης και αναζήτησης. Η λύση του Norvig θεωρείται κλασική και αναφέρεται συχνά όταν οι άνθρωποι αναπτύσσουν τον δικό τους κώδικα για να παίξουν το Sudoku. Αφού αναθεωρήσω το Sudoku και ορισμένες στρατηγικές, θα αναλύσω τον κώδικα του Norvig βήμα προς βήμα, ώστε να καταλάβετε πώς λειτουργεί.

Τι είναι το Sudoku;

Το Sudoku είναι ένα παζλ τοποθέτησης αριθμών και υπάρχουν μερικοί διαφορετικοί τύποι. Αυτό το άρθρο αφορά τον πιο δημοφιλή τύπο.

Ο στόχος είναι να γεμίσετε ένα πλέγμα 9x9 με ψηφία (1-9) έτσι ώστε κάθε στήλη, σειρά και καθένα από τα εννέα υποπλέγματα 3x3 (που ονομάζονται επίσης κουτιά) όλα να περιέχουν καθένα από τα ψηφία από το 1 έως το 9. Τα παζλ ξεκινούν με μερικά αριθμούς ήδη στο πλέγμα και εναπόκειται σε εσάς να συμπληρώσετε τους άλλους αριθμούς.

Στην παρακάτω εικόνα από ένα παιχνίδι Sudoku, ο αριθμός που πρέπει να πάει στο μπλε επισημασμένο τετράγωνο δεν μπορεί να είναι σε κανένα από τα κίτρινα τετράγωνα που αντιστοιχούν στη στήλη, τη σειρά και το πλαίσιο 3x3.

Πώς να λύσετε το Sudoku

Κατά την επίλυση ενός παζλ Sudoku, θα πρέπει να κάνετε συνεχώς δύο πράγματα. Το πρώτο πράγμα που πρέπει να κάνετε είναι να εξαλείψετε αριθμούς από σειρές, στήλες και πλαίσια (3x3 υποπλέγματα). Το δεύτερο πράγμα που πρέπει να κάνετε είναι να αναζητήσετε έναν μόνο υποψήφιο.

Στο παρακάτω παράδειγμα, οι πιθανοί αριθμοί για κάθε τετράγωνο σημειώνονται με μικρότερη γραμματοσειρά. Οι πιθανοί αριθμοί καθορίστηκαν με την εξάλειψη όλων των ψηφίων που εμφανίζονται στην ίδια στήλη, σειρά ή πλαίσιο. Τα περισσότερα άτομα θα καθορίσουν τον πιθανό αριθμό για ένα κουτί κάθε φορά, αντί για το πλήρες πλέγμα.

Αφού καταργήσετε τους αριθμούς, μπορείτε να αναζητήσετε μεμονωμένους υποψηφίους. Αυτό σημαίνει να βρείτε ένα τετράγωνο που μπορεί να είναι μόνο ένας πιθανός αριθμός. Στο παρακάτω παράδειγμα, τα δύο κίτρινα επισημασμένα τετράγωνα πρέπει να περιέχουν 1 και 8, επειδή όλα τα άλλα ψηφία έχουν εξαλειφθεί, καθώς εμφανίζονται ήδη στη στήλη, τη σειρά ή το πλαίσιο του τετραγώνου.

Τώρα που είναι γνωστά τα δύο τετράγωνα που επισημαίνονται με κίτρινο χρώμα, αυτό εξαλείφει περισσότερες πιθανότητες από άλλα τετράγωνα. Τώρα γνωρίζετε ότι το τετράγωνο που επισημαίνεται με μπλε χρώμα πρέπει να είναι 7.

Εάν συνεχίζετε να βρίσκετε τους μεμονωμένους υποψηφίους και στη συνέχεια να εξαλείψετε τις επιλογές από άλλα τετράγωνα, ενδέχεται τελικά να φτάσετε στο σημείο όπου δεν υπάρχουν πλέον μεμονωμένοι υποψήφιοι.

Σε αυτό το σημείο μπορείτε να αναζητήσετε πιθανές λύσεις σε τετράγωνα όπου ο αριθμός είναι μόνο σε ένα τετράγωνο σε πλαίσιο, σειρά ή στήλη. Στο παρακάτω παράδειγμα μπορούμε να προσδιορίσουμε ότι η λύση στο τετράγωνο που επισημαίνεται με μπλε χρώμα πρέπει να είναι 6 αφού ο αριθμός 6 δεν εμφανίζεται σε κανένα άλλο τετράγωνο στο κίτρινο κουτί.

Μερικές φορές ο πίνακας θα φτάσει σε μια κατάσταση όπου φαίνεται ότι κάθε άλυτο τετράγωνο θα μπορούσε ενδεχομένως να είναι πολλαπλές τιμές. Αυτό σημαίνει ότι υπάρχουν πολλές διαδρομές που θα μπορούσατε να επιλέξετε και δεν είναι προφανές ποια διαδρομή θα οδηγήσει στην επίλυση του παζλ.

Σε αυτό το σημείο είναι απαραίτητο να δοκιμάσετε κάθε επιλογή. Επιλέξτε ένα και συνεχίστε να λύνετε μέχρι να καταστεί σαφές ότι η επιλογή που επιλέξατε δεν μπορεί να είναι λύση. Στη συνέχεια θα πρέπει να ακολουθήσετε και να δοκιμάσετε μια άλλη επιλογή.

Αυτός ο τύπος αναζήτησης μπορεί εύκολα να γίνει με έναν υπολογιστή χρησιμοποιώντας ένα δυαδικό δέντρο αναζήτησης. Όταν υπάρχει η επιλογή δύο διαφορετικών αριθμών για την επίλυση ενός τετραγώνου, είναι απαραίτητο να ξεχωρίσετε σε δύο διαφορετικές πιθανότητες. Ένα δέντρο δυαδικής αναζήτησης θα επιτρέψει σε έναν αλγόριθμο να κατεβεί έναν κλάδο επιλογών και, στη συνέχεια, να δοκιμάσει μια διαφορετική επιλογή.

Τώρα πρόκειται να δούμε κώδικα Python που μπορεί να λύσει παζλ Sudoku χρησιμοποιώντας μια παρόμοια μέθοδο με αυτήν που μόλις περιγράφηκε.

Το πρόγραμμα του Peter Norvig για να κερδίσει το Sudoku

Ο Peter Norvig εξήγησε την προσέγγισή του στην επίλυση του Sudoku και τον κώδικα που χρησιμοποίησε στο άρθρο του Solving Every Sudoku Puzzle.

Κάποιοι μπορεί να βρουν την εξήγησή του λίγο δύσκολο να ακολουθηθεί, ειδικά αρχάριους. Θα αναλύσω τα πράγματα, ώστε να είναι πιο εύκολο να καταλάβουμε πώς λειτουργεί ο κώδικας του Norvig.

Σε αυτό το άρθρο, ο κωδικός Python 2 του Norvig έχει ενημερωθεί σε Python 3. (Μετατροπή Python 3 από Naoki Shibuya.) Θα περάσω από τον κώδικα μερικές γραμμές κάθε φορά, αλλά μπορείτε να δείτε τον πλήρη κώδικα στο τέλος αυτού του άρθρου . Για ορισμένα άτομα, μπορεί να είναι χρήσιμο να κοιτάξετε τον πλήρη κώδικα πριν διαβάσετε.

Πρώτον, θα καλύψουμε τη βασική ρύθμιση και τη σημειογραφία. Δείτε πώς ο Norvig περιγράφει τη βασική σημειογραφία που χρησιμοποιεί στον κώδικά του:

Ένα παζλ Sudoku είναι ένα πλέγμα 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

You will notice that cols is set to equal digits. While they are the same value, the represent different things. The digits variable represents the digits that go in a square to solve the puzzle. The cols variable represents the names of the columns of the grid.

The squares are also defined as strings but the strings are created with a function:

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)

The return part of the cross function ( [a+b for a in A for b in B]) is just a fancy way of writing this code:

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

The squares variable now equals a list of all the square names.

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

Each square in the grid has 3 units and 20 peers. The units of a square are the row, column, and box that it appears in. The peers of a square are all the other squares in the units. For example, here are the units and peers for the square 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:

θα χρησιμοποιήσουμε μια κοινή ευρετική που ονομάζεται ελάχιστες υπόλοιπες τιμές, που σημαίνει ότι επιλέγουμε το τετράγωνο (ή ένα από τα) με τον ελάχιστο αριθμό πιθανών τιμών. Γιατί; Εξετάστε το πλέγμα2 παραπάνω. Ας υποθέσουμε ότι επιλέξαμε πρώτα το 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])

Σύμφωνα με τους κανόνες του Sudoku, το παζλ επιλύεται όταν κάθε τετράγωνο έχει μόνο μία τιμή. Η searchσυνάρτηση καλείται αναδρομικά μέχρι να λυθεί το παζλ. valuesαντιγράφεται για να αποφευχθεί η πολυπλοκότητα.

Εδώ είναι η someσυνάρτηση που χρησιμοποιείται για να ελέγξετε εάν μια προσπάθεια επιτυγχάνει να λύσει το παζλ.

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

Αυτός ο κωδικός θα λύσει τώρα κάθε παζλ Sudoku. Μπορείτε να δείτε τον πλήρη κώδικα παρακάτω.

Πλήρης κωδικός επίλυσης Sudoku

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