Observer Pattern Applied: Solving Sudoku, Easy Ones

5 min readApr 5, 2021

We solve Sudoku by following certain routines in our mind. Thus we have to apply handful of patterns to solve each of these routines. I am taking just one of these patterns good enough for solving easy ones and delve in to detail. We all know, we will be given a Sudoku 9x9 array with few cells filled with values 1 to 9. The placement and values of numbers guarantees a unique solution. The puzzle is solved by placing appropriate values in the remaining cells such that the numbers are not repeated vertically, horizontally or within the 9 minor 3x3 arrays.

Routine followed

To start with, each cell can have any value between 1 and 9, inclusive, with equal probability. When each of the given numbers is placed in the corresponding cell, the adjacent cells (horizontally, vertically and within the minor array) loose the opportunity to have this number. This is the crux of the problem that we are discussing. Let’s implement a class to define a cell that holds all possible entries.

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));
   }
  } 
... 
}

Placing a number in a cell reduces the array list to have just that number and remove the corresponding entry in the adjacent cells (8 vertically, 8 horizontally and 4 remaining cells in the minor array). As we place more numbers the size of array list in each of the cells gets reduced.

Pattern applied

Having said the routine that we want to follow in order to reduce the possibilities; how can we trigger the adjacent cells such that they respond to placing a number in a particular cell? The answer is to apply observer pattern. Here the observers are adjacent cells. See below code that has the criteria to identify the adjacent cells:

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 goes here 
  …
  }
 }
}

We need to re-look our definition of a cell as each cell is an observable to the adjacent cells and at the same time an observer of the adjacent cell. Refer below redefined cell class. The super class, observable, has the implementation to notify observers (here it refers to adjacent cells). Update method is the implementation of Observer interface that is called placing a value in a cell. Here we want to remove an entry from the array list.

public class Cell extends Observable implements Observer { 
 …
 // add the known value… and notify observerspublic 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) 
  …
 } 
}

Class definitions

Let us put together the definition of cell class below:

package my.apps.sudoku;import java.util.Observable;
import java.util.Observer;
import java.util.ArrayList;
import java.util.List;public class Cell extends Observable implements Observer {
 private List values = new ArrayList();
 private boolean isSolved = false;
 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));
  }
 }
 
 // add cells that are in the same line or same box as observers
 public synchronized void addObserver(Cell[][] cells) {
  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 isSecondary = (i/3 == row/3) && (j/3 == col/3);
    if (!isSame && (isSameLine || isSecondary)) {
     super.addObserver(cells[i][j]);
    }
   }
  }
 }// add the known value after clearing and notify observers
 public void setValue(int value) {
  values.clear();
  values.add(new Integer(value));
  isSolved = true;
  super.setChanged();
  super.notifyObservers(new Integer(value));
 }// Observe and remove the entry set in the observable
 public void update(Observable o, Object arg) {
  values.remove(arg);
  if (!isSolved && values.size() == 1) {
   Integer value = (Integer)values.get(0);
   setValue(value.intValue());
  }
 }
 
 // A cell is solved if the it has just one value
 public int getValue() {
  if (values.size() == 1) {
   return ((Integer)values.get(0)).intValue();
  }
  return 0;
 }
}

Below is the code for creating a collection of cell and setting up the values. It also demonstrates with a sample:

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

We discussed how the observer pattern distributes the logic to the observers rather than cluttering the code in one place. Likewise you will find other programming patterns coming handy. Learn them by applying to real world problems!

Article Source: http://EzineArticles.com/5909658

Observer Pattern Applied: Solving Sudoku, Easy Ones

Written by Shivaji Chelladurai