Observer pattern applied: Solving Sudoku, easy ones

This article is intended for audience associated with software development and others who are interested in solving Sudoku (http://en.wikipedia.org/wiki/Sudoku) puzzles with little knowledge about Object Oriented programming. As we know Sudoku can be played at various difficuly levels, here I discuss about solving easy ones and how we can apply observer software pattern for the same. The essence of observer pattern is that one or more objects (called observers or listeners) are registered (or register themselves) to observe an event that may be raised by the observed object (the subject).

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 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)
      …
   }
}

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