Moving Objects and Sprite Manager - Part 1

Simple moving objects

A moving object is often known as a sprite in the world of game programming. It is simple to write a routine for moving a small object across the screen. We just need simple formula relating the velocity and the coordinates of the object.

Suppose an object is currently located in (x,y). We can define the next coordinates by the velocity formula :

x = x+xv;
y = y+yv;

The (x,y) coordinates are calculated on each animation frame.

For example, if xv = 3 and yv = 0, then the object is moving to the right at a rate of 3 pixels per frame. If yv = -1 and xv = 0, then the object is moving upwards at a rate of 1 pixel per frame.

The anatomy of a moving object

We would make an object moving across the screen by repeating the following steps.

1. Erase the object at old position.
2. Update the position of the object by the velocity formula.
3. Draw the object at new position.
4. Wait for a short time so that the user can see the object.

It is commonly agreed that we need 20 to 30 frames per second (FPS) to achieve a reasonably smooth animation. It is best to implement the animation in a timer thread. The thread is actually a loop that sleep for 30 ms for each pass. Since 1 second contains 1000 ms, this effectively equals to an FPS of 33. (1000ms / 30 ms = 33 ) Of course the actual FPS is a bit smaller due to the overhead of redrawing the object and repainting the screen. The animation thread is listed as follows :

// thread entry point
  public void run()
  {
    try
    {
      while (true)
      {
        moveBall();       // move the ball to a new position
        repaint();        // redraw the panel.
        Thread.sleep(30); // delay so that user can see the ball.
      }
    }
    catch (Exception e)
    {
      e.printStackTrace();
    }
  }

Demonstration

A full sample of a bouncing ball follows. This should be simple enough as a starting point of writing simple animation program.

/******************************************************************************
* File : BouncingBall.java
* Author : http://java.macteki.com/
* Description :
*   Display a bouncing ball.
* Tested with : JDK 1.6
******************************************************************************/


import java.awt.image.BufferedImage;

class BouncingBall extends javax.swing.JPanel implements Runnable
{
  BufferedImage image=new BufferedImage(300,300,BufferedImage.TYPE_INT_RGB);

  int xBall=100, yBall=100;   // initial coordinates of the moving ball
  int xVelocity=3;            // moving 3 pixels per frame (to the right)

  public BouncingBall()
  {
    int w=image.getWidth(this);
    int h=image.getHeight(this);
    this.setPreferredSize(new java.awt.Dimension(w,h));
  }
 
  // override the paint() method, we don't count on the system.
  // We draw our own panel.
  public void paintComponent(java.awt.Graphics gr)
  {
    // Redraw the whole image instead of redrawing every object in the screen.
    // This technique is commonly known as "double buffering"
    gr.drawImage(image,0,0,this);
  }  


  // start the bouncing thread
  public void start()  
  {
    new Thread(this).start();
  }

  // thread entry point
  public void run()
  {
    try
    {
      while (true)
      {
        moveBall();       // move the ball to a new position
        repaint();        // redraw the panel.
        Thread.sleep(30); // delay and let the user see the ball.
      }
    }
    catch (Exception e)
    {
      e.printStackTrace();
    }
  }

  
  public void moveBall()
  { 
    // Double Buffering Technique :
    // Erase and redraw everything in a image object 
    // instead of directly drawing to the screen.
    java.awt.Graphics2D gr=(java.awt.Graphics2D) image.getGraphics();

    // erase ball at old position
    int diameter=10;
    gr.setColor(java.awt.Color.BLACK);  // this is the background color
    java.awt.geom.Ellipse2D circle=
      new java.awt.geom.Ellipse2D.Double(xBall,yBall,diameter,diameter);

    gr.fill(circle);

    // update ball position
    xBall+=xVelocity;
    if (xBall>=300-diameter || xBall<0) // hit border
    {
      xBall-=xVelocity;        // undo movement
      xVelocity=-xVelocity;    // change direction of velocity
    }

    // draw ball at new position
    gr.setColor(java.awt.Color.RED);  // this is the ball color
    java.awt.geom.Ellipse2D newCircle=
      new java.awt.geom.Ellipse2D.Double(xBall,yBall,diameter,diameter);

    gr.fill(newCircle);
  }

  public static void main(String[] args) throws Exception
  {
    javax.swing.JFrame window = new javax.swing.JFrame();
    window.setDefaultCloseOperation(javax.swing.JFrame.EXIT_ON_CLOSE);
    window.setTitle("Macteki bouncing ball");

    BouncingBall ball=new BouncingBall();
    window.add(ball);

    window.pack();
    window.setVisible(true);
    
    ball.start();
  }
}

Part 1 completed. To be continued...

Simple Random Number

Introduction

There are many algorithms to generate random number, some require very complex operations in order for the random sequence to have good statistical properties. As the title suggested, this article focus on "simple" algorithm only. That is, no more than a few lines of coding.

Physical Randomness vs Pseudo Randomness

Roughly speaking, a random sequence of numbers should be unpredictable. However, many computer algorithms use deterministic formula to generate random sequence. The sequence is hence predictable if we know the formula and the parameters in advance. To get really random data, we need some physical methods. For example, we may throw 10 dices a hundred times and record the sum of every throw. Of course I am not talking about virtual dice in computer, I am talking about physical dice in reality.

Throwing physical dices does produce pretty random results. It is, however, not practical in computer applications. Fortunately, there exists some methods to collect physical random data in computer, for example, the mini seconds value of the system clock, the hard disk seeking time, the time interval between key press, the pattern of mouse cursor movements are good source for randomness. Collecting these data periodically could produce quite unpredictable results, which is a good starting point for a random seed.

Test for randomness

Not all algorithms produce good random sequences. A good random sequence is required to have certain statistical properties. This is not a statistics course and I am not going through the details here. Instead I would use some more interesting and intuitive method to test whether a sequence is "random" enough. But first we must clarify what is random enough. The obvious question is "random enough for what purpose ?". In this article, "good enough" means it is good enough for casual applications such as computer game, but not for gambling game that involves real money.

How should we define good random sequence ? There are some strict answers in statistical sense. However, those are not the scope of this article. I would give an answer in a more informal sense. Intuitively, a random sequence should at least "looks" random. The next section we will provide a "visual test" for randomness. Note that the visual test only provides a gut feeling for randomness, it is not a strict science.

Linear Congruential Generator

One of the simplest random sequence generator is the linear congruential generator. Which has the following form :

N0 = seed
Ni+1 = (a*Ni + c ) mod m

For example, if we have a=16807, m=2147483647, seed=1, c=0, then we have the following sequence :

N0=1
N1=(16807*1+0) mod 2147483647 = 16807
N2=(16807*16807+0) mod 2147483647 = 282475249
N3=(16807*282475249+0) mod 2147483647 = 1622650073

The implementation is simple :

class LCG
{
  int a=16807,m=2147483647,seed=1, c=0;
  public int nextRandom()
  {
    seed=(a*seed + c) % m;
    return seed;
  }

  public static void main(String[] args) throws Exception
  {
    LCG random=new LCG();

    for (int i=0;i<10;i++)
    {
      System.out.println(random.nextRandom());
    }
  }
}

Visual Test

How good is the above random sequence ? Does it "look" random ? OK, let's have a "look" at it. The following program will generate a random "star field" using the above random sequence.

/******************************************************************************
* File : RandomStarField.java
* Author : http://java.macteki.com/
* Description :
*   Draw a random star field using a random number generator.
* Tested with : JDK 1.6
******************************************************************************/

import java.awt.image.BufferedImage;

class RandomStarField extends javax.swing.JPanel implements Runnable
{
  private BufferedImage image;    // image for holding the star field
  private boolean running=false;  // thread is running

  public RandomStarField()
  {
    this.setPreferredSize(new java.awt.Dimension(300,300));
    image = new BufferedImage(300,300,BufferedImage.TYPE_INT_RGB);
  }

  // override the paint method
  public void paintComponent(java.awt.Graphics graphics)
  {
    graphics.drawImage(image,0,0,this);
  }

  // this method is to be overridden for different random tests
  int a=16807,m=2147483647,seed=1, c=0;
  public int nextRandom()
  {
    seed=(a*seed + c) % m;
    return seed;
  }


  // thread entry point
  public void run()
  {
    java.awt.Graphics gr=image.getGraphics();
    int pixelCount=0;
    java.awt.Color[] colorTable=new java.awt.Color[] {
      java.awt.Color.RED, java.awt.Color.GREEN, java.awt.Color.BLUE, java.awt.Color.WHITE
    };
    running=true;
    while (running)
    {
      int x=Math.abs(nextRandom() % 300);  // random coordinates 
      int y=Math.abs(nextRandom() % 300);

      gr.setColor(colorTable[pixelCount%4]);  // cycle over 4 colors
      pixelCount++;
      gr.drawLine(x,y,x,y);      // draw the random pixel
      repaint();
      try { Thread.sleep(30); } catch (Exception ignore) {}
    }
  }

  // stop a running thread
  public void stop()
  {
    running=false;
  }

  // testing
  public static void main(String[] args) throws Exception
  {
    javax.swing.JFrame window=new javax.swing.JFrame();
    window.setDefaultCloseOperation(javax.swing.JFrame.EXIT_ON_CLOSE);
    window.setTitle("Macteki testing on Randomness");
    RandomStarField field = new RandomStarField();
    window.add(field);
    window.pack();
    window.setVisible(true);

    Thread thread=new Thread(field);
    thread.start();

  }
}

Here is how the "star field" looks like after running the program for one minute, at least it looks quite random:

Let's modify the nextRandom() method to generate a "visually less random" sequence. Just change the parameter m to 65536 to see what would happen.

  int a=16807, m=65536, seed=1, c=0;
  public int nextRandom()
  {
    seed=(a*seed + c) % m;
    return seed;
  }

The star field is as follows. Obviously it looks less random, and we would say this random sequence is not as good as the previous one. It shows that the choice of parameters is very important for linear congruential generator.

XORShift Random Number Generator

This method is invented by George Marsaglia. It generates a sequence of long integer. We will only use the higher 32 bits for the integer sequence.

//  XORShift Random Number Generator by George Marsaglia 
  long x=1;
  private long nextRandomLong() {
    x ^= (x << 21);
    x ^= (x >>> 35);
    x ^= (x << 4);
    return x;
  }

  // override nextRandom() for random test
  public int nextRandom()
  {
    return (int) (nextRandomLong()>>>32);  // we need 32 bits only
  }

How does the star field look like ? We will see it later. Let's see some other random sequence first.

Multiply by Carry

