Number Board - A Java Backtracking Algorithm

About the game

What to do when you're in a boring class? Try to solve this puzzle! Just try to fill in a 10 by 10 rectangle with all the numbers from 1 till 100. If you're a computer freak this should be 0 till 99 of course... Now... This one is too easy! Let's make some more rules.

After you've put one number (the red box) on the rectangle, the next number should be on one of the marked locations relative to the red number.

I Think that's all... Try it!

The Applet

How to use this one?

Enter the board size
Hit the NEW button
Select the starting rectangle using the mouse
Hit the STEP or SOLUTION button
Select ANIMATE if you're too lazy to hit the step/solution buttons all the time.

The Algorithm

The algorithm is a classic one. It's a backtracking algorithme using one recursive call. I'm not going to give a very long explanation right here. If you are curious, you can take a look at the next lines or you can download the Java source.

public void Generate(int x, int y, int num) {
    int nx, ny, dir;
    if (num >= mxsize) {
        System.out.println("Next solution:");
        board.output(System.out);
        return;
    } else {
        dir = 0;
        while (dir < NumDir) {
            nx = x + xAdd(dir);
            ny = y + yAdd(dir);
            dir++;
            if (board.isAvailable(nx,ny)) {
                board.set(nx,ny,num);
                Generate(nx,ny,num+1);
                board.reset(nx,ny);
            }
        }
    }
}

The source

What's next?

Home
My java Page

By Jan Struyf, 22/03/98