The Java Specialists' Newsletter
Issue 1282006-06-21 Category: Tips and Tricks Java version: JDK 1.5

Welcome to the 128th edition of The Java(tm) Specialists' Newsletter. On my flight from Cape Town to Frankfurt en route to TSSJS in Barcelona, I was reading about an attempted hijacking aboard a South African Airways (SAA) flight last Saturday. The flight attendants all seemed a bit skittish, not their usual friendly selves. But that was not what caught my attention. I saw a copy of a SuDoKu puzzle in the newspaper I was reading. You would have seen them around, together with a claim that this was the latest craze. I don't enjoy puzzles and games that can be handled by brute force number crunching, so up to now I had never attempted one.

So whilst flying at 30'000 feet, I wrote a little algorithm that solves them. There will be much better and faster approaches than mine, but it solved all the puzzles I threw at it in milliseconds, and I don't need to be much faster than that :)

Upcoming Java Specialist Master Courses: - please click here to sign up.

As from May 2010, we are also offering this course on the island of Crete. We only accept 6 students per class in Crete, due to the size of our conference room. Please book early to avoid disappointment!

San Jose CA, Mar 16-19 2010, $3500
Ottawa, Canada, Mar 22-25 2010, $3500
Oslo, Norway, Apr 13-16 2010, Kr 24500
Montreal, Canada, Apr 20-23 2010, $3500
Toronto, Canada, May 17-20 2010, $3500
Chania, Crete, May 25-28, Jun 29-Jul 2 or Aug 24-27 2010, €2500

In-house courses if these dates or locations do not suit you - click here for more information.

SuDoKu Madness

The program was written at 30'000 with a severe shortage of oxygen, so please excuse that it is not the most object-oriented in the world. It is also more complex than need be.

We start with the SuDoKu class, which we initialise with 81 integers. These must all be between 0 and 9, where 0 means that the cell is empty. We then call the solve() method and sit back and wait until the answer pops out a millisecond later.

Some notes about the code. Each cell on the gameboard holds an EnumSet of all possible values for that cell. When we reach an EnumSet of size 1, we have found a solution for that cell. If we end up with size 0, then there is no solution for the game.

I alternatively go through sieving the numbers that are on the board and searching for possible answers. I keep on going until I cannot reduce any more numbers, at which point there will be several answers to the puzzle. We could expand the program by then making a nondeterministic choice and continuing.

package
    com.cretesoft.sudoku;

    import java.util.*;

public class SuDoKu {
  public enum Value {
    ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE;

    public String toString() {
      return Integer.toString(ordinal() + 1);
    }
  }

  private static final int GRID = 9;

  private final Map<Position, EnumSet<Value>> numbers =
      new HashMap<Position, EnumSet<Value>>();

  public SuDoKu(int... values) {
    if (values.length != GRID * GRID)
      throw new IllegalArgumentException("Bad value count");
    Value[] all = Value.values();
    for (int i = 0; i < values.length; i++) {
      Position pos = new Position(i / GRID, i % GRID);
      if (values[i] == 0) {
        numbers.put(pos, EnumSet.range(Value.ONE, Value.NINE));
      } else {
        numbers.put(pos, EnumSet.of(all[values[i] - 1]));
      }
    }
    sieveImpossibleNumbers();
  }

  public boolean solve() {
    do {
      System.out.println(this);
    } while (sieveImpossibleNumbers() || searchForAnswers()) ;
    for (EnumSet<Value> values : numbers.values()) {
      if (values.size() != 1) return false;
    }
    return true;
  }

  /**
   * Goes through all the positions and removes numbers that are
   * not possible.  Also checks the correctness of the found
   * numbers.
   */
  private boolean sieveImpossibleNumbers() {
    boolean removed = false;
    for (Position pos : numbers.keySet()) {
      Value value = getNumber(pos);
      if (value == null) {
        // must be bitwise OR, otherwise it will fall through
        removed |= removeImpossibleNumbers(pos);
      } else {
        checkCorrectness(pos, value);
      }
    }
    return removed;
  }

  private boolean removeImpossibleNumbers(Position pos) {
    boolean removed = false;
    EnumSet<Value> vals = numbers.get(pos);
    for (Position other : pos.getRelatedPositions()) {
      removed |= vals.remove(getNumber(other));
    }
    return removed;
  }

  private Value getNumber(Position pos) {
    EnumSet<Value> vals = numbers.get(pos);
    if (vals.size() == 1) {
      return vals.iterator().next();
    }
    return null;
  }

  private void checkCorrectness(Position pos, Value val) {
    for (Position other : pos.getRelatedPositions()) {
      if (val == getNumber(other)) {
        throw new IllegalArgumentException("Error with: " + pos
            + " clashes with relative " + other);
      }
    }
  }