This method is also invented by George Marsaglia. The implementation is :

  int w = 31;    // must not be zero 
  int z = 41;    // must not be zero 
 
  public int nextRandom()
  {
    z = 36969 * (z & 65535) + (z >> 16);
    w = 18000 * (w & 65535) + (w >> 16);
    return (z << 16) + w;  // 32-bit result 
  }

java.util.Random

Finally we have the Java API implementation of random sequence.

  java.util.Random random=new java.util.Random(1);

  // override the nextRandom() method
  public int nextRandom()
  {
    return random.nextInt();
  }

Visual Random Test for all methods

With the help of multi threading, we may visually compare all methods in a single program. First we create four subclasses of RandomStarField, all we have to do is to override the nextRandom() method for different algorithms.

// java.util.Random
class StarField1 extends RandomStarField
{
  java.util.Random random=new java.util.Random(1);

  // override the nextRandom() method
  public int nextRandom()
  {
    return random.nextInt();
  }
}

//  XORShift Random Number Generator by George Marsaglia 
class StarField2 extends RandomStarField
{
  //  XORShift Random Number Generator by George Marsaglia 
  long x=1;
  private long nextRandomLong() {
    x ^= (x << 21);
    x ^= (x >>> 35);
    x ^= (x << 4);
    return x;
  }

  // override nextRandom() for random test
  public int nextRandom()
  {
    return (int) (nextRandomLong()>>>32);  // we need 32 bit only
  }
}

// Linear Congruential Generator
class StarField3 extends RandomStarField
{
  // override nextRandom() 
  int a=16807,m=2147483647,seed=1, c=0;
  public int nextRandom()
  {
    seed=(a*seed + c) % m;
    return seed;
  }
}

// Multiply-with-carry method invented by George Marsaglia.
class StarField4 extends RandomStarField
{

  int w = 31;    // must not be zero 
  int z = 41;    // must not be zero 
 
  public int nextRandom()
  {
    z = 36969 * (z & 65535) + (z >> 16);
    w = 18000 * (w & 65535) + (w >> 16);
    return (z << 16) + w;  // 32-bit result 
  }

}

Next we create a window to hold the four star fields. To run the demo, you must have RandomStarField.java and VisualRandomTest.java in the same folder.

javac *.java
java VisualRandomTest

RandomStarField.java is listed above. VisualRandomTest.java is as follows :

/******************************************************************************
* File : VisualRandomTest.java
* Author : http://java.macteki.com/
* Description :
*   Display visual test for four random sequences.
* Tested with : JDK 1.6
******************************************************************************/

class VisualRandomTest
{
  public static void main(String[] args) throws Exception
  {
    javax.swing.JFrame window=new javax.swing.JFrame();
    window.setDefaultCloseOperation(javax.swing.JFrame.EXIT_ON_CLOSE);
    window.setTitle("Macteki Visual Test on Randomness");

    // create four random star fields
    RandomStarField[] fields = {
      new StarField1(), new StarField2(), new StarField3(), new StarField4()
    };

    // use a GridLayout to hold the star fields
    window.setLayout(new java.awt.GridLayout(2,2,1,1));
    for (int i=0;i<fields.length;i++)
    {
      window.add(fields[i]);
    }
    window.pack();
    window.setVisible(true);

    // start all threads
    for (int i=0;i<fields.length;i++)
    {
      Thread thread=new Thread(fields[i]);
      thread.start();
    }

  }

}  // class VisualRandomTest

// java.util.Random
class StarField1 extends RandomStarField
{
  java.util.Random random=new java.util.Random(1);

  // override the nextRandom() method
  public int nextRandom()
  {
    return random.nextInt();
  }
}

//  XORShift Random Number Generators by George Marsaglia 
class StarField2 extends RandomStarField
{
  //  XORShift Random Number Generators by George Marsaglia 
  long x=1;
  private long nextRandomLong() {
    x ^= (x << 21);
    x ^= (x >>> 35);
    x ^= (x << 4);
    return x;
  }

  // override nextRandom() for random test
  public int nextRandom()
  {
    return (int) (nextRandomLong()>>>32);
  }
}

// Linear Congruential Generator
class StarField3 extends RandomStarField
{
  // override nextRandom() 
  int a=16807,m=2147483647,seed=1, c=0;
  public int nextRandom()
  {
    seed=(a*seed + c) % m;
    return seed;
  }
}

// Multiply-with-carry method invented by George Marsaglia.
class StarField4 extends RandomStarField
{

  int w = 31;    // must not be zero 
  int z = 41;    // must not be zero 
 
  public int nextRandom()
  {
    z = 36969 * (z & 65535) + (z >> 16);
    w = 18000 * (w & 65535) + (w >> 16);
    return (z << 16) + w;  // 32-bit result 
  }

}

The official Java convention suggests that we should use separate source file for every class. Yes, we should, but we don't have to. Since this site is focus on simplicity and readability, I prefer storing all the StarField subclasses in the same source file. Of course, this should not be done too often, for example, if the classes are very complex, it should go to another source file. In addition, if you are not the only member in the programming team, you'd better follow strict convention.

Are those good random sequences ?

Let's have a look at the result after running the program for one minute. All algorithms look quite random.

Let's see what happen after 30 minutes. That really shows a difference. The third method (linear congruential generator) is obviously "less random" than others. Anyway, I would say all of them are still acceptable for casual applications such as computer games.

Conclusion

This article introduces a visual random test for looking at random sequence. It is not a strict test. That means if a sequence "looks random" in the test, it doesn't mean it is random enough. However, if it doesn't look random at all in the test, you may say it is a bad sequence and discard it for further statistical tests.

Thanks for reading. Comments are welcome.

Logging Console Output and Exception

What we are missing

This is a continuation of the previous article. It is suggested to read it first before proceeding.

The SystemOutLogger demo in the previous article has some major drawbacks. It only works for String output. For example :

System.out.println("Hello World !")  // this works !
int number=12;
System.out.println(number);          // this doesn't work !

The reason is that we only overrode the method print(String) in SystemOutLogger.java, but not the method print(int).

To overcome this problem, we may choose to override print(int) as well. However, it is very clumsy since obviously we must also override print(float), print(double), print(long)...etc.

A better way is to override the "lower level" method. The write() method is a good candidate, because it is a good guess that all output should finally call the write() method.
We no longer need to override the print() and println() method once we override the write() method.

  public void write(byte[] buf, int off, int len) {
      try {
          super.write(buf, off, len);       // write to file
          consoleOut.write(buf, off, len);  // write to console
      } catch (Exception ignore) {
      }
  }

It is not yet a complete console logger, because we only log System Output, but not System Error. It is simple to fix, just adding a single line to the constructor will do.

System.setErr(this);  // redirect System Error

Demonstration

/******************************************************************************
* File : FullConsoleLogger.java
* Author : http://java.macteki.com/
* Description :
*   A class to log the console output, it logs everything include :
*   1. Normal String.  e.g.  System.out.println("hello");
*   2. Any object or primitive data type.  e.g.   System.out.println(i);
*   3. All exception output.  e.g.  e.printStackTrace();
* Tested with : JDK 1.6
******************************************************************************/


public class FullConsoleLogger extends java.io.PrintStream
{
  private java.io.PrintStream consoleOut=null;

  // initialize a file output stream, also save the console output stream to a variable
  public FullConsoleLogger() throws Exception
  {
      super(new java.io.FileOutputStream("out.txt"),true);
      consoleOut = System.out;
      System.setOut(this);
      System.setErr(this);
  }

  public void write(byte[] buf, int off, int len) {
      try {
          super.write(buf, off, len);
          consoleOut.write(buf, off, len);
      } catch (Exception ignore) {
      }
  }

 

  // Testing program, which can be placed in another source file if you wish
  public static void main(String[] args) throws Exception
  {
    FullConsoleLogger logger = new FullConsoleLogger();
    System.out.println("Logging output to out.txt");
    System.out.print("Hello, ");   // no line break, 
    System.out.println("World !"); // "Hello World !" would be on the same line
    System.out.println();          // Add an empty line
    for (int i=0;i<10;i++)
      System.out.println(i);    
    System.out.println("Thanks for visiting java.macteki.com");
    throw new RuntimeException("Exception !!!");
  }
}

Advance Usage : SwingConsole

With a little effort, we may derive a class from FullConsoleLogger to display the console output to a Swing GUI component such as JTextArea. Since it is a subclass of FullConsoleLogger, both files must be in the same folder to compile and run.

javac *.java
java SwingConsole

/******************************************************************************
* File : SwingConsole.java
* Author : http://java.macteki.com/
* Description :
*   1. log the console output (out.txt)
*   2. print the console output to a Swing component (JTextArea with scrollbar)
* Tested with : JDK 1.6
******************************************************************************/


public class SwingConsole extends FullConsoleLogger
{
  private javax.swing.JPanel myPanel=null;
  private javax.swing.JTextArea myTextArea=null;
  private StringBuffer myBuffer=new StringBuffer();

  // initialize a file output stream, also save the console output stream to a variable
  public SwingConsole() throws Exception
  {

      // initialize a JPanel for holding the output
      myTextArea = new javax.swing.JTextArea(); 
      myTextArea.setBackground(java.awt.Color.CYAN);
      myTextArea.setForeground(java.awt.Color.BLUE);
      myTextArea.setEditable(false);                  // read only
      // wrap the text area inside a panel with scroll bar.
      javax.swing.JScrollPane scrollingPanel=new javax.swing.JScrollPane(myTextArea);
      scrollingPanel.setPreferredSize(new java.awt.Dimension(580,380));

      // create a panel to hold the scrolling panel
      myPanel = new javax.swing.JPanel();      
      myPanel.add(scrollingPanel);  
      myPanel.setPreferredSize(new java.awt.Dimension(600,400));

  }

  public void write(byte[] buf, int off, int len) {
      try {
          super.write(buf, off, len);
          updateTextArea(buf, off, len);
      } catch (Exception ignore) {
      }
  }


  public void updateTextArea(byte[] buf, int off, int len)
  {
    String s=new String(buf,off,len);
    myBuffer.append(s);  // write to buffer until linefeed found
    if (s.indexOf("\n")>=0) 
    {
      // linefeed found, update TextArea
      myTextArea.append(myBuffer.toString());  // write to JTextArea
      myTextArea.setCaretPosition(myTextArea.getDocument().getLength()); // auto scroll
      keepLines(50);          // keep 50 lines only

      myBuffer.setLength(0);  // clear buffer
    }
  }


