Count the number of six digit numbers possible

The problem is to calculate the number of 6-digit numbers that you can create using the following scheme of things.

0-9 digits are arranged like a phone keypad.
1 2 3
4 5 6
7 8 9
   0

The 6-digit number cannot start with 0. A digit can follow any other digit in the 6-digit number only if both the numbers are in the same row or column.
For eg. in a 6-digit number:
2 can follow 0
0 can follow 8
9 can follow 7
5 can follow 4
4 can follow 1
1 can follow 7
...
...
9 cannot follow 5
1 cannot follow 6
0 cannot follow 1
...
...

The idea of the solution is to use dynamic programming. A possible implementation is given below. To further optimize we can do memoization.

	/**
	* Author: Varun
	* Date: Apr 17, 2013
	*/
	public class SixDigitNumbers {
	static int[][] reachableNodes = {
	{0,0,1,0,0,1,0,0,1,0},
	{0,0,1,1,1,0,0,1,0,0},
	{1,1,0,1,0,1,0,0,1,0},
	{0,1,1,0,0,0,1,0,0,1},
	{0,1,0,0,0,1,1,1,0,0},
	{1,0,1,0,1,0,1,0,1,0},
	{0,0,0,1,1,1,0,0,0,1},
	{0,1,0,0,1,0,0,0,1,1},
	{1,0,1,0,0,1,0,1,0,1},
	{0,0,0,1,0,0,1,1,1,0}
	};
	public static int countNDigitNumbers(int n, int startWith) {
	int count = 0;
	if(n == 1) {
	return 1;
	}
	for(int i = 0; i <= 9; i++) {
	if(reachableNodes[startWith][i] == 1) {
	count += countNDigitNumbers(n-1, i);
	}
	}
	return count;
	}
	public static void main(String[] args) {
	int sixDigitNumberCount = 0;
	for(int i = 1; i <= 9; i++) {
	sixDigitNumberCount += countNDigitNumbers(6, i);
	}
	System.out.println("The Total: " + sixDigitNumberCount);
	}
	}

view raw SixDigitNumbers.java hosted with ❤ by GitHub