当前位置:首页 » Project Euler » 详细页

Criss Cross 题号:166 难度: 50 中英对照

A 4x4 grid is filled with digits d, 0 ≤ d ≤ 9.

It can be seen that in the grid

6 3 3 0
5 0 4 3
0 7 1 4
1 2 4 5

the sum of each row and each column has the value 12. Moreover the sum of each diagonal is also 12.

In how many ways can you fill a 4x4 grid with the digits d, 0 ≤ d ≤ 9 so that each row, each column, and both diagonals have the same sum?

Solution

枚举所有的有序四元组$(a_0,a_1,a_2,a_3)$,将其和记录下来。 枚举所有可能的和$sum$,从所有和为$sum$的有序四元组中选取3个填入前三行,第四行可以直接由$sum$和前三行的数字计算得出。 判断第四行的数字是否合法、斜线和第四行的和是否为$sum$即可。

Code

public final class p166 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }
	
    final static int N = 4;
	final static int[][][] sum = new int[9 * N + 1][701][N];
	
    static public String run() {
		int[] a = new int[N];
		for (a[0] = 0; a[0] < 10; ++a[0]) {
			for (a[1] = 0; a[1] < 10; ++a[1]) {
				for (a[2] = 0; a[2] < 10; ++a[2]) {
					for (a[3] = 0; a[3] < 10; ++a[3]) {
						int[][] s2 = sum[a[0] + a[1] + a[2] + a[3]];
						System.arraycopy(a, 0, s2[s2[700][0]++], 0, N);
					}
				}
			}
		}
		int cnt = 0;
		for (int sum1 = 0; sum1 <= 9 * N; ++sum1) {
			int LIM = sum[sum1][700][0];
			int[][] AR = sum[sum1];
			for (int i = 0; i < LIM; ++i) {
				for (int j = 0; j < LIM; ++j) {
					for (int k = 0; k < LIM; ++k) {
						a[0] = sum1 - AR[k][0] - AR[j][0] - AR[i][0];
						if (a[0] < 0
								|| a[0] > 9
								|| a[0] != sum1 - AR[i][3] - AR[j][2]
										- AR[k][1])
							continue;
						a[3] = sum1 - AR[k][3] - AR[j][3] - AR[i][3];
						if (a[3] < 0
								|| a[3] > 9
								|| a[3] != sum1 - AR[i][0] - AR[j][1]
										- AR[k][2])
							continue;
						a[1] = sum1 - AR[k][1] - AR[j][1] - AR[i][1];
						if (a[1] < 0 || a[1] > 9)
							continue;
						a[2] = sum1 - AR[k][2] - AR[j][2] - AR[i][2];
						if (a[2] < 0 || a[2] > 9)
							continue;
						if (a[0] + a[1] + a[2] + a[3] == sum1)
							++cnt;
					}
				}
			}
		}
		return ""+cnt;
	}
}
7130034
36119ms