  // control how many lines to be kept in the JTextArea to avoid memory error
  public void keepLines(int maxLines)
  {
    try
    {
      javax.swing.text.Element root = myTextArea.getDocument().getDefaultRootElement();
      if (root.getElementCount() > maxLines) {
        javax.swing.text.Element firstLine = root.getElement(0);
        myTextArea.getDocument().remove(0, firstLine.getEndOffset());
      }
    } catch (Exception e)
    {
      e.printStackTrace();
    }
  }


  // return a panel for holding the console output
  public javax.swing.JPanel getPanel()
  {
    return myPanel;
  }

  // Testing program, which can be placed in another source file if you wish
  public static void main(String[] args) throws Exception
  {
    SwingConsole console = new SwingConsole();

    javax.swing.JFrame window=new javax.swing.JFrame();
    window.setTitle("Macteki GUI console");
    window.setDefaultCloseOperation(javax.swing.JFrame.EXIT_ON_CLOSE);
    window.add(console.getPanel());
    window.pack();
    window.setVisible(true);

    System.out.println("Logging output to out.txt");
    System.out.print("Hello, ");   // no line break, 
    System.out.println("World !"); // "Hello World !" would be on the same line
    System.out.println();          // Add an empty line
    System.out.println("Thanks for visiting java.macteki.com");

    for (int i=0;i<100;i++)
    {
      System.out.println("progress="+i+"%");
      Thread.sleep(100);
    }

    System.out.println("Completed ! Check the file out.txt.  ");
    System.out.println("You may also scroll up to check the text area");
    System.out.println("If you wish to keep all output in the text area, ");
    System.out.println("set a bigger buffer size in the keepLine() method.");

  }
}

Thanks for reading. Comments are welcome.

How to log console output ?

What is Console Output

Any output that is produced by System.out.

Redirect vs Logging

The previous article talked about redirecting System.out. Redirecting means to store the console output to a file, without actually printing to the Console Window. Logging means that the output is print to the console window as normal, but those output are saved to a log file as well for other purpose(such as debugging, auditing,...etc).

How ?

A small modification of the sample program in the previous article would serve the purpose.

/******************************************************************************
* File : SystemOutLogger.java
* Author : http://java.macteki.com/
* Description :
*   A class to log the console output
* Tested with : JDK 1.6
******************************************************************************/


public class SystemOutLogger extends java.io.PrintStream
{
  private java.io.PrintStream consoleOut=null;

  // initialize a file output stream, also save the console output stream to a variable
  public SystemOutLogger() throws Exception
  {
      super(new java.io.FileOutputStream("out.txt"),true);
      consoleOut = System.out;
      System.setOut(this);
  }

 
  // override the print() method so that it prints to file as well as console
  public void print(String s)
  {
    super.print(s);        // write to file
    consoleOut.print(s);   // write to console
  }

  // override println() with String parameter
  public void println(String s)
  {
    print(s+"\n");
  }

  // override println() without parameter
  public void println()
  {
    println("");
  }

  // Testing program, which can be placed in another source file if you wish
  public static void main(String[] args) throws Exception
  {
    SystemOutLogger logger = new SystemOutLogger();
    System.out.println("Logging output to out.txt");
    System.out.print("Hello, ");   // no line break, 
    System.out.println("World !"); // "Hello World !" would be on the same line
    System.out.println();          // Add an empty line
    System.out.println("Thanks for visiting java.macteki.com");
  }
}

Thanks for reading. Comments are welcome.

How to redirect System.out ?

Redirect Console Output

The previous article talked about console input, it is time to write something about console output.

To print something to the console window, simply write :

// console output
System.out.println("Hello !");

System.out is a system variable in Java. Looking at the documentation of java.lang.System, you will find System.out is actually a PrintStream.

A PrintStream is capable of writing output to file or console window. To redirect System.out, we just need to define a new PrintStream targeting to a text file instead of the console window.

public class MySystemOut extends java.io.PrintStream
{
  private java.io.PrintStream oldOut=null;

  public MySystemOut() throws Exception
  {
      super(new java.io.FileOutputStream("out.txt"),true);
  }
}

We need to define two more methods in MySystemOut, namely startRedirect() and stopRedirect(). The method names are self explanatory.

// defined inside class MySystemOut
public void startRedirect()
{
  oldOut = System.out;
  System.setOut(this);
}

public void stopRedirect()
{
  System.setOut(oldOut);
}

You will need a testing program which contains a main() method. It just creates a MySystemOut object and starts the redirect process.

/******************************************************************************
* File : A.java
* Author : http://java.macteki.com/
* Description :
*   Main program for testing MySystemOut
* Tested with : JDK 1.6
******************************************************************************/

public class A
{
  public static void main(String[] args) throws Exception
  {
    MySystemOut out=new MySystemOut();
  
    System.out.println("Going to redirect System.out...");

    out.startRedirect();

    for (int i=0;i<10;i++)
      System.out.println("this should be in out.txt:"+i);


    out.stopRedirect();

    System.out.println("Console output restored !");

    for (int i=0;i<10;i++)  
      System.out.println("this should be on console screen:"+i);
  }

}

MySystemOut.java

/******************************************************************************
* File : MySystemOut.java
* Author : http://java.macteki.com/
* Description :
*   A class to redirect System.out
* Tested with : JDK 1.6
******************************************************************************/


public class MySystemOut extends java.io.PrintStream
{
  private java.io.PrintStream oldOut=null;

  public MySystemOut() throws Exception
  {
      super(new java.io.FileOutputStream("out.txt"),true);
  }

  public void startRedirect()
  {
    oldOut = System.out;
    System.setOut(this);
  }

  public void stopRedirect()
  {
    System.setOut(oldOut);
  }
}

Compilation and Testing

To compile, you need both A.java and MySystemOut.java in the same folder, issue :

javac *.java

To run, just type :

java A

An output file "out.txt" will be generated in the same folder.

Thanks for reading. Comments are welcome.

About Console Input

Reading from System.in

What is System.in ?

It is a system variable. Its data type is InputStream. From the documentation of java.io.InputStream, the simplest method to read a byte is the read() method.

To read a line from the console, a while loop can be used to repeatedly read character until the linefeed character is read.

// read a line from console input character by character
public static void main(String[] args) throws Exception
{
  String s="";
  byte[] buffer=new byte[1];
  while (true)
  {
    int n=System.in.read();
    char ch=0;      
    if (n>0) {
      ch=(char) n; 
      s += ch;
    }
    if (ch=='\n') break;
  }
  System.out.println("Input String="+s);
}

Reading System.in character by character is not efficient. Java does provide wrapper for InputStream so that reading a line is more simple. The following program wraps System.in with a InputStreamReader, then wraps the InputStreamReader with a BufferedReader object. Since BufferedReader supports the readLine() method, it is a more high level and thus simpler implementation.

// read a line from Console using BufferedReader
public static void main(String[] args) throws Exception
{
  java.io.BufferedReader br=new java.io.BufferedReader(
    new java.io.InputStreamReader(System.in));
  String line=br.readLine();
  System.out.println(line);
}

Command Line Interpreter

Let's complete the demonstration by writing a simple command interpreter. The interpreter supports only three commands :

1. time
   
2. date
   
3. exit
   

The commands will display the current time, current date and exit the program respectively. The program won't stop until you type 'exit'. Anything other than the above commands will result in an error message.

/******************************************************************************
* File : ConsoleInput.java
* Author : http://java.macteki.com/
* Description :
*   Console Input Demonstration (A simple command line interpreter)
* Tested with : JDK 1.6
******************************************************************************/

class ConsoleInput
{

  // a simple "command interpreter"
  public static void doCommand(String line)
  {
    if (line.equals("time"))
    {
      // display current time
      java.util.Date date=new java.util.Date();
      java.text.SimpleDateFormat f=new java.text.SimpleDateFormat("HH:mm");
      String time=f.format(date);
      System.out.println(time);
    }
    else if (line.equals("date"))
    {
      // display current time
      java.util.Date date=new java.util.Date();
      java.text.SimpleDateFormat f=new java.text.SimpleDateFormat("yyyy-MM-dd");
      String dateString=f.format(date);
      System.out.println(dateString);
    }
    else if (line.equals("exit"))
    {
      System.exit(1);  // quit the program
    }
    else
    {
      System.out.println("Unknown command !");
    }
  }

  public static void main(String[] args) throws Exception
  {
    while (true)
    {
      java.io.BufferedReader br=new java.io.BufferedReader(
        new java.io.InputStreamReader(System.in));
      String line=br.readLine();
      doCommand(line);
    }
  }
}

Thanks for reading. Comments are welcome.

Display a rotating Taichi Image.

The previous article contains source code for drawing a Taichi image. This article will create an animation thread that rotate the image in the graphics panel.

How to rotate a image in Java

A coordinate transformation can be applied to the Graphics2D object.

// gr is a java.awt.Graphics2D object
java.awt.geom.AffineTransform transform = gr.getTransform();

// rotate the image about the center of panel.
int xPanelCenter=this.getWidth()/2;
int yPanelCenter=this.getHeight()/2;
double pi=3.141592654;
double angle=rotatedDegree*pi/180;  // convert to radian
transform.rotate(angle,xPanelCenter,yPanelCenter);

gr.setTransform(transform);  // apply transformation

At this point, all coordinates in the gr object will be transformed. Calling the drawImage() method now will draw a transformed (rotated) image.

// draw the image
gr.drawImage(taichiImage,10,10,this);

How to create an animation thread

To create a new thread in Java, you must specified the thread entry point, which is typically know as the "run()" method.

Steps to start a running thread :

1. Implements the run() method of a "Runnable" interface.
2. Wrap the Runnable interface with a Thread object.
3. Invoke the start() method of the Thread object.

Let's do it step by step now.

1. Implements the run() method of a "Runnable" interface.

// animation thread
public void run()
{
  while (true)
  {
    rotatedDegree=rotatedDegree+1;  // rotate one degree for each frame.
    repaint();

    // sleep for 40 ms, roughly 25 frames per second (1000/40=25)
    try { Thread.sleep(40); } catch (Exception ignore) {}
  }
}

/*
The idea of the above animation is : repeatedly draw a new frame, repaint the screen 
then delay for a while so that the frame can be seen.  
To create a smooth animation, frame per second should between 20 and 30.  
The above sample has a FPS value slightly less than 25.
*/

2. Wrap the Runnable interface with a Thread object.

// graphicsPanel is a Runnable interface
Thread thread=new Thread(graphicsPanel);

3. Invoke the start() method of the Thread object.

thread.start();   // the run() method will be started

Full runnable demo

