Der vollständige Implementierungsprozess von Sudoku mit JavaScript

Inhaltsverzeichnis

Vorwort
So lösen Sie Sudoku

Füllen Sie das erste Feld aus
Füllen Sie das zweite Feld aus
Füllen Sie das dritte Feld aus
Füllen Sie das neunte Feld aus
Zusammenfassend

Implementierung durch Code

Dynamische Darstellung des Testverlaufs

Neun-Raster-Stil
Fragenlogik

Zusammenfassen

Vorwort

Vor kurzem sah ich, wie meine Frau jeden Tag Sudoku auf ihrem Mobiltelefon spielte. Plötzlich fiel mir ein, dass es vor N Jahren, als ich LeetCode spielte, ein ähnliches Algorithmusproblem gab (37. Sudoku lösen). Ist es möglich, diesen Algorithmus zu visualisieren?

Tun Sie es einfach, nach einer Stunde Übung ist der Endeffekt wie folgt:

So lösen Sie Sudoku

Bevor wir Sudoku lösen, wollen wir zunächst die Sudoku-Regeln verstehen:

Die Zahlen 1-9 dürfen in jeder Zeile nur einmal vorkommen.
Die Zahlen 1-9 dürfen in jeder Spalte nur einmal vorkommen.
Die Zahlen 1-9 dürfen in jedem der durch dicke durchgezogene Linien getrennten 3x3-Raster nur einmal vorkommen.

Als nächstes müssen wir in jedes Kästchen eine Zahl eintragen und dann feststellen, ob diese Zahl gegen die Regeln verstößt.

Füllen Sie das erste Feld aus

Tragen Sie zunächst 1 in das erste Raster ein. Sie werden feststellen, dass in der ersten Spalte bereits eine 1 steht. Zu diesem Zeitpunkt müssen Sie die zuvor eingetragene Zahl 1 löschen und dann 2 in das Raster eintragen. Sie werden feststellen, dass die Zahlen in den Zeilen, Spalten und Neunerrastern nicht wiederholt werden. Dann ist das Raster erfolgreich gefüllt.

Füllen Sie das zweite Feld aus

Schauen wir uns das zweite Raster an. Versuchen Sie wie zuvor, zuerst 1 auszufüllen. Wenn Sie feststellen, dass sich in den Zeilen, Spalten und im Raster keine Zahlen wiederholen, wurde auch dieses Raster erfolgreich ausgefüllt.

Füllen Sie das dritte Feld aus

Schauen wir uns nun das dritte Kästchen an. Da wir die ersten beiden Kästchen bereits mit den Zahlen 1 und 2 ausgefüllt haben, können wir direkt mit dem Ausfüllen von Zahl 3 beginnen. Nachdem ich 3 eingetragen hatte, stellte ich fest, dass in der ersten Reihe bereits eine 3 stand. Dann trug ich 4 in das Gitter ein und stellte fest, dass die Zahl 4 sowohl in der Reihe als auch im Gitter wiederholt wurde. Es war immer noch erfolglos. Dann versuchte ich, die Zahl 5 einzutragen. Schließlich gab es keine wiederholten Zahlen, was darauf hindeutete, dass das Ausfüllen erfolgreich war.

…

Weiter ausfüllen...

Füllen Sie das neunte Feld aus

Füllen Sie gemäß diesem Prinzip bis zum neunten Quadrat aus. An dieser Stelle werden Sie feststellen, dass die letzte Zahl 9 im Neunerraster einen Konflikt darstellt. Da 9 jedoch bereits die letzte Zahl ist, gibt es hier keine Möglichkeit, andere Zahlen einzutragen. Ich kann nur zum vorherigen Raster zurückkehren und die Zahl im siebten Raster von 8 auf 9 ändern, habe jedoch festgestellt, dass im Neunerraster immer noch ein Konflikt besteht.

Zu diesem Zeitpunkt müssen Sie die Zahl im vorherigen Raster (dem sechsten Raster) ersetzen. Solange, bis es keine Konflikte mehr gibt. Bei diesem Vorgang müssen Sie also nicht nur die Zahlen rückwärts eintragen, sondern auch zurückschauen, um zu sehen, ob es Probleme mit den vorherigen Zahlen gibt, und es dann weiter versuchen.

