[PYTHON] Ich möchte SUDOKU lösen

Einführung

Als ich meinen Vater nach langer Zeit zu Hause traf, benutzte ich eine Smartphone-App, um Sudoku zu lösen. Wir werden es mit Google Colaboratory machen.

Was sind die Herausforderungen?

Wenn Sie mit "sudoku" googeln, scheint es eine Site wie diese zu geben. Ziel ist es daher, das Problem hier zu lösen. Wenn man sich "Schwierigkeit" ansieht, scheint es, dass es die folgenden 4 Stufen gibt.

• Easy
• Medium
• Hard
• Expert

Ich werde versuchen, jeweils eine Frage zu lösen.

Implementierung

Problem

Zum Beispiel, wenn das folgende Problem ...

Ich werde es wie folgt als zweidimensionale Liste ausdrücken. Dieses Problem ist übrigens ein Beispiel für leichte Schwierigkeiten.

sudoku.ipynb

# easy
list_sudoku = [
 [0, 4, 8, 0, 9, 0, 0, 5, 0],
 [0, 0, 0, 7, 4, 5, 2, 1, 0],
 [0, 7, 5, 0, 0, 2, 4, 0, 0],
 [0, 0, 0, 0, 7, 0, 0, 0, 2],
 [7, 0, 6, 4, 0, 9, 0, 0, 0],
 [9, 0, 2, 0, 6, 0, 3, 0, 0],
 [0, 0, 0, 6, 1, 0, 8, 2, 7],
 [0, 1, 3, 0, 5, 0, 6, 4, 9],
 [0, 0, 7, 9, 8, 0, 0, 0, 1]]

Funktion zum Eingrenzen von Kandidaten

In der oberen linken Zelle des obigen Problems wird beispielsweise entschieden, dass die Zahlen, die sich bereits in der Vertikalen, Horizontalen und im Block befinden, nicht enthalten sind, sodass die Kandidaten auf [1,2,3,6] eingegrenzt werden können. Deshalb. Erstellen Sie eine Funktion, die dies kann.

Lassen Sie uns zunächst eine Liste der Kandidaten 1 bis 9 als Variablen erstellen.

sudoku.ipynb

list_possible = [i for i in range(1, 10)]

Nun erstellen wir eine Funktion. Zunächst vertikal.

sudoku.ipynb

def narrow_ver(x, list_possible, list_sudoku):
  """
Grenzen Sie die Kandidaten in vertikaler Richtung ein
  """
  list_ver = [list_sudoku[i][x] for i in range(9) if type(list_sudoku[i][x]) is int]
  return set(list_possible) - set(list_ver)

Dann seitwärts.

sudoku.ipynb

def narrow_hor(y, list_possible, list_sudoku):
  """
Grenzen Sie die Kandidaten in horizontaler Richtung ein
  """
  list_hor = [list_sudoku[y][i] for i in range(9) if type(list_sudoku[y][i]) is int]
  return set(list_possible) - set(list_hor)

Und im Block.

sudoku.ipynb