/******************************************************************************
* File : RotatingTaichi.java
* Author : http://java.macteki.com/
* Description :
*   Display a rotating Taichi image in a graphics panel.
* Tested with : JDK 1.6
******************************************************************************/

import java.awt.image.BufferedImage;
import java.awt.Point;

class RotatingTaichi extends javax.swing.JPanel implements Runnable
{
  private BufferedImage taichiImage;
  private int rotatedDegree=0;

  public static RotatingTaichi getInstance()
  {
    RotatingTaichi panel=new RotatingTaichi();
    panel.setPreferredSize(new java.awt.Dimension(320,320));

    panel.setBackground(java.awt.Color.WHITE);

    panel.taichiImage = new BufferedImage(300,300,BufferedImage.TYPE_INT_RGB);
    panel.drawTaichi(panel.taichiImage,150,150,100);

    return panel;
  }

  // draw a taichi image
  public void drawTaichi(BufferedImage image,int xCenter,int yCenter, int radius)
  {
    java.awt.Graphics2D gr = (java.awt.Graphics2D) image.getGraphics();
    gr.setColor(java.awt.Color.WHITE);
    gr.fillRect(0,0,image.getWidth(this),image.getWidth(this));

    gr.setStroke(new java.awt.BasicStroke(2));  // pen width
    gr.setColor(java.awt.Color.BLACK);

    // draw the big circle
    int r=radius;  // radius
    int xc=xCenter, yc=yCenter;  // center
    // the bounding rectangle (x,y,w,h) of the circle is defined by :
    // x=xc-r,  y=yc-r,  w=r*2,  h=r*2;
    gr.drawArc(xc-r,yc-r,r*2,r*2,0,360);  // (x,y,w,h,startDegree,arcDegree)

    // draw a half circle inside the big circle
    xc=xCenter; yc=yCenter-radius/2; r=radius/2;
    gr.drawArc(xc-r,yc-r,r*2,r*2,270,180);  // (x,y,w,h,startDegree,arcDegree)

    // draw another half circle inside the big circle
    xc=xCenter; yc=yCenter+radius/2; r=radius/2;
    gr.drawArc(xc-r,yc-r,r*2,r*2,90,180);  // (x,y,w,h,startDegree,arcDegree)

    // draw two more small circles
    xc=xCenter; yc=yCenter-radius/2; r=radius/8;
    gr.drawArc(xc-r,yc-r,r*2,r*2,0,360);  // (x,y,w,h,startDegree,arcDegree)

    xc=xCenter; yc=yCenter+radius/2; r=radius/8+1;
    gr.drawArc(xc-r,yc-r,r*2,r*2,0,360);  // (x,y,w,h,startDegree,arcDegree)

    // fill with appropriate color
    int black=packRgb(0,0,0);
    floodFill(image,xCenter,yCenter-radius/2,black);

    floodFill(image,xCenter,yCenter+radius/16,black);
  }


  // override the paint method
  // just paint the taichi image here
  public void paintComponent(java.awt.Graphics graphics)
  {
    super.paintComponent(graphics);  

    // Graphics2D is a better choice to the default Graphics object
    java.awt.Graphics2D gr=(java.awt.Graphics2D) graphics;

    java.awt.geom.AffineTransform transform = gr.getTransform();

    // rotate the image about the center of panel.
    int xPanelCenter=this.getWidth()/2;
    int yPanelCenter=this.getHeight()/2;
    double pi=3.141592654;
    double angle=rotatedDegree*pi/180;  // convert to radian
    transform.rotate(angle,xPanelCenter,yPanelCenter);
 
    gr.setTransform(transform);
    
    gr.drawImage(taichiImage,10,10,this);
  }

  public static int packRgb(int r,int g,int b)
  {
    return (r*256+g)*256+b;
  }


  // implements the flood fill algorithm
  public static void floodFill(BufferedImage image, int x,int y, int fillColor)
  {
    java.util.ArrayList<Point> examList=new java.util.ArrayList<Point>();

    int initialColor=image.getRGB(x,y);
    examList.add(new Point(x,y));

    while (examList.size()>0)
    {
      Point p = examList.remove(0);  // get and remove the first point in the list
      if (image.getRGB(p.x,p.y)==initialColor) 
      {
        x = p.x;  y = p.y;
        image.setRGB(x, y, fillColor);  // fill current pixel

        if (image.getRGB(x-1,y)==initialColor) // check west neighbor
        {
          examList.add(new Point(x-1,y));        
        }
        if (image.getRGB(x+1,y)==initialColor) // check east neighbor
        {
          examList.add(new Point(x+1,y));        
        }
        if (image.getRGB(x,y-1)==initialColor) // check north neighbor
        {
          examList.add(new Point(x,y-1));        
        }
        if (image.getRGB(x,y+1)==initialColor) // check south neighbor
        {
          examList.add(new Point(x,y+1));       
        }

      }
    }

  }


  // animation thread
  public void run()
  {
    while (true)
    {
      rotatedDegree=rotatedDegree+1;  // rotate one degree for each frame.
      repaint();

      // sleep for 40 ms, roughly 25 frames per second (1000/40=25)
      try { Thread.sleep(40); } catch (Exception ignore) {}
    }
  }

  public static void main(String[] args) throws Exception
  {
    RotatingTaichi graphicsPanel = RotatingTaichi.getInstance();

    javax.swing.JFrame window=new javax.swing.JFrame();
    window.add(graphicsPanel);
    window.pack();

    window.setDefaultCloseOperation(javax.swing.JFrame.EXIT_ON_CLOSE);
    window.setTitle("Macteki Taichi Panel");
    window.setVisible(true);

    // start the animation thread
    new Thread(graphicsPanel).start();
  }
}

Thanks for reading. Comments are welcome.

How to draw a taichi image ?

We may draw a taichi by the following steps :

1. Draw 3 circles.

2. Erase the left half of the upper circle and the right half of the lower circle.

3. Add two "eyes".

4. Fill regions with appropriate color.

Straight forward implementation

public void drawTaichi(BufferedImage image)
{
  java.awt.Graphics2D gr = (java.awt.Graphics2D) image.getGraphics();
  gr.setColor(java.awt.Color.WHITE);
  gr.fillRect(0,0,300,300);

  gr.setStroke(new java.awt.BasicStroke(2));  // pen width
  gr.setColor(java.awt.Color.BLACK);

  // draw a big circle with radius 100 with center at (150,150)
  int r=100;  // radius
  int xc=150, yc=150;  // center
  // the bounding rectangle (x,y,w,h) of the circle is defined by :
  // x=xc-r,  y=yc-r,  w=r*2,  h=r*2;
  gr.drawArc(xc-r,yc-r,r*2,r*2,0,360);  // (x,y,w,h,startDegree,arcDegree)

  // draw a small half circle with radius 50 with center at (150,100)
  xc=150; yc=100; r=50;
  gr.drawArc(xc-r,yc-r,r*2,r*2,270,180);  // (x,y,w,h,startDegree,arcDegree)

  // draw another small half circle with radius 50 with center at (150,200)
  xc=150; yc=200; r=50;
  gr.drawArc(xc-r,yc-r,r*2,r*2,90,180);  // (x,y,w,h,startDegree,arcDegree)

  // draw two more small circles ("eyes")
  xc=150; yc=100; r=12;
  gr.drawArc(xc-r,yc-r,r*2,r*2,0,360);  // (x,y,w,h,startDegree,arcDegree)

  xc=150; yc=200; r=12;
  gr.drawArc(xc-r,yc-r,r*2,r*2,0,360);  // (x,y,w,h,startDegree,arcDegree)

  // fill with appropriate color
  int black=packRgb(0,0,0);
  floodFill(image,150,100,black);

  floodFill(image,150,160,black);
}

The above implementation uses the floodFill() method described in the previous article.

Improvement : removing the hard coded values

The above implementation is full of hard coded values such as 300,150,100...etc. A way to remove those hard coded values is to introduce magic constants such as :

int BIG_RADIUS=100;
int HARD_RADIUS=BIG_RADIUS/2;
...

Another approach is to redefine the drawing routine to accept parameters. Full runnable sample follows :

/******************************************************************************
* File : Taichi.java
* Author : http://java.macteki.com/
* Description :
*   Draw a Taichi image in a graphics panel.
* Tested with : JDK 1.6
******************************************************************************/

import java.awt.image.BufferedImage;
import java.awt.Point;

class Taichi extends javax.swing.JPanel
{
  private BufferedImage taichiImage;

  public static Taichi getInstance()
  {
    Taichi panel=new Taichi();
    panel.setPreferredSize(new java.awt.Dimension(320,320));

    panel.taichiImage = new BufferedImage(300,300,BufferedImage.TYPE_INT_RGB);
    panel.drawTaichi(panel.taichiImage,150,150,100);

    return panel;
  }

  // draw a taichi image
  public void drawTaichi(BufferedImage image,int xCenter,int yCenter, int radius)
  {
    java.awt.Graphics2D gr = (java.awt.Graphics2D) image.getGraphics();
    gr.setColor(java.awt.Color.WHITE);
    gr.fillRect(0,0,image.getWidth(this),image.getWidth(this));

    gr.setStroke(new java.awt.BasicStroke(2));  // pen width
    gr.setColor(java.awt.Color.BLACK);

    // draw the big circle
    int r=radius;  // radius
    int xc=xCenter, yc=yCenter;  // center
    // the bounding rectangle (x,y,w,h) of the circle is defined by :
    // x=xc-r,  y=yc-r,  w=r*2,  h=r*2;
    gr.drawArc(xc-r,yc-r,r*2,r*2,0,360);  // (x,y,w,h,startDegree,arcDegree)

    // draw a half circle inside the big circle
    xc=xCenter; yc=yCenter-radius/2; r=radius/2;
    gr.drawArc(xc-r,yc-r,r*2,r*2,270,180);  // (x,y,w,h,startDegree,arcDegree)

    // draw another half circle inside the big circle
    xc=xCenter; yc=yCenter+radius/2; r=radius/2;
    gr.drawArc(xc-r,yc-r,r*2,r*2,90,180);  // (x,y,w,h,startDegree,arcDegree)

    // draw two more small circles
    xc=xCenter; yc=yCenter-radius/2; r=radius/8;
    gr.drawArc(xc-r,yc-r,r*2,r*2,0,360);  // (x,y,w,h,startDegree,arcDegree)

    xc=xCenter; yc=yCenter+radius/2; r=radius/8+1;
    gr.drawArc(xc-r,yc-r,r*2,r*2,0,360);  // (x,y,w,h,startDegree,arcDegree)

    // fill with appropriate color
    int black=packRgb(0,0,0);
    floodFill(image,xCenter,yCenter-radius/2,black);

    floodFill(image,xCenter,yCenter+radius/16,black);
  }