Zusammenfassend

Das Lösen von Sudoku ist ein Prozess des ständigen Ausprobierens. Versuchen Sie die Zahlen 1-9 in jedem Raster. Wenn es einen Konflikt gibt, löschen Sie die Zahl, bis alle Raster ausgefüllt sind.

Durch Code implementiert

Um die obige Lösung im Code widerzuspiegeln, müssen wir sie durch Rekursion + Backtracking implementieren.

Bevor wir den Code schreiben, schauen wir uns an, wie man Sudoku darstellt. Hier ist ein Verweis auf die Frage zu LeetCode: 37. Sudoku lösen.

Die vorherige Frage kann durch ein zweidimensionales Array dargestellt werden. Das äußerste Array enthält 9 Arrays, die die 9 Zeilen von Sudoku darstellen. Die 9 Zeichen in jedem inneren Array entsprechen den Spalten des Arrays, und die nicht ausgefüllten Leerzeichen werden durch Zeichen ('.') dargestellt.

const sudoku = [
  ['.', '.', '.', '4', '.', '.', '.', '3', '.'],
  ['7', '.', '4', '8', '.', '.', '1', '.', '2'],
  ['.', '.', '.', '2', '3', '.', '4', '.', '9'],
  ['.', '4', '.', '5', '.', '9', '.', '8', '.'],
  ['5', '.', '.', '.', '.', '.', '9', '1', '3'],
  ['1', '.', '.', '.', '8', '.', '2', '.', '4'],
  ['.', '.', '.', '.', '.', '.', '3', '4', '5'],
  ['.', '5', '1', '9', '4', '.', '7', '2', '.'],
  ['4', '7', '3', '.', '5', '.', '.', '9', '1'],
]

Nachdem wir nun wissen, wie Arrays dargestellt werden, schreiben wir Code.

const sudoku = [……]
// Die Methode akzeptiert zwei Parameter, Zeile und Spalte, um das Raster der Sudoku-Funktion zu lokalisieren. solve(row, col) {
  wenn (Spalte >= 9) { 
   // Jenseits der neunten Spalte bedeutet dies, dass diese Zeile beendet ist und eine neue Zeile begonnen werden muss col = 0
    Zeile += 1
    wenn (Zeile >= 9) {
      // Wenn nach dem Starten einer neuen Zeile die neunte Zeile überschritten wird, ist das gesamte Sudoku abgeschlossen und es wird true zurückgegeben.
    }
  }
  wenn (Sudoku[Zeile][Spalte] !== '.') {
    // Wenn das Raster ausgefüllt wurde, fülle das nächste Raster aus. return solve(row, col + 1)
  }
  // Versuchen Sie, die Zahlen 1-9 in das Raster einzutragen
  für (let num = 1; num <= 9; num++) {
    if (!isValid(Zeile, Spalte, Num)) {
      // Wenn es eine ungültige Nummer ist, überspringen Sie die Nummer weiter
    }
    // Zahlen eintragen sudoku[row][col] = num.toString()
    // Fahren Sie mit dem Ausfüllen der folgenden Gitter fort if (solve(row, col + 1)) {
      // Wenn bis zum Ende alles in Ordnung ist, dann ist die Zahl in diesem Raster in Ordnung. returniere true
    }
    //Wenn ein Problem vorliegt, gibt „solve“ „false“ zurück.
    // Zeigt an, dass dieser Platz nachgefüllt werden muss sudoku[row][col] = '.' // Lösche die Zahl }
  // Die Zahlen 1-9 konnten alle nicht ausgefüllt werden, was darauf hinweist, dass es ein Problem mit den vorherigen Zahlen gibt. // Gib FALSE zurück, gehe zurück und fülle die vorherigen Zahlen erneut aus. return false
}

Der obige Code implementiert nur die Rekursions- und Backtracking-Teile, und es gibt eine isValid-Methode, die nicht implementiert wurde. Bei dieser Methode wird im Wesentlichen eine Verifizierung nach den Regeln des Sudoku durchgeführt.