  private boolean searchForAnswers() {
    for (Position pos : numbers.keySet()) {
      EnumSet<Value> possible = numbers.get(pos);
      if (possible.size() > 1) {
        for (Value value : possible) {
          if (valueNotIn(value, pos.getHorizontalPositions()) ||
              valueNotIn(value, pos.getVerticalPositions()) ||
              valueNotIn(value, pos.getSmallSquarePositions())) {
            System.out.println(pos + " MUST BE " + value);
            numbers.put(pos, EnumSet.of(value));
            return true;
          }
        }
      }
    }
    return false;
  }

  private boolean valueNotIn(Value value,
                             Collection<Position> positions) {
    for (Position pos : positions) {
      if (numbers.get(pos).contains(value)) {
        return false;
      }
    }
    return true;
  }

  public String toString() {
    StringBuffer result = new StringBuffer();
    for (int row = 0; row < GRID; row++) {
      for (int col = 0; col < GRID; col++) {
        EnumSet<Value> vals = numbers.get(new Position(row, col));
        result.append('[');
        for (Value v : vals) result.append(v);
        result.append(']').append('\t');
      }
      result.append('\n');
    }
    return result.toString();
  }
}
  

The Position class represents a place on the gameboard. It also can tell me which other positions are related to it, either horizontally, vertically or in a small 3x3 box.

package 
    com.cretesoft.sudoku;

    import java.util.*;

public final class Position {
  private final int row;
  private final int col;

  public Position(int row, int col) {
    this.row = row;
    this.col = col;
  }

  public int hashCode() {
    return row * 29 + col;
  }

  public boolean equals(Object o) {
    if (this == o) return true;
    if (!(o instanceof Position)) return false;
    Position position = (Position) o;
    return !(col != position.col || row != position.row);
  }

  public String toString() {
    return "(" + row + "," + col + ")";
  }

  public Collection<Position> getRelatedPositions() {
    Collection<Position> result = new HashSet<Position>();
    result.addAll(getHorizontalPositions());
    result.addAll(getVerticalPositions());
    result.addAll(getSmallSquarePositions());
    return result;
  }

  public Collection<Position> getHorizontalPositions() {
    Collection<Position> result = new HashSet<Position>();
    for (int i = 0; i < 9; i++) {
      result.add(new Position(row, i));
    }
    result.remove(this);
    return result;
  }

  public Collection<Position> getVerticalPositions() {
    Collection<Position> result = new HashSet<Position>();
    for (int i = 0; i < 9; i++) {
      result.add(new Position(i, col));
    }
    result.remove(this);
    return result;
  }

  public Collection<Position> getSmallSquarePositions() {
    Collection<Position> result = new HashSet<Position>();
    for (int i = 0; i < 9; i++) {
      int smallSqRow = i / 3 + (row / 3) * 3;
      int smallSqCol = i % 3 + (col / 3) * 3;
      result.add(new Position(smallSqRow, smallSqCol));
    }
    result.remove(this);
    return result;
  }
}
  

We can try it out like this:

package 
    com.cretesoft.sudoku;

    public class SuDoKuTest {
  public static void main(String[] args) {
    SuDoKu gb = new SuDoKu( // Cape Times Mon 2006/06/19
        2, 0, 0, 9, 0, 6, 0, 0, 4,
        0, 0, 5, 0, 7, 0, 9, 0, 0,
        0, 3, 0, 0, 0, 0, 0, 8, 0,
        0, 0, 3, 4, 0, 7, 8, 0, 0,
        8, 9, 0, 2, 0, 5, 0, 6, 3,
        0, 0, 7, 6, 0, 8, 2, 0, 0,
        0, 7, 0, 0, 0, 0, 0, 2, 0,
        0, 0, 8, 0, 6, 0, 1, 0, 0,
        3, 0, 0, 7, 0, 1, 0, 0, 8);
    if (gb.solve()) {
      System.out.println("SOLVED!!!");
    } else {
      System.out.println("Could not solve");
    }
  }
}
  

When we run this SuDoKuTest, we see the various steps taken in order to solve it. So you could also use this as a tutor to show you how the answer is derived, if you are into SuDoKu.

    2 8 1 9 5 6 3 7 4
    4 6 5 8 7 3 9 1 2
    7 3 9 1 2 4 5 8 6
    6 2 3 4 9 7 8 5 1
    8 9 4 2 1 5 7 6 3
    5 1 7 6 3 8 2 4 9
    1 7 6 3 8 9 4 2 5
    9 4 8 5 6 2 1 3 7
    3 5 2 7 4 1 6 9 8
  

Kind regards

Heinz

Tips and Tricks Articles Related Java Course