  // override the paint method
  // just paint the taichi image here
  public void paintComponent(java.awt.Graphics graphics)
  {
    super.paintComponent(graphics);  

    // Graphics2D is a better choice to the default Graphics object
    java.awt.Graphics2D gr=(java.awt.Graphics2D) graphics;

    gr.drawImage(taichiImage,10,10,this);
  }

  public static int packRgb(int r,int g,int b)
  {
    return (r*256+g)*256+b;
  }


  // implements the flood fill algorithm
  public static void floodFill(BufferedImage image, int x,int y, int fillColor)
  {
    java.util.ArrayList<Point> examList=new java.util.ArrayList<Point>();

    int initialColor=image.getRGB(x,y);
    examList.add(new Point(x,y));

    while (examList.size()>0)
    {
      Point p = examList.remove(0);  // get and remove the first point in the list
      if (image.getRGB(p.x,p.y)==initialColor) 
      {
        x = p.x;  y = p.y;
        image.setRGB(x, y, fillColor);  // fill current pixel

        if (image.getRGB(x-1,y)==initialColor) // check west neighbor
        {
          examList.add(new Point(x-1,y));        
        }
        if (image.getRGB(x+1,y)==initialColor) // check east neighbor
        {
          examList.add(new Point(x+1,y));        
        }
        if (image.getRGB(x,y-1)==initialColor) // check north neighbor
        {
          examList.add(new Point(x,y-1));        
        }
        if (image.getRGB(x,y+1)==initialColor) // check south neighbor
        {
          examList.add(new Point(x,y+1));       
        }

      }
    }

  }



  public static void main(String[] args) throws Exception
  {
    Taichi graphicPanel = Taichi.getInstance();

    javax.swing.JFrame window=new javax.swing.JFrame();
    window.add(graphicPanel);
    window.pack();

    window.setDefaultCloseOperation(javax.swing.JFrame.EXIT_ON_CLOSE);
    window.setTitle("Macteki Taichi Panel");
    window.setVisible(true);
  }
}

The next article will make a rotating Taichi animation.

Thanks for reading. Comments are welcome.

How to do a flood fill operation in Java ?

Java does provide API to fill a simple shape with a specified color. So why do we want to write a flood fill program ?

The answer is :

1. API belongs to public. Knowledge belongs to yourself.
2. Self written method is sometimes more flexible than API.

The algorithm for flood fill is simple :

1. Starts with any pixel inside the shape to be filled.
2. Remember the color of this pixel, name it as initialColor.
3. Add the initial point to the examination list
4. For all point P in the examination list do
• If P.color = initialColor then
• Fill point P with the target color
• Add all neighboring pixels of point P to the examination list

This leads to the following implementation :

  public static void floodFill(BufferedImage image, int x,int y, int fillColor)
  {
    java.util.ArrayList<Point> examList=new java.util.ArrayList<Point>();

    int initialColor=image.getRGB(x,y);
    examList.add(new Point(x,y));

    while (examList.size()>0)
    {
      Point p = examList.remove(0);  // get and remove the first point in the list
      if (image.getRGB(p.x,p.y)==initialColor) 
      {
        x = p.x;  y = p.y;
        image.setRGB(x, y, fillColor);  // fill current pixel

        examList.add(new Point(x-1,y));        // check west neighbor
        examList.add(new Point(x+1,y));        // check east neighbor
        examList.add(new Point(x,y-1));        // check north neighbor
        examList.add(new Point(x,y+1));        // check south neighbor

        repaintAndDelay(image);    // this line can be removed
      }
    }
  }

The method repaintAndDelay() is just for showing how the shape is actually filled. You may remove it if you wish.

Full runnable source code follows :

/******************************************************************************
* File : AnimationFiller.java
* Author : http://java.macteki.com/
* Description :
*   Demonstrate a flood fill algorithm.
* Tested with : JDK 1.6
******************************************************************************/

import java.awt.image.BufferedImage;
import javax.swing.JLabel;
import javax.swing.ImageIcon;
import java.awt.Point;

class AnimationFiller
{
  
  // fill the whole image with a color specified by its RGB component
  static void fillImage(BufferedImage image, int red, int green, int blue)
  {
    int packedRGB = (red*256+green)*256+blue;

    for (int y=0;y<image.getHeight(null);y++)
    {
      for (int x=0;x<image.getWidth(null);x++)
        image.setRGB(x,y,packedRGB);
    }
  }

  // draw a red circle with a pen width of 5 pixels
  static void drawCircle(BufferedImage image)
  {
    java.awt.Graphics2D gr=(java.awt.Graphics2D) image.getGraphics(); 

    gr.setColor(new java.awt.Color(255,0,0));  // red
    gr.setStroke(new java.awt.BasicStroke(5));  // set pen width to 5 pixel
    gr.drawArc(5,5,150,150,0,360);  // (x,y,w,h,startDegree, endDegree);
  }

  // repaint the image and delay for a little while
  private static void repaintAndDelay(BufferedImage image)
  {
    _imageLabel.setIcon(new ImageIcon(image));
    _imageLabel.repaint();
    try { Thread.sleep(1); } catch (Exception ignore) {}
  }

  // implements the flood fill algorithm
  public static void floodFill(BufferedImage image, int x,int y, int fillColor)
  {
    java.util.ArrayList<Point> examList=new java.util.ArrayList<Point>();

    int initialColor=image.getRGB(x,y);
    examList.add(new Point(x,y));

    while (examList.size()>0)
    {
      Point p = examList.remove(0);  // get and remove the first point in the list
      if (image.getRGB(p.x,p.y)==initialColor) 
      {
        x = p.x;  y = p.y;
        image.setRGB(x, y, fillColor);  // fill current pixel

        examList.add(new Point(x-1,y));        // check west neighbor
        examList.add(new Point(x+1,y));        // check east neighbor
        examList.add(new Point(x,y-1));        // check north neighbor
        examList.add(new Point(x,y+1));        // check south neighbor

        repaintAndDelay(image);    // this line can be removed
      }
    }

  }

  public static int packRgb(int r,int g,int b)
  {
    return (r*256+g)*256+b;
  }

  static JLabel _imageLabel;
  public static void main(String[] args) throws Exception
  {
    // create an 200x200 RGB image
    BufferedImage image=new BufferedImage(200,200,BufferedImage.TYPE_INT_RGB);

    // fill the image with green color
    fillImage(image,0,255,0);

    // draw a red circle with 5 pixel pen width
    drawCircle(image);

    JLabel imageLabel=new JLabel();
    _imageLabel = imageLabel;  // make it global
    imageLabel.setIcon(new ImageIcon(image));
    imageLabel.setText("Filling the circle with yellow color ...");

    javax.swing.JFrame window=new javax.swing.JFrame();
    window.setTitle("Macteki flood filler");
    window.setDefaultCloseOperation(javax.swing.JFrame.EXIT_ON_CLOSE);

    window.add(imageLabel);

    window.pack();
    window.setVisible(true);

    // fill the circle with yellow color
    int yellow = packRgb(255,255,0);
    int x=50, y=50;  // make sure (x,y) is within the circle
    floodFill(image,x,y, yellow); 

    imageLabel.setIcon(new ImageIcon(image));
    imageLabel.setText("Completed !");

  }
}

Thanks for reading. Comments are welcome.

How to write a sudoku generator ?

The idea is to start with an empty grid. Then repeatedly fill a random digit to a random cell, until a valid puzzle is produced. A puzzle is valid if it has a unique solution. The number of solution can be found using a modified version of SudokuSolver.java described in the previous article.

To compile :

javac SudokuGenerator.java

To run, you must supply an integer seed :

java SudokuGenerator 0

The file out.txt will be generated :

Puzzle in plain text format :
.....2...
1.6....39
....6.5.1
....9....
.........
..9.2....
.9...4...
.....5...
...6.8...

Puzzle in Java String format :
    String puzzle = ".....2..."+
                    "1.6....39"+
                    "....6.5.1"+
                    "....9...."+
                    "........."+
                    "..9.2...."+
                    ".9...4..."+
                    ".....5..."+
                    "...6.8...";

Supplying a different seed will generate a different puzzle.

Full source can be found here : SudokuGenerator.java

Thanks for reading. Comments are welcome.

Patching

A reader's comment pointed out that there are two issues.
The fix is now available at :
Sudoku Generator - A Bug Fixing Patch

Sudoku Solver Part 2

The previous article presents how to solve a sudoku puzzle by the method of elimination.

The method of elimination is derived directly from the rule of sudoku :

1. Row Elimination : No cells in the same row are allowed to contain duplicate digits
2. Column Elimination : No cells in the same column are allowed to contain duplicate digits
3. Region Elimination : No cells in a region are allowed to contain duplicate digits

The above elimination process can solve some simple sudoku puzzles. Some complex puzzles cannot be solved, but would be simplified by the elimination process.

For simple puzzle solvable by the method of elimination, the sudoku solver can quit immediately.
The following is a puzzle solvable by elimination only :

//
    String puzzle= ".4.61..9."+
                   ".7..5...."+
                   "1.3948..."+
                   "961.....2"+
                   "..58261.."+
                   "8.....365"+
                   "...3792.4"+
                   "....8..5."+
                   ".8..65.3.";

And the solution is :

After all eliminations:
2       |4       |8       |6       |1       |7       |5       |9       |3

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

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

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

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

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

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

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

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

The following is a puzzle not solvable by elimination alone :

//
    String puzzle= "9.1..4..."+
                   "......296"+
                   ".8....4.7"+
                   "21...6..."+
                   "..6.23..4"+
                   ".5.94...."+
                   ".....8.4."+
                   "....7..3."+
                   "....316.5";

The result after all eliminations is :

After all eliminations:
9       |2367    |1       |23678   |68      |4       |358     |58      |38

347     |347     |347     |1378    |18      |5       |2       |9       |6

356     |8       |235     |1236    |169     |29      |4       |15      |7

2       |1       |34789   |58      |58      |6       |35789   |578     |389

78      |79      |6       |158     |2       |3       |15789   |1578    |4

38      |5       |38      |9       |4       |7       |138     |1268    |1238

13567   |23679   |23579   |256     |569     |8       |179     |4       |129

14568   |2469    |24589   |2456    |7       |29      |189     |3       |1289

478     |2479    |24789   |24      |3       |1       |6       |278     |5

Puzzle solvable by method of eliminations : false

Checking puzzle states