const sudoku = [……]
Funktion istgültig(Zeile, Spalte, Zahl) {
  //Überprüfen Sie, ob die Zeile wiederholt wird für (let i = 0; i < 9; i++) {
    wenn (Sudoku[Zeile][i] === Zahl) {
      return false
    }
  }
  //Überprüfen, ob in der Spalte for (let i = 0; i < 9; i++) { ein Duplikat vorhanden ist.
    wenn (sudoku[i][col] === num) {
      return false
    }
  }
  // Bestimmen Sie, ob das Neunerraster wiederholt wird const startRow = parseInt(row / 3) * 3
  const startCol = parseInt(col / 3) * 3
  für (lass i = startRow; i < startRow + 3; i++) {
    für (let j = startCol; j < startCol + 3; j++) {
      wenn (Sudoku[i][j] === Zahl) {
        return false
      }
    }
  }
  returniere wahr
}

Mit dem obigen Code können wir ein Sudoku lösen.

const sudoku = [
  ['.', '.', '.', '4', '.', '.', '.', '3', '.'],
  ['7', '.', '4', '8', '.', '.', '1', '.', '2'],
  ['.', '.', '.', '2', '3', '.', '4', '.', '9'],
  ['.', '4', '.', '5', '.', '9', '.', '8', '.'],
  ['5', '.', '.', '.', '.', '.', '9', '1', '3'],
  ['1', '.', '.', '.', '8', '.', '2', '.', '4'],
  ['.', '.', '.', '.', '.', '.', '3', '4', '5'],
  ['.', '5', '1', '9', '4', '.', '7', '2', '.'],
  ['4', '7', '3', '.', '5', '.', '.', '9', '1']
]
Funktion ist gültig (Zeile, Spalte, Nummer) {……}
Funktion lösen(Zeile, Spalte) {……}
solve(0, 0) // Löse vom ersten Raster aus console.log(sudoku) // Gib das Ergebnis aus

Dynamische Darstellung des Testverlaufs

Mit dem oben genannten theoretischen Wissen können wir den Problemlösungsprozess anwenden, um zu reagieren und den Problemlösungsprozess dynamisch anzuzeigen. Dies ist das GIF am Anfang des Artikels.

Hier verwenden wir das Create-React-App-Scaffolding, um schnell ein Projekt zu starten

npx Erstellen-Reagieren-App Sudoku
CD-Sudoku

Öffnen Sie App.jsx und beginnen Sie mit dem Schreiben des Codes.

importiere React von „react“;
importiere './App.css';

Klasse App erweitert React.Component {
  Zustand = {
    // Konfigurieren Sie ein zweidimensionales Sudoku-Array im Status Sudoku: [
      ['.', '.', '.', '4', '.', '.', '.', '3', '.'],
      ['7', '.', '4', '8', '.', '.', '1', '.', '2'],
      ['.', '.', '.', '2', '3', '.', '4', '.', '9'],
      ['.', '4', '.', '5', '.', '9', '.', '8', '.'],
      ['5', '.', '.', '.', '.', '.', '9', '1', '3'],
      ['1', '.', '.', '.', '8', '.', '2', '.', '4'],
      ['.', '.', '.', '.', '.', '.', '3', '4', '5'],
      ['.', '5', '1', '9', '4', '.', '7', '2', '.'],
      ['4', '7', '3', '.', '5', '.', '.', '9', '1']
    ]
  }

 // TODO: Sudoku lösensolveSudoku = async () => {
    const { sudoku } = dieser.Zustand
  }

  rendern() {
    const { sudoku } = dieser.Zustand
    zurückkehren (
      <div Klassenname="Container">
        <div Klassenname="Wrapper">
          {/* Durchlaufe das zweidimensionale Array und erzeuge ein Raster mit neun Quadraten*/}
          {sudoku.map((Liste, Zeile) => (
            {/* div.row entspricht der Zeile von Sudoku*/}
            <div Klassenname = "Zeile" Schlüssel = {`Zeile-${Zeile}`}>
              {list.map((Element, Spalte) => (
              {/* Spanne entspricht jedem Sudoku-Gitter */}
                <span key={`box-${col}`}>{ Element !== '.' && Element }</span>
              ))}
            </div>
          ))}
          <button onClick={this.solveSudoku}>Beginnen Sie mit der Lösung des Problems</button>
        </div>
      </div>
    );
  }
}