def narrow_blo(x, y, list_possible, list_sudoku):
  """
Grenzen Sie die Kandidaten im Block ein
  """
  index_x = (x // 3) * 3
  index_y = (y // 3) * 3
  list_blo = [list_sudoku[i][j] for i in range(index_y, index_y+3) for j in range(index_x, index_x+3) if type(list_sudoku[i][j]) is int]
  return set(list_possible) - set(list_blo)

Erstellen Sie eine Funktion, die vertikal, horizontal und innerhalb eines Blocks aufruft ...

sudoku.ipynb

def narrow(x, y, list_possible, list_sudoku):
  """
Grenzen Sie die Kandidaten für die Zielzelle ein
  """
  list_possible = narrow_ver(x, list_possible, list_sudoku)
  list_possible = narrow_hor(y, list_possible, list_sudoku)
  list_possible = narrow_blo(x, y, list_possible, list_sudoku)
  return sorted(list(list_possible))

Erstellen Sie eine Funktion, die ↑ für alle Zellen ausführt. Zellen, für die die Nummer bereits festgelegt wurde, sind jedoch durch.

sudoku.ipynb

def apply_narrow(list_sudoku):
  """
Eng für alle Zellen()Laufen
  """
  for y in range(9):
    for x in range(9):
      if list_sudoku[y][x] != 0 and type(list_sudoku[y][x]) is int:
        continue
      elif list_sudoku[y][x] == 0:
        list_sudoku[y][x] = narrow(x, y, list_possible, list_sudoku)
      else:
        list_sudoku[y][x] = narrow(x, y, list_sudoku[y][x], list_sudoku)
        if len(list_sudoku[y][x]) == 1:
          list_sudoku[y][x] = list_sudoku[y][x][0]
  return list_sudoku

Vielleicht ist das alles, was Sie lösen müssen? Lass es uns versuchen!

Versuchen Sie einfach zu lösen

Kopieren Sie es nach temp_sudoku, vergleichen Sie es mit dem nach dem Ausführen von apply_narrow (), und wenn es keine Änderung gibt, wird es beendet.

sudoku.ipynb

import copy

list_possible = [i for i in range(1, 10)]
count = 0
temp_sudoku = []
while(True):
  temp_sudoku = copy.deepcopy(list_sudoku)
  count += 1
  list_sudoku = apply_narrow(list_sudoku)
  if temp_sudoku == list_sudoku:
    break
print(count)
list_sudoku

↓ Ausgabeergebnis

6
[[2, 4, 8, 1, 9, 6, 7, 5, 3],
 [3, 6, 9, 7, 4, 5, 2, 1, 8],
 [1, 7, 5, 8, 3, 2, 4, 9, 6],
 [4, 5, 1, 3, 7, 8, 9, 6, 2],
 [7, 3, 6, 4, 2, 9, 1, 8, 5],
 [9, 8, 2, 5, 6, 1, 3, 7, 4],
 [5, 9, 4, 6, 1, 3, 8, 2, 7],
 [8, 1, 3, 2, 5, 7, 6, 4, 9],
 [6, 2, 7, 9, 8, 4, 5, 3, 1]]

Du hast es gelöst! Ich habs gemacht!

Wie wäre es mit Medium?

sudoku.ipynb

# medium
list_sudoku = [
 [9, 0, 0, 8, 1, 0, 0, 0, 0],
 [0, 0, 5, 0, 0, 4, 7, 0, 6],
 [0, 0, 0, 2, 0, 5, 8, 0, 1],
 [0, 9, 0, 7, 4, 0, 5, 0, 0],
 [0, 0, 0, 0, 0, 3, 0, 7, 0],
 [7, 4, 0, 0, 0, 0, 0, 0, 0],
 [3, 0, 0, 9, 5, 0, 6, 0, 0],
 [0, 0, 6, 4, 0, 0, 0, 1, 3],
 [1, 7, 0, 0, 0, 0, 0, 0, 4]]

↓ Ergebnis

6
[[9, [3, 6], [2, 3, 7], 8, 1, [6, 7], [3, 4], [3, 4], 5],
 [8, 1, 5, 3, 9, 4, 7, 2, 6],
 [[4, 6], [3, 6], [3, 7], 2, [6, 7], 5, 8, [3, 4, 9], 1],
 [[2, 6], 9, [1, 2, 3, 8], 7, 4, [2, 6], 5, [3, 6], [2, 8]],
 [[2, 6], [5, 6], [1, 2, 8], [1, 5], [2, 6, 8], 3, [1, 4], 7, [2, 8, 9]],
 [7,
  4,
  [1, 2, 3, 8],
  [1, 5],
  [2, 6, 8],
  [2, 6, 9],
  [1, 3],
  [3, 6, 9],
  [2, 8, 9]],
 [3, 2, 4, 9, 5, 1, 6, 8, 7],
 [5, 8, 6, 4, [2, 7], [2, 7], 9, 1, 3],
 [1, 7, 9, 6, 3, 8, 2, 5, 4]]

Ist es nicht gut Die 2., 7. und 9. Zeile sind alle gelöst und die Zeilen sind ziemlich gut. Anscheinend reicht dies allein nicht aus, um die Kandidaten einzugrenzen.

Die folgende Tabelle zeigt dieses Ergebnis. Das Defizit ist ein Kandidat.

Nun, es ist so voll, dass es sich wie eine Verschnaufpause anfühlt, aber wie lösen Sie es? Wenn Sie versuchen, es selbst zu lösen ... Wenn es beispielsweise in der 1. Spalte und 3. Zeile "46" ist, gibt es keine andere Zelle im Block, die "4" als Kandidaten hat, sodass die Antwort "4" lautet.

Eine Funktion, die die Antwort findet, indem sie sie mit anderen Zellkandidaten vergleicht

Vergleichen Sie die Zellenkandidaten nach dem Eingrenzen mit den Zellenkandidaten in Vertikal, Horizontal und Block. Wenn sich ein Kandidat nicht in anderen Zellen befindet, erstellen Sie als Vergleich eine Funktion, die darauf antwortet.

Es verwendet itertools, also importieren wir es.

sudoku.ipynb

import itertools

Zuerst aus der vertikalen Zelle.

sudoku.ipynb

def generate_possible_ver(x, y, list_sudoku):
  """
Sammeln Sie Kandidatenzellen in vertikaler Richtung
  """
  list_ver = [list_sudoku[i][x] for i in range(9) if type(list_sudoku[i][x]) is list and i!=y]
  return set(itertools.chain.from_iterable(list_ver))

Dann seitwärts.

sudoku.ipynb

def generate_possible_hor(x, y, list_sudoku):
  """
Sammle Kandidaten für horizontale Zellen
  """
  list_hor = [list_sudoku[y][i] for i in range(9) if type(list_sudoku[y][i]) is list and i!=x]
  return set(itertools.chain.from_iterable(list_hor))

Und im Block.

sudoku.ipynb

def generate_possible_blo(x, y, list_sudoku):
  """
Sammeln Sie Kandidatenzellen im Block
  """
  index_x = (x // 3) * 3
  index_y = (y // 3) * 3
  list_blo = [list_sudoku[i][j] for i in range(index_y, index_y+3) for j in range(index_x, index_x+3) if type(list_sudoku[i][j]) is list and (i!=y or j!=x)]
  return set(itertools.chain.from_iterable(list_blo))

Erstellen Sie eine Funktion, die die Kandidaten vergleicht und sie der Zelle zuweist, wenn nur ein Kandidat vorhanden ist.

sudoku.ipynb

def find_only_one(x, y, list_possible, list_sudoku):
  """
Vergleichen Sie mit den Zellkandidaten in Vertikal, Horizontal und Block.
Wenn es einen Kandidaten gibt, der sich nicht in anderen Zellen befindet, beantworten Sie ihn
  """
  diff_ver = set(list_possible) - generate_possible_ver(x, y, list_sudoku)
  if len(diff_ver) == 1:
    return list(diff_ver)[0]
  
  diff_hor = set(list_possible) - generate_possible_hor(x, y, list_sudoku)
  if len(diff_hor) == 1:
    return list(diff_hor)[0]

  diff_blo = set(list_possible) - generate_possible_blo(x, y, list_sudoku)
  if len(diff_blo) == 1:
    return list(diff_blo)[0]
  
  return list_possible

Erstellen Sie eine Funktion, die ↑ für alle Zellen ausführt. Natürlich ist derjenige, der bereits die Antwort hat, durch.

sudoku.ipynb

def try_solve(list_sudoku):
  """
Für Zellen, für die die Antwort noch nicht ermittelt wurde
  narrow()Und finde_only_one()Laufen
  """
  for y in range(9):
    for x in range(9):
      if list_sudoku[y][x] != 0 and type(list_sudoku[y][x]) is int:
        continue
      else:
        list_sudoku[y][x] = narrow(x, y, list_sudoku[y][x], list_sudoku)
        list_sudoku[y][x] = find_only_one(x, y, list_sudoku[y][x], list_sudoku)
        if type(list_sudoku[y][x]) is list and len(list_sudoku[y][x]) == 1:
          list_sudoku[y][x] = list_sudoku[y][x][0]
  return list_sudoku

Lass es uns jetzt versuchen!

Versuchen Sie, Medium zu lösen

Auch diesmal endet es, wenn sich im Vergleich zu temp_sudoku nichts ändert.

sudoku.ipynb

import copy

list_possible = [i for i in range(1, 10)]
count = 0
temp_sudoku = []
while(True):
  temp_sudoku = copy.deepcopy(list_sudoku)
  count += 1
  list_sudoku = try_solve(apply_narrow(list_sudoku))
  if temp_sudoku == list_sudoku:
    break
print(count)
list_sudoku

↓ Ausgabeergebnis

4
[[9, 6, 2, 8, 1, 7, 3, 4, 5],
 [8, 1, 5, 3, 9, 4, 7, 2, 6],
 [4, 3, 7, 2, 6, 5, 8, 9, 1],
 [2, 9, 1, 7, 4, 6, 5, 3, 8],
 [6, 5, 8, 1, 2, 3, 4, 7, 9],
 [7, 4, 3, 5, 8, 9, 1, 6, 2],
 [3, 2, 4, 9, 5, 1, 6, 8, 7],
 [5, 8, 6, 4, 7, 2, 9, 1, 3],
 [1, 7, 9, 6, 3, 8, 2, 5, 4]]

Hört sich gut an. Lassen Sie uns mit dieser Bedingung hart gehen.

Versuche hart zu lösen

sudoku.ipynb

# hard
list_sudoku = [
 [1, 3, 0, 6, 0, 0, 0, 8, 0],
 [0, 4, 6, 0, 3, 0, 0, 0, 0],
 [0, 2, 0, 5, 0, 0, 0, 0, 0],
 [0, 0, 0, 2, 0, 0, 1, 0, 6],
 [0, 9, 0, 0, 5, 7, 0, 0, 0],
 [8, 0, 0, 0, 0, 0, 0, 4, 5],
 [0, 0, 0, 0, 0, 0, 3, 7, 0],
 [0, 0, 0, 0, 6, 3, 4, 0, 0],
 [0, 0, 0, 0, 0, 0, 5, 0, 1]]

↓ Ergebnis

4
[[1, 3, 5, 6, 7, 2, 9, 8, 4],
 [9, 4, 6, 8, 3, 1, 2, 5, 7],
 [7, 2, 8, 5, 4, 9, 6, 1, 3],
 [3, 5, 7, 2, 8, 4, 1, 9, 6],
 [6, 9, 4, 1, 5, 7, 8, 3, 2],
 [8, 1, 2, 3, 9, 6, 7, 4, 5],
 [2, 6, 9, 4, 1, 5, 3, 7, 8],
 [5, 8, 1, 7, 6, 3, 4, 2, 9],
 [4, 7, 3, 9, 2, 8, 5, 6, 1]]

Sie sind fertig! Vielleicht können alle Deutschen auf dieser Welt mit dieser Logik gelöst werden? Versuchen wir es auch mit Expert!

sudoku.ipynb

# expert
list_sudoku = [
 [4, 0, 0, 0, 8, 0, 1, 0, 0],
 [0, 0, 0, 2, 0, 9, 0, 0, 0],
 [0, 0, 0, 7, 3, 0, 0, 0, 0],
 [0, 2, 0, 0, 0, 1, 0, 0, 9],
 [0, 0, 5, 0, 0, 0, 0, 7, 0],
 [0, 9, 0, 0, 0, 0, 0, 5, 0],
 [0, 1, 0, 5, 0, 0, 4, 0, 0],
 [6, 0, 0, 3, 0, 0, 0, 0, 0],
 [0, 0, 4, 0, 0, 7, 6, 0, 3]]

↓ Ergebnis

3
[[4, [3, 7], [2, 3, 7, 9], 6, 8, 5, 1, [2, 3, 9], [2, 7]],
 [[3, 5, 7, 8],
  [3, 5, 6, 7, 8],
  [3, 6, 7, 8],
  2,
  1,
  9,
  [3, 5, 7, 8],
  [3, 4, 6, 8],
  [4, 5, 6, 7, 8]],
 [[1, 2, 5, 8, 9],
  [5, 6, 8],
  [1, 2, 6, 8, 9],
  7,
  3,
  4,
  [2, 5, 8, 9],
  [2, 6, 8, 9],
  [2, 5, 6, 8]],
 [[3, 7, 8], 2, [3, 6, 7, 8], [4, 8], 5, 1, [3, 8], [3, 4, 6, 8], 9],
 [[1, 3, 8], 4, 5, 9, [2, 6], [2, 3, 6, 8], [2, 3, 8], 7, [1, 2, 6, 8]],
 [[1, 3, 8],
  9,
  [1, 3, 6, 8],
  [4, 8],
  7,
  [2, 3, 6, 8],
  [2, 3, 8],
  5,
  [1, 2, 4, 6, 8]],
 [[2, 3, 7, 8, 9],
  1,
  [2, 3, 7, 8, 9],
  5,
  [2, 6, 9],
  [2, 6, 8],
  4,
  [2, 8, 9],
  [2, 7, 8]],
 [6, [5, 7, 8], [2, 7, 8, 9], 3, 4, [2, 8], [2, 5, 7, 8, 9], 1, [2, 5, 7, 8]],
 [[2, 5, 8, 9], [5, 8], 4, 1, [2, 9], 7, 6, [2, 8, 9], 3]]

Ja. Es hat überhaupt nicht funktioniert. Ist es so in einer Tabelle?

Wie erwartet ist es ein Expertenlevel. Ich kann es überhaupt nicht lösen. Um die Sache noch schlimmer zu machen, habe ich nicht das Gefühl, dass ich es selbst lösen kann. Was nun?

Eine Funktion, die per Round-Robin gelöst werden muss

Ich kann nicht anders, also werde ich alle der Reihe nach ausprobieren. Es scheint, dass es rekursiv gemacht werden kann.

Zunächst die Funktion zur Überprüfung von Duplikaten. Sie können es per Round-Robin lösen, müssen aber keine Zahlen ausprobieren, von denen Sie bereits wissen, dass sie nicht passen.

sudoku.ipynb

def dup_check(x, y, possible, list_sudoku):
  """
In den Zellen in der Vertikalen, Horizontalen und Block
Überprüfen Sie, ob bereits doppelte Werte vorhanden sind
  """
  for pos in range(9):
    if list_sudoku[y][pos] == possible or list_sudoku[pos][x] == possible:
      return False
  
  index_x = (x // 3) * 3
  index_y = (y // 3) * 3
  for pos_y in range(index_y, index_y+3):
    for pos_x in range(index_x, index_x+3):
      if list_sudoku[pos_y][pos_x] == possible:
        return False
  return True

Und eine Funktion, die im Kreisverkehr zu lösen ist. Wenn ein unlösbares Problem vorliegt, gibt es eine Endlosschleife. Daher haben wir ein Zeitlimit (60 Sekunden) festgelegt. Die Anzahl der Sekunden ist angemessen.

sudoku.ipynb

def brute_force(list_sudoku, list_ans, x=0, y=0):
  """
Versuchen Sie, im Kreisverkehr zu lösen
Wenn es länger als 60 Sekunden dauert, wird beurteilt, dass es nicht gelöst werden kann
  """
  if type(list_sudoku[y][x]) is list:
    time_process = time.time()
    if (time_process - time_start) >= 60:
      return False
    for possible in list_sudoku[y][x]:
      if dup_check(x, y, possible, list_ans):
        list_ans[y][x] = possible
        if x <= 7:
          next_x = x + 1
          next_y = y
        elif y <= 7:
          next_x = 0
          next_y = y + 1
        else:
          return True
        if not brute_force(list_sudoku, list_ans, next_x, next_y):
          continue
        else:
          return True
    list_ans[y][x] = []
    return False
  else:
    list_ans[y][x] = list_sudoku[y][x]
    if x <= 7:
      next_x = x + 1
      next_y = y
    elif y <= 7:
      next_x = 0
      next_y = y + 1
    else:
      return True
    return brute_force(list_sudoku, list_ans, next_x, next_y)

Versuchen Sie, Expert zu lösen

Wie wäre es mit?

sudoku.ipynb

import copy
import time

time_start = time.time()
temp_sudoku = copy.deepcopy(list_sudoku)
list_ans = [[[] for i in range(9)] for j in range(9)]
result = brute_force(temp_sudoku, list_ans)
print(result)
list_ans

↓ Ausgabeergebnis

True
[[4, 7, 9, 6, 8, 5, 1, 3, 2],
 [5, 3, 8, 2, 1, 9, 7, 6, 4],
 [1, 6, 2, 7, 3, 4, 5, 9, 8],
 [7, 2, 6, 8, 5, 1, 3, 4, 9],
 [3, 4, 5, 9, 2, 6, 8, 7, 1],
 [8, 9, 1, 4, 7, 3, 2, 5, 6],
 [9, 1, 3, 5, 6, 8, 4, 2, 7],
 [6, 8, 7, 3, 4, 2, 9, 1, 5],
 [2, 5, 4, 1, 9, 7, 6, 8, 3]]

Gelöst! Ich habs gemacht!

Schließlich

Ich wollte es mit einer anderen Logik als Round-Robin lösen, aber ich konnte es nicht normal lösen, also konnte ich es nicht implementieren. Wenn Sie nach "Wie man ein paar Deutsche löst, Fortgeschrittene" usw. suchen, werden Sie verschiedene Dinge finden, aber Sie können es nicht lösen, selbst wenn Sie sich auf eines von ihnen beziehen. .. Ich möchte wenn möglich etwas dagegen tun.

Referenz

Informationen zum Round-Robin finden Sie im Folgenden. ・ Mathematik mit Python lösen

Apropos

Ich schaltete den Bildschirm ein, damit ich es versuchen konnte. SUDOKU SOLVER