For the above simplified puzzle, it can be solved by a recursive "trial and error" algorithm.
Before entering the recursive search routine, we need to check whether the puzzle had already been solved by the method of eliminations.

A straight forward way is just to count the number of possible values in every cell, if all of them have only one possible value, then all cells are solved cells.

// check whether the puzzle is solved
  public boolean isSolved()
  {
    boolean solved=true;
    for (int i=0;i<81;i++)
    {
      if (cells[i].size()!=1) { solved=false; break; }
    }
    return solved;
  }

Method of Recursion

This method is based on trial an error. The algorithm of the Recursive Solver is :

1. Find next unsolved cell in the puzzle (cell with more than one possible values)
2. We will name this cell as 'X'. Fill cell X with one of the possible value(a trial)
3. call solveByElimination()
4. If the puzzle is solved, return true
5. check for conflict (a puzzle is in conflict state if the elimination process eliminates all possible values of some cells)
6. If the puzzle is not solved and not in conflict state, call the recursive solver to do a trial and error on the next unsolved cell
   
7. If the puzzle is not solved, fill cell X with next possible value, then go to step 3
   
8. If all possible values of cell X is tried, return false, this tells the parent that the puzzle cannot be solved
   

The actual java code follows :

//
  public boolean solveByRecursion()
  {
    // before doing anything, backup the puzzle first
    ArrayList<Integer>[] backupCells=new ArrayList[81];
    for (int i=0;i<81;i++) // allocate back structure
    {
      backupCells[i]=new ArrayList();
    }
 
    cellCopy(cells, backupCells);  // backup
    
    // get next unsolved cell
    int unsolvedCellIndex=-1;
    for (int i=0;i<81;i++)
    {
      if (cells[i].size()>1) { unsolvedCellIndex=i; break; }
    }

    // no unsolved cell, the puzzle is solved
    if (unsolvedCellIndex==-1) return true;

    for (int j=0;j<cells[unsolvedCellIndex].size();j++) // try all possible digits
    {       
      Integer digit = cells[unsolvedCellIndex].get(j); 
      cells[unsolvedCellIndex].clear();  // clear all values
      cells[unsolvedCellIndex].add(digit);  // then fill it with only one value         
      solveByElimination();
      if (isSolved()) return true;  // solved
      if (!isConflict()) 
      {
        // The unsolved cell is filled with a trial value, but the puzzle is not solved,
        // call myself recursively to do a trial and error on another unsolved cell.
        if (solveByRecursion()) return true; // solved        
      }
      // the trial digit cannot solve the puzzle
      cellCopy(backupCells,cells); // restore from backup, try next digit
    }
    // all values of a cell have been tried 
    return false;   // cannot solve this way.
  }

The solution of the sample puzzle presented above is :

9       |2       |1       |7       |6       |4       |3       |5       |8       
4       |3       |7       |8       |1       |5       |2       |9       |6       
6       |8       |5       |3       |9       |2       |4       |1       |7       
2       |1       |4       |5       |8       |6       |9       |7       |3       
7       |9       |6       |1       |2       |3       |5       |8       |4       
3       |5       |8       |9       |4       |7       |1       |6       |2       
1       |6       |3       |2       |5       |8       |7       |4       |9       
5       |4       |2       |6       |7       |9       |8       |3       |1       
8       |7       |9       |4       |3       |1       |6       |2       |5       
Puzzle solvable by method of recursion : true

More sample puzzles here :

// sample puzzle 1
    String puzzle= ".9..76.1."+
                   ".374....."+
                   ".......57"+
                   ".2..54..."+
                   "....6.9.5"+
                   ".1.9.3..."+
                   ".5.31..4."+
                   "..4..2..."+
                   "1.9....8.";

// sample puzzle 2
   String puzzle= "........."+
                  ".13.94..8"+
                  "8..5.2..."+
                  ".498..2.7"+
                  ".....1.83"+
                  "13......5"+
                  "2...7...6"+
                  ".6......."+
                  "..72.53..";

The full source code can be view here : SudokuSolver.java

Thanks for reading. Comments are welcome.

How to write a sudoku solver ?

Sudoku is a number-placement puzzle.

If you don't know what is sudoku, try googling for "sudoku wiki".

First we define the data structures for holding the puzzle.
A sudoku puzzle contains a grid of 81 cells, we may label it in a row major order :

0

1

2

9

10

11

18

19

20

3

4

5

12

13

14

21

22

23

6

7

8

15

16

17

24

25

26

27

28

29

36

37

38

45

46

47

30

31

32

39

40

41

48

49

50

33

34

35

42

43

44

51

52

53

54

55

56

63

64

65

72

73

74

57

58

59

66

67

68

75

76

77

60

61

62

69

70

71

78

79

80

That is naturally implemented by a one-dimensional array.

// structure for holding sudoku grid
  int[] cells=new int[81];

Normally a cell would contains one digit only, but that is true for a solved puzzle only.
Before the puzzle is completely solved, some cells may contains more than one possible values, it is desirable to store all the possible values of a cell. Hence each cell should hold a integer list.

For this reason, we change the simple integer array implementation.

// structure for holding sudoku grid
  ArrayList<Integer>[] cells=new ArrayList[81];

Roughly speaking, there are three constraints for filling the cells.
1. No duplicate digits allowed in the same row
2. No duplicate digits allowed in the same column
3. No duplicate digits allowed in the same region.

It is obvious that we need some data structures to represent the row, column and region.

We may group the cell label to form a row. A row is actually a list of indices to the cell array.

For example, the first row would be :
{ 0, 1, 2, 3, 4, 5, 6, 7, 8}

The second row would be :
{ 9,10,11,12,13,14,15,16,17}

A column can be defined in a similar way.

The first column is :
{0,9,18,27,36,45,54,63,72}

and the last column would be :
{8,17,26,35,44,53,62,71,80}

Region can be defined in a similar way.
The upperleft region contains 9 cells :
{0,1,2 ,9,10,11, 18,19,20}


The full data structure would be :

// structure for holding sudoku grid
  ArrayList<Integer>[] cells=new ArrayList[81];
  
  private int[][] row=new int[][] {
    { 0, 1, 2, 3, 4, 5, 6, 7, 8}, // row 0
    { 9,10,11,12,13,14,15,16,17}, // row 1
    {18,19,20,21,22,23,24,25,26}, // row 2
    {27,28,29,30,31,32,33,34,35}, // row 3
    {36,37,38,39,40,41,42,43,44}, // row 4
    {45,46,47,48,49,50,51,52,53}, // row 5
    {54,55,56,57,58,59,60,61,62}, // row 6
    {63,64,65,66,67,68,69,70,71}, // row 7
    {72,73,74,75,76,77,78,79,80}  // row 8
  };

  private int[][] column=new int[][] {
    { 0, 9,18,27,36,45,54,63,72}, // column 0
    { 1,10,19,28,37,46,55,64,73}, // column 1
    { 2,11,20,29,38,47,56,65,74}, // column 2
    { 3,12,21,30,39,48,57,66,75}, // column 3
    { 4,13,22,31,40,49,58,67,76}, // column 4
    { 5,14,23,32,41,50,59,68,77}, // column 5
    { 6,15,24,33,42,51,60,69,78}, // column 6
    { 7,16,25,34,43,52,61,70,79}, // column 7
    { 8,17,26,35,44,53,62,71,80}  // column 8
  };

  private int[][] region=new int[][] {
    { 0, 1, 2, 9,10,11,18,19,20}, // region 0, upper left region (North West)
    { 3, 4, 5,12,13,14,21,22,23}, // region 1, top region (North)
    { 6, 7, 8,15,16,17,24,25,26}, // region 2, upper right region (North East)
    {27,28,29,36,37,38,45,46,47}, // region 3, left region (west)
    {30,31,32,39,40,41,48,49,50}, // region 4, middle region
    {33,34,35,42,43,44,51,52,53}, // region 5, right region (east)
    {54,55,56,63,64,65,72,73,74}, // region 6, lower left region (South West)
    {57,58,59,66,67,68,75,76,77}, // region 7, bottom region (south)
    {60,61,62,69,70,71,78,79,80}  // region 8, lower right right (South East)
  };

Next we define a problem, suppose we want to solve the following puzzle :

4

7

1

3

6

1

5

9

4

8

9

9

6

1

5

8

8

2

6

2

1

3

6

5

8

3

7

9

8

6

5

2

4

5

3

The puzzle can be represented by a String :

String puzzle =  ".4.61..9."+
                 ".7..5...."+
                 "1.3948..."+
                 "961.....2"+
                 "..58261.."+
                 "8.....365"+
                 "...3792.4"+
                 "....8..5."+
                 ".8..65.3.";
  

To solve another puzzle, just change the content of the puzzle String.

It is not difficult to read the puzzle through command line parameter or read it from a file.

For simplicity purpose, I am not going to mess up the source code and just hard code the puzzle string.


Next, initialize all possible values of each cell, according to the puzzle.

//
  public void init(String puzzle)
  {
    for (int i=0;i<81;i++)
    {
      cells[i]=new ArrayList<Integer>();
      String s=puzzle.substring(i,i+1);
      if (s.equals("."))  // unsolved cells, all values are possible
        for (int digit=1;digit<=9;digit++) cells[i].add(digit);
      else  // solved cells, only one possible value
        cells[i].add(Integer.parseInt(s));
    }
  }

Then print the grid :

// display all possible of the grid
  public void printGrid()
  {
    String delimiter="";

    for (int i=0;i<81;i++)
    {
      String s="";
      for (int j=0;j<cells[i].size();j++)
      {
        s+=cells[i].get(j);
      }
      // make sure each cell contains exactly 8 character
      for (int j=0;j<8-cells[i].size();j++) s+=" ";
     
      if (s.length()>8) s="ALL     ";  // overflow
      s=delimiter+s;
      delimiter="|";
      System.out.print(s);
      if ((i+1)%9==0) { System.out.println(); delimiter=""; }
    }
  }

Here is our first version of sudoku solver, it only display the problem grid :

/******************************************************************************
* File : SudokuSolver.java (Version 1)
* Author : http://java.macteki.com/
* Description :
*   A sudoku solver. (just display the puzzle grid)
* Tested with : JDK 1.6
******************************************************************************/

import java.util.ArrayList;
import java.lang.reflect.Array;

public class SudokuSolver
{
  // structure for holding sudoku grid
  ArrayList<Integer>[] cells=new ArrayList[81];
  