Neun-Raster-Stil

Fügen Sie jedem Raster einen gepunkteten Rand hinzu, damit es wie ein Neunerraster aussieht.

.Reihe {
  Anzeige: Flex;
  Richtung: Reihe;
  /* Zentrieren Sie die Elemente in der Zeile */
  Inhalt ausrichten: zentriert;
  Inhalt ausrichten: zentriert;
}
.Zeilenspanne {
  /*Jedes Gitter hat die gleiche Breite und Höhe*/
  Breite: 30px;
  Mindesthöhe: 30px;
  Zeilenhöhe: 30px;
  Textausrichtung: zentriert;
  /* Gepunkteten Rahmen setzen */
  Rand: 1px gestrichelt #999;
}

Sie können ein Diagramm wie das folgende erhalten:

Als nächstes müssen Sie dem äußeren Rand und jedem Neun-Quadrat-Raster eine durchgezogene Linie hinzufügen. Der spezifische Code lautet wie folgt:

/* Füge oben in Zeile 1 einen Rahmen hinzu*/
.row:nth-child(1) span {
  Rahmen oben: 3px durchgezogen #333;
}
/* Rahmen am unteren Rand der Zeilen 3, 6 und 9 hinzufügen*/
.row:n-tes-Kind(3n) span {
  Rahmen unten: 3px durchgezogen #333;
}
/* Fügen Sie links von der ersten Spalte einen Rahmen hinzu*/
.row span:erstes-Kind {
  Rahmen links: 3px durchgezogen #333;
}

/* Rahmen rechts neben den Spalten 3, 6 und 9 hinzufügen*/
.row span:n-tes-Kind(3n) {
  Rahmen rechts: 3px durchgezogen #333;
}

Hier werden Sie feststellen, dass sich der rechte Rand der dritten und sechsten Spalte und der linke Rand der vierten und siebten Spalte ein wenig überlappen. Der untere Rand der dritten und sechsten Zeile und der obere Rand der vierten und siebten Zeile haben ebenfalls dieses Problem. Daher müssen wir auch den linken Rand der vierten und siebten Spalte und den unteren Rand der dritten und sechsten Zeile ausblenden.

.row:n-tes-Kind(3n + 1) span {
  oberer Rand: keiner;
}
.row span:n-tes-Kind(3n + 1) {
  Rand links: keiner;
}

Fragenlogik

Nachdem der Stil geschrieben ist, können Sie die Logik der Beantwortung der Fragen weiter verbessern.

Klasse App erweitert React.Component {
  Zustand = {
    // Konfigurieren Sie ein zweidimensionales Sudoku-Array im Status Sudoku: [...]
  }

  löseSudoku = async () => {
    const { sudoku } = dieser.Zustand
    //Überprüfen Sie, ob die eingegebene Nummer gültig ist. Siehe den obigen Code und wird hier nicht wiederholt const isValid = (row, col, num) => {
      …
    }
    // Lösen Sie das Problem durch Rekursion + Backtracking const solve = async (row, col) => {
      wenn (Spalte >= 9) { 
        Spalte = 0
        Zeile += 1
        wenn (Zeile >= 9) true zurückgeben
      }
      wenn (Sudoku[Zeile][Spalte] !== '.') {
        Rückgabewert: lösen (Zeile, Spalte + 1)
      }
      für (let num = 1; num <= 9; num++) {
        if (!isValid(Zeile, Spalte, Num)) {
          weitermachen
        }
 
        sudoku[Zeile][Spalte] = Num.toString()
        this.setState({ sudoku }) // Nach dem Ausfüllen des Rasters müssen Sie mit dem Status synchronisieren

        wenn (löse(Zeile, Spalte + 1)) {
          returniere wahr
        }

        sudoku[Zeile][Spalte] = '.'
        this.setState({ sudoku }) // Nach dem Ausfüllen des Rasters müssen Sie mit dem Status synchronisieren
      }
      return false
    }
    // Löse das Problem löse(0, 0)
  }

  rendern() {
    const { sudoku } = dieser.Zustand
    zurückkehren (……)
  }
}

