Android

 Motif Observer appliqué: résoudre le Sudoku, les plus faciles

Nous résolvons le Sudoku en suivant certaines routines dans notre esprit. Nous devons donc appliquer une poignée de régularisations pour résoudre chacune de ces routines. Je ne prends qu’un de ces modèles assez bon pour résoudre des problèmes faciles et approfondir les détails. Nous savons tous que nous recevrons un tableau Sudoku 9×9 avec quelques cellules remplies avec les valeurs 1 à 9. Le placement et les valeurs des nombres garantissent une solution unique. Le puzzle est résolu en plaçant des valeurs appropriées dans les cellules restantes de sorte que les nombres ne se répètent pas verticalement, horizontalement ou dans les 9 matrices 3×3 mineures.

Routine suivie

Pour commencer, chaque cellule peut avoir une valeur comprise entre 1 et 9 inclus, avec une probabilité égale. Lorsque chacun des nombres donnés est placé dans la cellule correspondante, les cellules adjacentes (horizontalement, verticalement et à l'intérieur du tableau mineur) perdent l'occasion d'avoir ce numéro. C'est le noeud du problème dont nous discutons. Implémentons une classe pour définir une cellule contenant toutes les entrées possibles.


public class Cell {

private List values ​​= new ArrayList ();

private int row;

private int col;

// Add all possible entries (1 to 9) in each cell

public Cell (int row, int col) {

this.row = row;

this.col = col;

for (int n = 1; n <= 9; n ++) {

values.add (new Integer (n));

}

}
...
}

Le fait de placer un numéro dans une cellule réduit la liste du tableau à ce numéro et supprime l'entrée correspondante dans les cellules adjacentes (8 verticalement, 8 horizontalement et 4 cellules restantes dans le tableau mineur). Au fur et à mesure que nous plaçons plus de nombres, la taille de la liste dans chaque cellule est réduite.

Motif appliqué

Ayant dit la routine que nous voulons suivre afin de réduire les possibilités; Comment pouvons-nous déclencher les cellules adjacentes de manière à ce qu'elles réagissent en plaçant un nombre dans une cellule particulière? La réponse consiste à appliquer un motif d'observateur. Ici, les observateurs sont des cellules annexes. Voir ci-dessous le code qui a les critères pour identifier les cellules adjacentes:


for (int i = 0; i <9; i ++) {

for (int j = 0; j <9; j ++) {

boolean isSame = (i == row) && (j == col);

boolean isSameLine = (i == row) || (j == col);

boolean isMinor = (i / 3 == row / 3) && (j / 3 == col / 3);

if (! isSame && (isSameLine || isMinor)) {

// logic to add observers go here
...

}

}

}

Nous devons repenser notre définition d'une cellule car chaque cellule est observable par les cellules adjacentes et, en même temps, par un observateur de la cellule adjacente. Voir ci-dessous la classe de cellules redéfinie. La super-classe, observable, a l'implémentation de notifier les observateurs (ici, il s'agit de cellules auxiliaires). La méthode de mise à jour est l'implémentation de l'interface Observer appelée mise en place d'une valeur dans une cellule. Ici, nous voulons supprimer une entrée de la liste de tableaux.


public class Cell extends Observable implements Observer {
...

// add the known value ... and notify observers

public void setValue (int value) {
...

super.notifyObservers (new Integer (value));

}

// Observe and remove the entry set in the observable

public void update (Observable o, Object arg) {

values.remove (arg)
...

}
}

Définitions de classe

Mettons ensemble la définition de la classe de cellules ci-dessous:

package my.apps.sudoku;

importer java.util.Observable;

importer java.util.Observer;

importer java.util.ArrayList;

importer java.util.List;

Classe publique Cell extension Observable implements Observer {

Liste privée = new ArrayList ();

booléen privé isSolved = false;

privé int row;

privé int col;

// Ajouter toutes les entrées possibles (1 à 9) dans chaque cellule

public Cell (int row, int col) {

this.row = rangée;

this.col = col;

pour (int n = 1; n <= 9; n ++) {

valeurs.add (nouvel entier (n));

}

}

// ajoute des cellules qui sont dans la même ligne ou la même case que les observateurs

void public synchronized addObserver (Cell () () cellules) {

pour (int i = 0; i <9; i ++) {

pour (int j = 0; j <9; j ++) {

booléen isSame = (i == rangée) && (j == col);

booléen isSameLine = (i == rangée) || (j == col);

booléen isSecondary = (i / 3 == rangée / 3) && (j / 3 == col / 3);

if (! isSame && (isSameLine || isSecondary)) {

super.addObserver (cellules (i) (j));

}

}

}

}

// ajoute la valeur connue après avoir effacé et notifie les observateurs

public void setValue (int value) {

valeurs.clair ();

values.add (nouvel Integer (valeur));

isSolved = true;

super.setChanged ();

super.notifyObservers (nouvel entier (valeur));

}

// Observer et supprimer l'entrée définie dans l'observable

Mise à jour publique vide (Observable o, Object arg) {

valeurs.remove (arg);

if (! isSolved && values.size () == 1) {

Valeur entière = (Entier) values.get (0);

setValue (value.intValue ());

}

}

// Une cellule est résolue si elle n'a qu'une valeur

public int getValue () {

if (values.size () == 1) {

return ((Integer) values.get (0)). intValue ();

}

retourne 0;

}

}

Vous trouverez ci-dessous le code permettant de créer une collection de cellules et de définir les valeurs. Il montre également avec un exemple:


package my.apps.sudoku;

import java.util.Observable;
import java.util.Observer;
import java.util.ArrayList;
import java.util.List;

public class Sudoku {

private Cell () () cells = new Cell (9) (9);

public Sudoku () {

// initialize the cell

for (int i = 0; i <9; i ++) {

for (int j = 0; j <9; j ++) {

cells (i) (j) = new Cell (i, j);

}

}

// add observers

for (int i = 0; i <9; i ++) {

for (int j = 0; j <9; j ++) {

cells (i) (j) .addObserver (cells);

}

}

}

// set known values

public void setup (int () (puzzle) {

for (int i = 0; i <9; i ++) {

for (int j = 0; j <9; j ++) {

if (puzzle (i) (j)! = 0) {

cells (i) (j) .setValue (puzzle (i) (j));

}

}

}

}

public int getCellValue (int i, int j) {

return cells (i) (j) .getValue ();

}

public static void main (String () args) {

int ()) (puzzle = {

{0, 6, 2, 3, 0, 0, 9, 0, 0}

{0, 0, 0, 0, 8, 0, 0, 0, 7}

{8, 0, 0, 0, 0, 5, 0, 0, 4}

{0, 0, 5, 0, 2, 0, 0, 0, 6}

{0, 3, 0, 9, 4, 6, 0, 5, 0}

{4, 0, 0, 0, 5, 0, 7, 0, 0}

{7, 0, 0, 6, 0, 0, 0, 0, 3}

{5, 0, 0, 0, 3, 0, 0, 0, 0}

{0, 0, 3, 0, 0, 7, 8, 9, 0}

};

Sudoku sudoku = new Sudoku ();

sudoku.setup (puzzle);

for (int i = 0; i <9; i ++) {

for (int j = 0; j <9; j ++) {

System.out.print (sudoku.getCellValue (i, j) + "|");

}

System.out.println ();

}

}

Conclusion

Nous avons discuté de la façon dont le modèle d'observateur distribue la logique aux observateurs plutôt que d'encombrer le code au même endroit. De même, vous trouverez d'autres modèles de programmation très utiles. Apprenez-les en vous appliquant aux problèmes du monde réel!


Source by Shivaji Chelladurai

Afficher plus

Articles similaires

Laisser un commentaire

Bouton retour en haut de la page

Adblock détecté

S'il vous plaît envisager de nous soutenir en désactivant votre bloqueur de publicité