  private int[][] row=new int[][] {
    { 0, 1, 2, 3, 4, 5, 6, 7, 8}, // row 0
    { 9,10,11,12,13,14,15,16,17}, // row 1
    {18,19,20,21,22,23,24,25,26}, // row 2
    {27,28,29,30,31,32,33,34,35}, // row 3
    {36,37,38,39,40,41,42,43,44}, // row 4
    {45,46,47,48,49,50,51,52,53}, // row 5
    {54,55,56,57,58,59,60,61,62}, // row 6
    {63,64,65,66,67,68,69,70,71}, // row 7
    {72,73,74,75,76,77,78,79,80}  // row 8
  };

  private int[][] column=new int[][] {
    { 0, 9,18,27,36,45,54,63,72}, // column 0
    { 1,10,19,28,37,46,55,64,73}, // column 1
    { 2,11,20,29,38,47,56,65,74}, // column 2
    { 3,12,21,30,39,48,57,66,75}, // column 3
    { 4,13,22,31,40,49,58,67,76}, // column 4
    { 5,14,23,32,41,50,59,68,77}, // column 5
    { 6,15,24,33,42,51,60,69,78}, // column 6
    { 7,16,25,34,43,52,61,70,79}, // column 7
    { 8,17,26,35,44,53,62,71,80}  // column 8
  };

  private int[][] region=new int[][] {
    { 0, 1, 2, 9,10,11,18,19,20}, // region 0, upper left region (North West)
    { 3, 4, 5,12,13,14,21,22,23}, // region 1, top region (North)
    { 6, 7, 8,15,16,17,24,25,26}, // region 2, upper right region (North East)
    {27,28,29,36,37,38,45,46,47}, // region 3, left region (west)
    {30,31,32,39,40,41,48,49,50}, // region 4, middle region
    {33,34,35,42,43,44,51,52,53}, // region 5, right region (east)
    {54,55,56,63,64,65,72,73,74}, // region 6, lower left region (South West)
    {57,58,59,66,67,68,75,76,77}, // region 7, bottom region (south)
    {60,61,62,69,70,71,78,79,80}  // region 8, lower right right (South East)
  };


  public void init(String puzzle)
  {
    for (int i=0;i<81;i++)
    {
      cells[i]=new ArrayList<Integer>();
      String s=puzzle.substring(i,i+1);
      if (s.equals("."))  // unsolved cells, all values are possible
        for (int digit=1;digit<=9;digit++) cells[i].add(digit);
      else  // solved cells, only one possible value
        cells[i].add(Integer.parseInt(s));
    }
  }

  // display all possible of the grid
  public void printGrid()
  {
    String delimiter="";

    for (int i=0;i<81;i++)
    {
      String s="";
      for (int j=0;j<cells[i].size();j++)
      {
        s+=cells[i].get(j);
      }
      // make sure each cell contains exactly 8 character
      for (int j=0;j<8-cells[i].size();j++) s+=" ";
     
      if (s.length()>8) s="ALL     ";  // overflow
      s=delimiter+s;
      delimiter="|";
      System.out.print(s);
      if ((i+1)%9==0) { System.out.println(); delimiter=""; }
    }
  }



  public static void main(String[] args) throws Exception
  {
    // change this String for another puzzle
    String puzzle= ".4.61..9."+
                   ".7..5...."+
                   "1.3948..."+
                   "961.....2"+
                   "..58261.."+
                   "8.....365"+
                   "...3792.4"+
                   "....8..5."+
                   ".8..65.3.";

    SudokuSolver solver=new SudokuSolver();
    solver.init(puzzle);
    solver.printGrid();
  }
}

Row Elimination

The next step is to make sure all rows cannot have duplicate digits. If a cell contains only one possible digit, it is a solved cell. For each solved cell, check which row it belongs to, then remove the solved digit from every cells in the row.

// eliminate duplicate digit of the same rows
  public void rowElimination()
  {
    for (int i=0;i<81;i++) // loop over all cells
    {
      int n=cells[i].size(); // get number of possible values of current cell
      if (n==1)  // this is a solved cell
      {
        int solvedDigit=cells[i].get(0);
        int rowNumber=i/9;   // which row does the current cell belong to ?        
        for (int j=0;j<9;j++)  // loop over all cells in the affected row
        {
          int cellNum=row[rowNumber][j];
          // all other cells in the row cannot contain the solved digit
          if (cellNum!=i) cells[cellNum].remove(new Integer(solvedDigit));
        }
      }
    }
  }

Look at the first row of the puzzle, the digit "4","6","1" and "9" are solved, hence all unsolved cells in the row cannot have the possible value of "4","6","1","9", that means the unsolved cells must be "2","3","5","7" or "8". After row elimination, the puzzle should be simplified as follows (every cell shows the possible digits):

23578   |4       |23578   |6       |1       |23578   |23578   |9       |23578

1234689 |7       |1234689 |1234689 |5       |1234689 |1234689 |1234689 |1234689

1       |2567    |3       |9       |4       |8       |2567    |2567    |2567

9       |6       |1       |34578   |34578   |34578   |34578   |34578   |2

3479    |3479    |5       |8       |2       |6       |1       |3479    |3479

8       |12479   |12479   |12479   |12479   |12479   |3       |6       |5

1568    |1568    |1568    |3       |7       |9       |2       |1568    |4

1234679 |1234679 |1234679 |1234679 |8       |1234679 |1234679 |5       |1234679

12479   |8       |12479   |12479   |6       |5       |12479   |3       |12479

The following is the program that produce the above row eliminated output :

/******************************************************************************
* File : SudokuSolver.java
* Author : http://java.macteki.com/
* Description :
*   A sudoku solver.
* Tested with : JDK 1.6
******************************************************************************/

import java.util.ArrayList;
import java.lang.reflect.Array;

public class SudokuSolver
{
  // structure for holding sudoku grid
  ArrayList<Integer>[] cells=new ArrayList[81];
  
  private int[][] row=new int[][] {
    { 0, 1, 2, 3, 4, 5, 6, 7, 8}, // row 0
    { 9,10,11,12,13,14,15,16,17}, // row 1
    {18,19,20,21,22,23,24,25,26}, // row 2
    {27,28,29,30,31,32,33,34,35}, // row 3
    {36,37,38,39,40,41,42,43,44}, // row 4
    {45,46,47,48,49,50,51,52,53}, // row 5
    {54,55,56,57,58,59,60,61,62}, // row 6
    {63,64,65,66,67,68,69,70,71}, // row 7
    {72,73,74,75,76,77,78,79,80}  // row 8
  };

  private int[][] column=new int[][] {
    { 0, 9,18,27,36,45,54,63,72}, // column 0
    { 1,10,19,28,37,46,55,64,73}, // column 1
    { 2,11,20,29,38,47,56,65,74}, // column 2
    { 3,12,21,30,39,48,57,66,75}, // column 3
    { 4,13,22,31,40,49,58,67,76}, // column 4
    { 5,14,23,32,41,50,59,68,77}, // column 5
    { 6,15,24,33,42,51,60,69,78}, // column 6
    { 7,16,25,34,43,52,61,70,79}, // column 7
    { 8,17,26,35,44,53,62,71,80}  // column 8
  };

  private int[][] region=new int[][] {
    { 0, 1, 2, 9,10,11,18,19,20}, // region 0, upper left region (North West)
    { 3, 4, 5,12,13,14,21,22,23}, // region 1, top region (North)
    { 6, 7, 8,15,16,17,24,25,26}, // region 2, upper right region (North East)
    {27,28,29,36,37,38,45,46,47}, // region 3, left region (west)
    {30,31,32,39,40,41,48,49,50}, // region 4, middle region
    {33,34,35,42,43,44,51,52,53}, // region 5, right region (east)
    {54,55,56,63,64,65,72,73,74}, // region 6, lower left region (South West)
    {57,58,59,66,67,68,75,76,77}, // region 7, bottom region (south)
    {60,61,62,69,70,71,78,79,80}  // region 8, lower right right (South East)
  };


  public void init(String puzzle)
  {
    for (int i=0;i<81;i++)
    {
      cells[i]=new ArrayList<Integer>();
      String s=puzzle.substring(i,i+1);
      if (s.equals("."))  // unsolved cells, all values are possible
        for (int digit=1;digit<=9;digit++) cells[i].add(digit);
      else  // solved cells, only one possible value
        cells[i].add(Integer.parseInt(s));
    }
  }

  // display all possible of the grid
  public void printGrid()
  {
    String delimiter="";

    for (int i=0;i<81;i++)
    {
      String s="";
      for (int j=0;j<cells[i].size();j++)
      {
        s+=cells[i].get(j);
      }
      // make sure each cell contains exactly 8 character
      for (int j=0;j<8-cells[i].size();j++) s+=" ";
     
      if (s.length()>8) s="ALL     ";  // overflow
      s=delimiter+s;
      delimiter="|";
      System.out.print(s);
      if ((i+1)%9==0) { System.out.println(); delimiter=""; }
    }
  }


  // eliminate duplicate digit of the same rows
  public void rowElimination()
  {
    for (int i=0;i<81;i++) // loop over all cells
    {
      int n=cells[i].size(); // get number of possible values of current cell
      if (n==1)  // this is a solved cell
      {
        int solvedDigit=cells[i].get(0);
        int rowNumber=i/9;   // which row does the current cell belong to ?        
        for (int j=0;j<9;j++)  // loop over all cells in the affected row
        {
          int cellNum=row[rowNumber][j];
          // all other cells in the row cannot contain the solved digit
          if (cellNum!=i) cells[cellNum].remove(new Integer(solvedDigit));
        }
      }
    }
  }

  public static void main(String[] args) throws Exception
  {
    // change this String for another puzzle
    String puzzle= ".4.61..9."+
                   ".7..5...."+
                   "1.3948..."+
                   "961.....2"+
                   "..58261.."+
                   "8.....365"+
                   "...3792.4"+
                   "....8..5."+
                   ".8..65.3.";

    SudokuSolver solver=new SudokuSolver();
    solver.init(puzzle);
    solver.printGrid();

    solver.rowElimination();
    System.out.println("After row elimination:");
    solver.printGrid();

  }
}

Column Elimination

This is very similar to the row elimination, if a cell is solved, just remove the solved digit from the possible values of all cells in the same column.

// eliminate duplicate digit of the same column
  public void columnElimination()
  {
    for (int i=0;i<81;i++) // loop over all cells
    {
      int n=cells[i].size(); // get number of possible values of current cell
      if (n==1)  // this is a solved cell
      {
        int solvedDigit=cells[i].get(0);
        int columnNumber=i % 9;   // which column does the current cell belong to ?        
        for (int j=0;j<9;j++)  // loop over all cells in the affected column
        {
          int cellNum=column[columnNumber][j];
          // all other cells in the column cannot contain the solved digit
          if (cellNum!=i) cells[cellNum].remove(new Integer(solvedDigit));
        }
      }
    }
  }