Im Vergleich zur vorherigen Logik rufen wir hier einfach this.setState auf, um Sudoku mit dem Status zu synchronisieren, nachdem das zweidimensionale Array von Sudoku ausgefüllt wurde.

Funktion lösen(Zeile, Spalte) {
   …
   sudoku[Zeile][Spalte] = Num.toString()
+ dies.setState({ sudoku })
  …
   sudoku[Zeile][Spalte] = '.'
+ this.setState({ sudoku }) // Nach dem Ausfüllen des Rasters muss eine Synchronisierung mit dem Status erfolgen
}

Nach dem Aufruf von SolveSudoku wird festgestellt, dass kein dynamischer Effekt auftritt, das Ergebnis jedoch in einem Schritt mit der Ansicht synchronisiert wird.

Dies liegt daran, dass setState ein pseudo-asynchroner Aufruf ist. In einer Ereignisaufgabe werden alle setState-Aufrufe zu einem einzigen zusammengeführt. Wenn wir den dynamischen Prozess der Beantwortung von Fragen sehen möchten, müssen wir jede setState-Operation außerhalb des Ereignisflusses platzieren, d. h. in setTimeout. Weitere Fragen zur asynchronen Funktion „setState“ finden Sie in meinem vorherigen Artikel: Ist „setState“ in React eine Makro- oder eine Mikroaufgabe?

löseSudoku = async () => {
  const { sudoku } = dieser.Zustand
  //Überprüfen Sie, ob die eingegebene Nummer gültig ist. Siehe den obigen Code und wird hier nicht wiederholt const isValid = (row, col, num) => {
    …
  }
  // Verlasse den Ereignisfluss und rufe setState auf
  const setSudoku = async (Zeile, Spalte, Wert) => {
    sudoku[Zeile][Spalte] = Wert
    gib ein neues Versprechen zurück (Auflösen => {
      setzeTimeout(() => {
        dies.setState({
          Sudoku
        }, () => auflösen())
      })
    })
  }
  // Lösen Sie das Problem durch Rekursion + Backtracking const solve = async (row, col) => {
    …
    für (let num = 1; num <= 9; num++) {
      if (!isValid(Zeile, Spalte, Num)) {
        weitermachen
      }

   warte auf setSudoku(Zeile, Spalte, Num.toString())

      wenn (warte auf Lösung(Zeile, Spalte + 1)) {
        returniere wahr
      }

   warte auf setSudoku(Zeile, Spalte, '.')
    }
    return false
  }
  // Löse das Problem löse(0, 0)
}

Der endgültige Effekt ist wie folgt:

Zusammenfassen

Dies ist das Ende dieses Artikels über die Verwendung von JavaScript zum Lösen von Sudoku. Weitere relevante JavaScript-Sudoku-Inhalte finden Sie in den vorherigen Artikeln von 123WORDPRESS.COM oder in den folgenden verwandten Artikeln. Ich hoffe, dass jeder 123WORDPRESS.COM in Zukunft unterstützen wird!

Das könnte Sie auch interessieren:

Beispiel einer Javascript-Implementierung eines Sudoku-Algorithmus auf einer Webseite
Javascript-Implementierung der Sudoku-Lösung
Javascript-Sudoku Code zur Generierung von Sudoku-Puzzlespielen
JS-Implementierung eines gültigen Sudoku-Algorithmus-Beispiels
Zusammenfassung der wichtigsten Ideen zur Lösung von Sudoku-Problemen durch JavaScript-Traversierung

<<: Erste Schritte mit dem Alibaba Cloud ECS-Server (unbedingt zu lesendes Tutorial für Neulinge)

>>: Nach der Installation von Navicat in MySQL wird 2059 angezeigt: Authentifizierungs-Plugin und Docker für lokale virtuelle Maschinen sowie Remote-Link-Server