The problem is further simplified after column elimination :

2357    |4       |278     |6       |1       |237     |578     |9       |378

2346    |7       |24689   |124     |5       |1234    |4689    |1248    |13689

1       |25      |3       |9       |4       |8       |567     |27      |67

9       |6       |1       |457     |3       |347     |4578    |478     |2

347     |39      |5       |8       |2       |6       |1       |47      |379

8       |129     |2479    |1247    |9       |1247    |3       |6       |5

56      |15      |68      |3       |7       |9       |2       |18      |4

23467   |1239    |24679   |1247    |8       |12347   |4679    |5       |13679

247     |8       |2479    |1247    |6       |5       |479     |3       |179

Region Elimination

Each region cannot contains duplicate digit. It is a little bit tricky to find which region a cell belongs to. For example, cell number 0 belongs to region 0 (upper left) cell number 80 belongs to region 8 (lower right) Finding the row number and column number are relatively easy.

int rowNumber = cellIndex / 9;    // which row does the current cell belong to ?        
int columnNumber=cellIndex % 9;   // which column does the current cell belong to ?        

Actually, the region number can be found from rowNumber and columnNumber :

int regionNumber=3*(rowNumber/3) + columnNumber/3;

Think carefully and make sure you understand the above formula. Source code for region elimination :

// eliminate duplicate digit of the same region
  public void regionElimination()
  {
    for (int i=0;i<81;i++) // loop over all cells
    {
      int n=cells[i].size(); // get number of possible values of current cell
      if (n==1)  // this is a solved cell
      {
        int solvedDigit=cells[i].get(0);
        int rowNumber = i / 9;    // which row does the current cell belong to ?        
        int columnNumber=i % 9;   // which column does the current cell belong to ?        
        int regionNumber=3*(rowNumber/3) + columnNumber/3;
        for (int j=0;j<9;j++)  // loop over all cells in the affected region
        {
          int cellNum=region[regionNumber][j];
          // all other cells in the region cannot contain the solved digit
          if (cellNum!=i) cells[cellNum].remove(new Integer(solvedDigit));
        }
      }
    }
  }

After region elimination, the problem is further simplifed to :

25      |4       |28      |6       |1       |237     |578     |9       |378

26      |7       |2689    |2       |5       |23      |468     |1248    |1368

1       |25      |3       |9       |4       |8       |567     |27      |67

9       |6       |1       |457     |3       |47      |478     |478     |2

47      |3       |5       |8       |2       |6       |1       |47      |79

8       |2       |47      |147     |9       |147     |3       |6       |5

56      |15      |6       |3       |7       |9       |2       |18      |4

23467   |1239    |24679   |124     |8       |124     |679     |5       |1679

247     |8       |2479    |124     |6       |5       |79      |3       |179

Note that newly solved cells are generated after the three eliminations. Repeat the process until no more newly solved cells are found. Some problems can be solved by eliminations only, some cannot. For those puzzles which cannot be solved by eliminations only, we would still simplify the problem by elimination, then solve them by a trial and error algorithm. Full source code and solution of the puzzles follows :

/******************************************************************************
* File : SudokuSolver.java
* Author : http://java.macteki.com/
* Description :
*   A sudoku solver.
* Tested with : JDK 1.6
******************************************************************************/

import java.util.ArrayList;
import java.lang.reflect.Array;

public class SudokuSolver
{
  // structure for holding sudoku grid
  ArrayList<Integer>[] cells=new ArrayList[81];
  
  private int[][] row=new int[][] {
    { 0, 1, 2, 3, 4, 5, 6, 7, 8}, // row 0
    { 9,10,11,12,13,14,15,16,17}, // row 1
    {18,19,20,21,22,23,24,25,26}, // row 2
    {27,28,29,30,31,32,33,34,35}, // row 3
    {36,37,38,39,40,41,42,43,44}, // row 4
    {45,46,47,48,49,50,51,52,53}, // row 5
    {54,55,56,57,58,59,60,61,62}, // row 6
    {63,64,65,66,67,68,69,70,71}, // row 7
    {72,73,74,75,76,77,78,79,80}  // row 8
  };

  private int[][] column=new int[][] {
    { 0, 9,18,27,36,45,54,63,72}, // column 0
    { 1,10,19,28,37,46,55,64,73}, // column 1
    { 2,11,20,29,38,47,56,65,74}, // column 2
    { 3,12,21,30,39,48,57,66,75}, // column 3
    { 4,13,22,31,40,49,58,67,76}, // column 4
    { 5,14,23,32,41,50,59,68,77}, // column 5
    { 6,15,24,33,42,51,60,69,78}, // column 6
    { 7,16,25,34,43,52,61,70,79}, // column 7
    { 8,17,26,35,44,53,62,71,80}  // column 8
  };

  private int[][] region=new int[][] {
    { 0, 1, 2, 9,10,11,18,19,20}, // region 0, upper left region (North West)
    { 3, 4, 5,12,13,14,21,22,23}, // region 1, top region (North)
    { 6, 7, 8,15,16,17,24,25,26}, // region 2, upper right region (North East)
    {27,28,29,36,37,38,45,46,47}, // region 3, left region (west)
    {30,31,32,39,40,41,48,49,50}, // region 4, middle region
    {33,34,35,42,43,44,51,52,53}, // region 5, right region (east)
    {54,55,56,63,64,65,72,73,74}, // region 6, lower left region (South West)
    {57,58,59,66,67,68,75,76,77}, // region 7, bottom region (south)
    {60,61,62,69,70,71,78,79,80}  // region 8, lower right right (South East)
  };


  public void init(String puzzle)
  {
    for (int i=0;i<81;i++)
    {
      cells[i]=new ArrayList<Integer>();
      String s=puzzle.substring(i,i+1);
      if (s.equals("."))  // unsolved cells, all values are possible
        for (int digit=1;digit<=9;digit++) cells[i].add(digit);
      else  // solved cells, only one possible value
        cells[i].add(Integer.parseInt(s));
    }
  }

  // display all possible of the grid
  public void printGrid()
  {
    String delimiter="";

    for (int i=0;i<81;i++)
    {
      String s="";
      for (int j=0;j<cells[i].size();j++)
      {
        s+=cells[i].get(j);
      }
      // make sure each cell contains exactly 8 character
      for (int j=0;j<8-cells[i].size();j++) s+=" ";
     
      if (s.length()>8) s="ALL     ";  // overflow
      s=delimiter+s;
      delimiter="|";
      System.out.print(s);
      if ((i+1)%9==0) { System.out.println(); delimiter=""; }
    }
  }


  // eliminate duplicate digit of the same row
  public boolean rowElimination()
  {
    boolean newSolved=false;
    for (int i=0;i<81;i++) // loop over all cells
    {
      int n=cells[i].size(); // get number of possible values of current cell
      if (n==1)  // this is a solved cell
      {
        Integer solvedDigit=cells[i].get(0);
        int rowNumber=i/9;   // which row does the current cell belong to ?        
        for (int j=0;j<9;j++)  // loop over all cells in the affected row
        {
          int cellNum=row[rowNumber][j];
          // all other cells in the row cannot contain the solved digit
          if (cellNum!=i && cells[cellNum].contains(solvedDigit)) 
          {
            cells[cellNum].remove(solvedDigit);
            if (cells[cellNum].size()==1) newSolved=true;  // newly solved cell found
          }
        }
      }
    }
    return newSolved;
  }

  // eliminate duplicate digit of the same column
  public boolean columnElimination()
  {
    boolean newSolved=false;
    for (int i=0;i<81;i++) // loop over all cells
    {
      int n=cells[i].size(); // get number of possible values of current cell
      if (n==1)  // this is a solved cell
      {
        Integer solvedDigit=cells[i].get(0);
        int columnNumber=i % 9;   // which column does the current cell belong to ?        
        for (int j=0;j<9;j++)  // loop over all cells in the affected column
        {
          int cellNum=column[columnNumber][j];
          // all other cells in the column cannot contain the solved digit
          if (cellNum!=i && cells[cellNum].contains(solvedDigit)) 
          {
            cells[cellNum].remove(solvedDigit);
            if (cells[cellNum].size()==1) newSolved=true;  // newly solved cell found
          }
        }
      }
    }
    return newSolved;
  }

  // eliminate duplicate digit of the same region
  public boolean regionElimination()
  {
    boolean newSolved=false;
    for (int i=0;i<81;i++) // loop over all cells
    {
      int n=cells[i].size(); // get number of possible values of current cell
      if (n==1)  // this is a solved cell
      {
        Integer solvedDigit=cells[i].get(0);
        int rowNumber = i / 9;    // which row does the current cell belong to ?        
        int columnNumber=i % 9;   // which column does the current cell belong to ?        
        int regionNumber=3*(rowNumber/3) + columnNumber/3;
        for (int j=0;j<9;j++)  // loop over all cells in the affected region
        {
          int cellNum=region[regionNumber][j];
          // all other cells in the region cannot contain the solved digit
          if (cellNum!=i && cells[cellNum].contains(solvedDigit))
          {
            cells[cellNum].remove(solvedDigit);
            if (cells[cellNum].size()==1) newSolved=true;  // newly solved cell found
          }
        }
      }
    }
    return newSolved;
  }


  public void solveByElimination()
  {
    boolean newCellSolved=false;
    while (true)
    {
      newCellSolved=false;
      if (rowElimination()) newCellSolved=true;
      if (columnElimination()) newCellSolved=true;
      if (regionElimination()) newCellSolved=true;
      if (!newCellSolved) break;  // no newly solved cell generated, quit
    }
  }

  public static void main(String[] args) throws Exception
  {
    // change this String for another puzzle
    String puzzle= ".4.61..9."+
                   ".7..5...."+
                   "1.3948..."+
                   "961.....2"+
                   "..58261.."+
                   "8.....365"+
                   "...3792.4"+
                   "....8..5."+
                   ".8..65.3.";

    SudokuSolver solver=new SudokuSolver();
    solver.init(puzzle);
    solver.printGrid();

    solver.solveByElimination();

    System.out.println("After all eliminations:");
    solver.printGrid();

  }
}

Solution of the problems :

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

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

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

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

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

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

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

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

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

Summary

This article presents a java sample for solving sudoku by method of elimination.
Note that some complex puzzle cannot be solved by this sample. However, those puzzle would be highly simplified by the program and it is not difficult to solve it by a trial and error method, which will be presented in the next article.

Thanks for reading. Comments are welcome.