Sudoku

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 150    Accepted Submission(s): 61

Problem Description The puzzle game of Sudoku is played on a board of N^2 × N^2 cells. The cells are grouped in N × N squares of N × N cells each. Each cell is either empty or contains a number between 1 and N^2. The Sudoku position is correct when numbers in each row, each column and each square are different. The goal of the game is, starting from some correct positions; fill all empty cells so that the final position is still correct. (We call the final position is a solution to the starting position). This problem is not about to solve a specific Sudoku puzzle, but ask you to find all correct positions that have a unique solution when N = 2.  

 

Input There's no input for this problem.  

 

Output Output x on a single line where x is the number of correct positions have a unique solution when N = 2. 为了求得最终答案，我写了巨长的代码。 这是一个数独题目，大概有两步骤 1） 求得 N=2 的 288个解 2） 判断每一个解 添加空格后 独一无二的解的个数 ，算总和 心得： 1）记得要加上一个空格也没有的288个状态。 2）288个解要一个一个枚举，不是说每个解对应的加空格后独一无二的解个数都是一样的。 3）要是解独一无二，最多只能设置12个空格，即最少也要给定4个点来求解数独。 4）最后答案直接输出13579680即可。 代码 #include < stdio.h > #include < string .h > struct Point{ int x,y;}p[ 18 ]; int map[ 5 ][ 5 ],tmp[ 5 ][ 5 ]; // ={{1,2,3,4},{3,4,1,2,},{2,1,4,3,},{4,3,2,1}}; int ans,num,sum,total; int right[ 290 ][ 5 ][ 5 ]; // int map[5][5]={{1,2,3,4},{3,4,1,2,},{2,3,4,1,},{4,1,2,3}}; int ok( int q, int k){ int i,j,si,sj; for (i = 0 ;i < 4 ;i ++ ) if (map[p[q].x][i] == k && i != p[q].y) return 0 ; for (i = 0 ;i < 4 ;i ++ ) if (map[i][p[q].y] == k && i != p[q].x) return 0 ; si = p[q].x / 2 * 2 ; sj = p[q].y / 2 * 2 ; for (i = 0 ;i < 2 ;i ++ ) for (j = 0 ;j < 2 ;j ++ ) { if ((si + i) == p[q].x && (sj + j) == p[q].y) continue ; if (map[si + i][sj + j] == k) return 0 ; } return 1 ;} void dfs( int q){ int i; if (q == num) { ans ++ ; return ; } for (i = 1 ;i <= 4 ;i ++ ) if (ok(q,i)) { map[p[q].x][p[q].y] = i; dfs(q + 1 ); map[p[q].x][p[q].y] = 0 ; } return ;} void dfs2( int q){ int i,j; if (q == num) { for (i = 0 ;i < 4 ;i ++ ) { for (j = 0 ;j < 4 ;j ++ ) right[total][i][j] = map[i][j]; } total ++ ; return ; } for (i = 1 ;i <= 4 ;i ++ ) if (ok(q,i)) { map[p[q].x][p[q].y] = i; dfs2(q + 1 ); map[p[q].x][p[q].y] = 0 ; } return ;} void slove(){ int a,aa,b,bb,c,cc,d,dd,e,ee,f,ff,g,gg,h,hh,i,ii,j,jj; int k,kk,l,ll; int x,y; for (a = 0 ;a < 16 ;a ++ ) { aa = map[a / 4 ][a % 4 ]; map[a / 4 ][a % 4 ] = 0 ; p[ 0 ].x = a / 4 , p[ 0 ].y = a % 4 ; num = 1 ; ans = 0 ; dfs( 0 ); if (ans == 1 ) sum ++ ; map[a / 4 ][a % 4 ] = aa; } // printf("%d\n",sum+1); for (a = 0 ;a < 16 ;a ++ ) { aa = map[a / 4 ][a % 4 ]; map[a / 4 ][a % 4 ] = 0 ; p[ 0 ].x = a / 4 , p[ 0 ].y = a % 4 ; for (b = a + 1 ;b < 16 ;b ++ ) { bb = map[b / 4 ][b % 4 ]; map[b / 4 ][b % 4 ] = 0 ; p[ 1 ].x = b / 4 , p[ 1 ].y = b % 4 ; num = 2 ; ans = 0 ; dfs( 0 ); if (ans == 1 ) sum ++ ; map[b / 4 ][b % 4 ] = bb; } map[a / 4 ][a % 4 ] = aa; } // printf("%d\n",sum+1); for (a = 0 ;a < 16 ;a ++ ) { aa = map[a / 4 ][a % 4 ]; map[a / 4 ][a % 4 ] = 0 ; p[ 0 ].x = a / 4 , p[ 0 ].y = a % 4 ; for (b = a + 1 ;b < 16 ;b ++ ) { bb = map[b / 4 ][b % 4 ]; map[b / 4 ][b % 4 ] = 0 ; p[ 1 ].x = b / 4 , p[ 1 ].y = b % 4 ; for (c = b + 1 ;c < 16 ;c ++ ) { cc = map[c / 4 ][c % 4 ]; map[c / 4 ][c % 4 ] = 0 ; p[ 2 ].x = c / 4 , p[ 2 ].y = c % 4 ; num = 3 ; ans = 0 ; dfs( 0 ); if (ans == 1 ) sum ++ ; map[c / 4 ][c % 4 ] = cc; } map[b / 4 ][b % 4 ] = bb; } map[a / 4 ][a % 4 ] = aa; } // printf("%d\n",sum+1); for (a = 0 ;a < 16 ;a ++ ) { aa = map[a / 4 ][a % 4 ]; map[a / 4 ][a % 4 ] = 0 ; p[ 0 ].x = a / 4 , p[ 0 ].y = a % 4 ; for (b = a + 1 ;b < 16 ;b ++ ) { bb = map[b / 4 ][b % 4 ]; map[b / 4 ][b % 4 ] = 0 ; p[ 1 ].x = b / 4 , p[ 1 ].y = b % 4 ; for (c = b + 1 ;c < 16 ;c ++ ) { cc = map[c / 4 ][c % 4 ]; map[c / 4 ][c % 4 ] = 0 ; p[ 2 ].x = c / 4 , p[ 2 ].y = c % 4 ; for (d = c + 1 ;d < 16 ;d ++ ) { dd = map[d / 4 ][d % 4 ]; map[d / 4 ][d % 4 ] = 0 ; p[ 3 ].x = d / 4 , p[ 3 ].y = d % 4 ; num = 4 ; ans = 0 ; dfs( 0 ); if (ans == 1 ) sum ++ ; map[d / 4 ][d % 4 ] = dd; } map[c / 4 ][c % 4 ] = cc; } map[b / 4 ][b % 4 ] = bb; } map[a / 4 ][a % 4 ] = aa; } // printf("%d\n",sum+1); for (a = 0 ;a < 16 ;a ++ ) { aa = map[a / 4 ][a % 4 ]; map[a / 4 ][a % 4 ] = 0 ; p[ 0 ].x = a / 4 , p[ 0 ].y = a % 4 ; for (b = a + 1 ;b < 16 ;b ++ ) { bb = map[b / 4 ][b % 4 ]; map[b / 4 ][b % 4 ] = 0 ; p[ 1 ].x = b / 4 , p[ 1 ].y = b % 4 ; for (c = b + 1 ;c < 16 ;c ++ ) { cc = map[c / 4 ][c % 4 ]; map[c / 4 ][c % 4 ] = 0 ; p[ 2 ].x = c / 4 , p[ 2 ].y = c % 4 ; for (d = c + 1 ;d < 16 ;d ++ ) { dd = map[d / 4 ][d % 4 ]; map[d / 4 ][d % 4 ] = 0 ; p[ 3 ].x = d / 4 , p[ 3 ].y = d % 4 ; for (e = d + 1 ;e < 16 ;e ++ ) { ee = map[e / 4 ][e % 4 ]; map[e / 4 ][e % 4 ] = 0 ; p[ 4 ].x = e / 4 , p[ 4 ].y = e % 4 ; num = 5 ; ans = 0 ; dfs( 0 ); if (ans == 1 ) sum ++ ; map[e / 4 ][e % 4 ] = ee; } map[d / 4 ][d % 4 ] = dd; } map[c / 4 ][c % 4 ] = cc; } map[b / 4 ][b % 4 ] = bb; } map[a / 4 ][a % 4 ] = aa; } // printf("%d\n",sum+1); for (a = 0 ;a < 16 ;a ++ ) { aa = map[a / 4 ][a % 4 ]; map[a / 4 ][a % 4 ] = 0 ; p[ 0 ].x = a / 4 , p[ 0 ].y = a % 4 ; for (b = a + 1 ;b < 16 ;b ++ ) { bb = map[b / 4 ][b % 4 ]; map[b / 4 ][b % 4 ] = 0 ; p[ 1 ].x = b / 4 , p[ 1 ].y = b % 4 ; for (c = b + 1 ;c < 16 ;c ++ ) { cc = map[c / 4 ][c % 4 ]; map[c / 4 ][c % 4 ] = 0 ; p[ 2 ].x = c / 4 , p[ 2 ].y = c % 4 ; for (d = c + 1 ;d < 16 ;d ++ ) { dd = map[d / 4 ][d % 4 ]; map[d / 4 ][d % 4 ] = 0 ; p[ 3 ].x = d / 4 , p[ 3 ].y = d % 4 ; for (e = d + 1 ;e < 16 ;e ++ ) { ee = map[e / 4 ][e % 4 ]; map[e / 4 ][e % 4 ] = 0 ; p[ 4 ].x = e / 4 , p[ 4 ].y = e % 4 ; for (f = e + 1 ;f < 16 ;f ++ ) { ff = map[f / 4 ][f % 4 ]; map[f / 4 ][f % 4 ] = 0 ; p[ 5 ].x = f / 4 , p[ 5 ].y = f % 4 ; num = 6 ; ans = 0 ; dfs( 0 ); if (ans == 1 ) sum ++ ; map[f / 4 ][f % 4 ] = ff; } map[e / 4 ][e % 4 ] = ee; } map[d / 4 ][d % 4 ] = dd; } map[c / 4 ][c % 4 ] = cc; } map[b / 4 ][b % 4 ] = bb; } map[a / 4 ][a % 4 ] = aa; } // printf("%d\n",sum+1); for (a = 0 ;a < 16 ;a ++ ) { aa = map[a / 4 ][a % 4 ]; map[a / 4 ][a % 4 ] = 0 ; p[ 0 ].x = a / 4 , p[ 0 ].y = a % 4 ; for (b = a + 1 ;b < 16 ;b ++ ) { bb = map[b / 4 ][b % 4 ]; map[b / 4 ][b % 4 ] = 0 ; p[ 1 ].x = b / 4 , p[ 1 ].y = b % 4 ; for (c = b + 1 ;c < 16 ;c ++ ) { cc = map[c / 4 ][c % 4 ]; map[c / 4 ][c % 4 ] = 0 ; p[ 2 ].x = c / 4 , p[ 2 ].y = c % 4 ; for (d = c + 1 ;d < 16 ;d ++ ) { dd = map[d / 4 ][d % 4 ]; map[d / 4 ][d % 4 ] = 0 ; p[ 3 ].x = d / 4 , p[ 3 ].y = d % 4 ; for (e = d + 1 ;e < 16 ;e ++ ) { ee = map[e / 4 ][e % 4 ]; map[e / 4 ][e % 4 ] = 0 ; p[ 4 ].x = e / 4 , p[ 4 ].y = e % 4 ; for (f = e + 1 ;f < 16 ;f ++ ) { ff = map[f / 4 ][f % 4 ]; map[f / 4 ][f % 4 ] = 0 ; p[ 5 ].x = f / 4 , p[ 5 ].y = f % 4 ; for (g = f + 1 ;g < 16 ;g ++ ) { gg = map[g / 4 ][g % 4 ]; map[g / 4 ][g % 4 ] = 0 ; p[ 6 ].x = g / 4 , p[ 6 ].y = g % 4 ; num = 7 ; ans = 0 ; dfs( 0 ); if (ans == 1 ) sum ++ ; map[g / 4 ][g % 4 ] = gg; } map[f / 4 ][f % 4 ] = ff; } map[e / 4 ][e % 4 ] = ee; } map[d / 4 ][d % 4 ] = dd; } map[c / 4 ][c % 4 ] = cc; } map[b / 4 ][b % 4 ] = bb; } map[a / 4 ][a % 4 ] = aa; } // printf("%d\n",sum+1); for (a = 0 ;a < 16 ;a ++ ) { aa = map[a / 4 ][a % 4 ]; map[a / 4 ][a % 4 ] = 0 ; p[ 0 ].x = a / 4 , p[ 0 ].y = a % 4 ; for (b = a + 1 ;b < 16 ;b ++ ) { bb = map[b / 4 ][b % 4 ]; map[b / 4 ][b % 4 ] = 0 ; p[ 1 ].x = b / 4 , p[ 1 ].y = b % 4 ; for (c = b + 1 ;c < 16 ;c ++ ) { cc = map[c / 4 ][c % 4 ]; map[c / 4 ][c % 4 ] = 0 ; p[ 2 ].x = c / 4 , p[ 2 ].y = c % 4 ; for (d = c + 1 ;d < 16 ;d ++ ) { dd = map[d / 4 ][d % 4 ]; map[d / 4 ][d % 4 ] = 0 ; p[ 3 ].x = d / 4 , p[ 3 ].y = d % 4 ; for (e = d + 1 ;e < 16 ;e ++ ) { ee = map[e / 4 ][e % 4 ]; map[e / 4 ][e % 4 ] = 0 ; p[ 4 ].x = e / 4 , p[ 4 ].y = e % 4 ; for (f = e + 1 ;f < 16 ;f ++ ) { ff = map[f / 4 ][f % 4 ]; map[f / 4 ][f % 4 ] = 0 ; p[ 5 ].x = f / 4 , p[ 5 ].y = f % 4 ; for (g = f + 1 ;g < 16 ;g ++ ) { gg = map[g / 4 ][g % 4 ]; map[g / 4 ][g % 4 ] = 0 ; p[ 6 ].x = g / 4 , p[ 6 ].y = g % 4 ; for (h = g + 1 ;h < 16 ;h ++ ) { hh = map[h / 4 ][h % 4 ]; map[h / 4 ][h % 4 ] = 0 ; p[ 7 ].x = h / 4 , p[ 7 ].y = h % 4 ; num = 8 ; ans = 0 ; dfs( 0 ); if (ans == 1 ) sum ++ ; map[h / 4 ][h % 4 ] = hh; } map[g / 4 ][g % 4 ] = gg; } map[f / 4 ][f % 4 ] = ff; } map[e / 4 ][e % 4 ] = ee; } map[d / 4 ][d % 4 ] = dd; } map[c / 4 ][c % 4 ] = cc; } map[b / 4 ][b % 4 ] = bb; } map[a / 4 ][a % 4 ] = aa; } // printf("%d\n",sum+1); for (a = 0 ;a < 16 ;a ++ ) { aa = map[a / 4 ][a % 4 ]; map[a / 4 ][a % 4 ] = 0 ; p[ 0 ].x = a / 4 , p[ 0 ].y = a % 4 ; for (b = a + 1 ;b < 16 ;b ++ ) { bb = map[b / 4 ][b % 4 ]; map[b / 4 ][b % 4 ] = 0 ; p[ 1 ].x = b / 4 , p[ 1 ].y = b % 4 ; for (c = b + 1 ;c < 16 ;c ++ ) { cc = map[c / 4 ][c % 4 ]; map[c / 4 ][c % 4 ] = 0 ; p[ 2 ].x = c / 4 , p[ 2 ].y = c % 4 ; for (d = c + 1 ;d < 16 ;d ++ ) { dd = map[d / 4 ][d % 4 ]; map[d / 4 ][d % 4 ] = 0 ; p[ 3 ].x = d / 4 , p[ 3 ].y = d % 4 ; for (e = d + 1 ;e < 16 ;e ++ ) { ee = map[e / 4 ][e % 4 ]; map[e / 4 ][e % 4 ] = 0 ; p[ 4 ].x = e / 4 , p[ 4 ].y = e % 4 ; for (f = e + 1 ;f < 16 ;f ++ ) { ff = map[f / 4 ][f % 4 ]; map[f / 4 ][f % 4 ] = 0 ; p[ 5 ].x = f / 4 , p[ 5 ].y = f % 4 ; for (g = f + 1 ;g < 16 ;g ++ ) { gg = map[g / 4 ][g % 4 ]; map[g / 4 ][g % 4 ] = 0 ; p[ 6 ].x = g / 4 , p[ 6 ].y = g % 4 ; for (h = g + 1 ;h < 16 ;h ++ ) { hh = map[h / 4 ][h % 4 ]; map[h / 4 ][h % 4 ] = 0 ; p[ 7 ].x = h / 4 , p[ 7 ].y = h % 4 ; for (i = h + 1 ;i < 16 ;i ++ ) { ii = map[i / 4 ][i % 4 ]; map[i / 4 ][i % 4 ] = 0 ; p[ 8 ].x = i / 4 , p[ 8 ].y = i % 4 ; num = 9 ; ans = 0 ; dfs( 0 ); if (ans == 1 ) sum ++ ; map[i / 4 ][i % 4 ] = ii; } map[h / 4 ][h % 4 ] = hh; } map[g / 4 ][g % 4 ] = gg; } map[f / 4 ][f % 4 ] = ff; } map[e / 4 ][e % 4 ] = ee; } map[d / 4 ][d % 4 ] = dd; } map[c / 4 ][c % 4 ] = cc; } map[b / 4 ][b % 4 ] = bb; } map[a / 4 ][a % 4 ] = aa; } // printf("%d\n",sum+1); for (a = 0 ;a < 16 ;a ++ ) { aa = map[a / 4 ][a % 4 ]; map[a / 4 ][a % 4 ] = 0 ; p[ 0 ].x = a / 4 , p[ 0 ].y = a % 4 ; for (b = a + 1 ;b < 16 ;b ++ ) { bb = map[b / 4 ][b % 4 ]; map[b / 4 ][b % 4 ] = 0 ; p[ 1 ].x = b / 4 , p[ 1 ].y = b % 4 ; for (c = b + 1 ;c < 16 ;c ++ ) { cc = map[c / 4 ][c % 4 ]; map[c / 4 ][c % 4 ] = 0 ; p[ 2 ].x = c / 4 , p[ 2 ].y = c % 4 ; for (d = c + 1 ;d < 16 ;d ++ ) { dd = map[d / 4 ][d % 4 ]; map[d / 4 ][d % 4 ] = 0 ; p[ 3 ].x = d / 4 , p[ 3 ].y = d % 4 ; for (e = d + 1 ;e < 16 ;e ++ ) { ee = map[e / 4 ][e % 4 ]; map[e / 4 ][e % 4 ] = 0 ; p[ 4 ].x = e / 4 , p[ 4 ].y = e % 4 ; for (f = e + 1 ;f < 16 ;f ++ ) { ff = map[f / 4 ][f % 4 ]; map[f / 4 ][f % 4 ] = 0 ; p[ 5 ].x = f / 4 , p[ 5 ].y = f % 4 ; for (g = f + 1 ;g < 16 ;g ++ ) { gg = map[g / 4 ][g % 4 ]; map[g / 4 ][g % 4 ] = 0 ; p[ 6 ].x = g / 4 , p[ 6 ].y = g % 4 ; for (h = g + 1 ;h < 16 ;h ++ ) { hh = map[h / 4 ][h % 4 ]; map[h / 4 ][h % 4 ] = 0 ; p[ 7 ].x = h / 4 , p[ 7 ].y = h % 4 ; for (i = h + 1 ;i < 16 ;i ++ ) { ii = map[i / 4 ][i % 4 ]; map[i / 4 ][i % 4 ] = 0 ; p[ 8 ].x = i / 4 , p[ 8 ].y = i % 4 ; for (j = i + 1 ;j < 16 ;j ++ ) { jj = map[j / 4 ][j % 4 ]; map[j / 4 ][j % 4 ] = 0 ; p[ 9 ].x = j / 4 , p[ 9 ].y = j % 4 ; num = 10 ; ans = 0 ; dfs( 0 ); if (ans == 1 ) sum ++ ; map[j / 4 ][j % 4 ] = jj; } map[i / 4 ][i % 4 ] = ii; } map[h / 4 ][h % 4 ] = hh; } map[g / 4 ][g % 4 ] = gg; } map[f / 4 ][f % 4 ] = ff; } map[e / 4 ][e % 4 ] = ee; } map[d / 4 ][d % 4 ] = dd; } map[c / 4 ][c % 4 ] = cc; } map[b / 4 ][b % 4 ] = bb; } map[a / 4 ][a % 4 ] = aa; } // printf("%d\n",sum+1); for (a = 0 ;a < 16 ;a ++ ) { aa = map[a / 4 ][a % 4 ]; map[a / 4 ][a % 4 ] = 0 ; p[ 0 ].x = a / 4 , p[ 0 ].y = a % 4 ; for (b = a + 1 ;b < 16 ;b ++ ) { bb = map[b / 4 ][b % 4 ]; map[b / 4 ][b % 4 ] = 0 ; p[ 1 ].x = b / 4 , p[ 1 ].y = b % 4 ; for (c = b + 1 ;c < 16 ;c ++ ) { cc = map[c / 4 ][c % 4 ]; map[c / 4 ][c % 4 ] = 0 ; p[ 2 ].x = c / 4 , p[ 2 ].y = c % 4 ; for (d = c + 1 ;d < 16 ;d ++ ) { dd = map[d / 4 ][d % 4 ]; map[d / 4 ][d % 4 ] = 0 ; p[ 3 ].x = d / 4 , p[ 3 ].y = d % 4 ; for (e = d + 1 ;e < 16 ;e ++ ) { ee = map[e / 4 ][e % 4 ]; map[e / 4 ][e % 4 ] = 0 ; p[ 4 ].x = e / 4 , p[ 4 ].y = e % 4 ; for (f = e + 1 ;f < 16 ;f ++ ) { ff = map[f / 4 ][f % 4 ]; map[f / 4 ][f % 4 ] = 0 ; p[ 5 ].x = f / 4 , p[ 5 ].y = f % 4 ; for (g = f + 1 ;g < 16 ;g ++ ) { gg = map[g / 4 ][g % 4 ]; map[g / 4 ][g % 4 ] = 0 ; p[ 6 ].x = g / 4 , p[ 6 ].y = g % 4 ; for (h = g + 1 ;h < 16 ;h ++ ) { hh = map[h / 4 ][h % 4 ]; map[h / 4 ][h % 4 ] = 0 ; p[ 7 ].x = h / 4 , p[ 7 ].y = h % 4 ; for (i = h + 1 ;i < 16 ;i ++ ) { ii = map[i / 4 ][i % 4 ]; map[i / 4 ][i % 4 ] = 0 ; p[ 8 ].x = i / 4 , p[ 8 ].y = i % 4 ; for (j = i + 1 ;j < 16 ;j ++ ) { jj = map[j / 4 ][j % 4 ]; map[j / 4 ][j % 4 ] = 0 ; p[ 9 ].x = j / 4 , p[ 9 ].y = j % 4 ; for (k = j + 1 ;k < 16 ;k ++ ) { kk = map[k / 4 ][k % 4 ]; map[k / 4 ][k % 4 ] = 0 ; p[ 10 ].x = k / 4 , p[ 10 ].y = k % 4 ; num = 11 ; ans = 0 ; dfs( 0 ); if (ans == 1 ) sum ++ ; map[k / 4 ][k % 4 ] = kk; } map[j / 4 ][j % 4 ] = jj; } map[i / 4 ][i % 4 ] = ii; } map[h / 4 ][h % 4 ] = hh; } map[g / 4 ][g % 4 ] = gg; } map[f / 4 ][f % 4 ] = ff; } map[e / 4 ][e % 4 ] = ee; } map[d / 4 ][d % 4 ] = dd; } map[c / 4 ][c % 4 ] = cc; } map[b / 4 ][b % 4 ] = bb; } map[a / 4 ][a % 4 ] = aa; } // printf("%d\n",sum+1); for (a = 0 ;a < 16 ;a ++ ) { aa = map[a / 4 ][a % 4 ]; map[a / 4 ][a % 4 ] = 0 ; p[ 0 ].x = a / 4 , p[ 0 ].y = a % 4 ; for (b = a + 1 ;b < 16 ;b ++ ) { bb = map[b / 4 ][b % 4 ]; map[b / 4 ][b % 4 ] = 0 ; p[ 1 ].x = b / 4 , p[ 1 ].y = b % 4 ; for (c = b + 1 ;c < 16 ;c ++ ) { cc = map[c / 4 ][c % 4 ]; map[c / 4 ][c % 4 ] = 0 ; p[ 2 ].x = c / 4 , p[ 2 ].y = c % 4 ; for (d = c + 1 ;d < 16 ;d ++ ) { dd = map[d / 4 ][d % 4 ]; map[d / 4 ][d % 4 ] = 0 ; p[ 3 ].x = d / 4 , p[ 3 ].y = d % 4 ; for (e = d + 1 ;e < 16 ;e ++ ) { ee = map[e / 4 ][e % 4 ]; map[e / 4 ][e % 4 ] = 0 ; p[ 4 ].x = e / 4 , p[ 4 ].y = e % 4 ; for (f = e + 1 ;f < 16 ;f ++ ) { ff = map[f / 4 ][f % 4 ]; map[f / 4 ][f % 4 ] = 0 ; p[ 5 ].x = f / 4 , p[ 5 ].y = f % 4 ; for (g = f + 1 ;g < 16 ;g ++ ) { gg = map[g / 4 ][g % 4 ]; map[g / 4 ][g % 4 ] = 0 ; p[ 6 ].x = g / 4 , p[ 6 ].y = g % 4 ; for (h = g + 1 ;h < 16 ;h ++ ) { hh = map[h / 4 ][h % 4 ]; map[h / 4 ][h % 4 ] = 0 ; p[ 7 ].x = h / 4 , p[ 7 ].y = h % 4 ; for (i = h + 1 ;i < 16 ;i ++ ) { ii = map[i / 4 ][i % 4 ]; map[i / 4 ][i % 4 ] = 0 ; p[ 8 ].x = i / 4 , p[ 8 ].y = i % 4 ; for (j = i + 1 ;j < 16 ;j ++ ) { jj = map[j / 4 ][j % 4 ]; map[j / 4 ][j % 4 ] = 0 ; p[ 9 ].x = j / 4 , p[ 9 ].y = j % 4 ; for (k = j + 1 ;k < 16 ;k ++ ) { kk = map[k / 4 ][k % 4 ]; map[k / 4 ][k % 4 ] = 0 ; p[ 10 ].x = k / 4 , p[ 10 ].y = k % 4 ; for (l = k + 1 ;l < 16 ;l ++ ) { ll = map[l / 4 ][l % 4 ]; map[l / 4 ][l % 4 ] = 0 ; p[ 11 ].x = l / 4 , p[ 11 ].y = l % 4 ; num = 12 ; ans = 0 ; dfs( 0 ); if (ans == 1 ) { /* printf("%d %d %d %d %d %d %d %d %d %d %d %d\n",a,b,c,d,e,f,g,h,i,j,k,l); for(x=0;x<4;x++) { for(y=0;y<4;y++) printf("%d ",map[x][y]); puts(""); } */ sum ++ ; } map[l / 4 ][l % 4 ] = ll; } map[k / 4 ][k % 4 ] = kk; } map[j / 4 ][j % 4 ] = jj; } map[i / 4 ][i % 4 ] = ii; } map[h / 4 ][h % 4 ] = hh; } map[g / 4 ][g % 4 ] = gg; } map[f / 4 ][f % 4 ] = ff; } map[e / 4 ][e % 4 ] = ee; } map[d / 4 ][d % 4 ] = dd; } map[c / 4 ][c % 4 ] = cc; } map[b / 4 ][b % 4 ] = bb; } map[a / 4 ][a % 4 ] = aa; } // printf("%d\n",sum+1); /* for(i=0;i<4;i++) for(j=0;j<4;j++) tmp[i][j]=map[i][j]; memset(map,0,sizeof(map)); for(a=0;a<16;a++) { map[a/4][a%4]=tmp[a/4][a%4]; for(b=a+1;b<16;b++) { map[b/4][b%4]=tmp[b/4][b%4]; for(c=b+1;c<16;c++) { map[c/4][c%4]=tmp[c/4][c%4]; num=0; for(i=0;i<4;i++) for(j=0;j<4;j++) if(map[i][j]==0) p[num].x=i, p[num++].y=j; ans=0; dfs(0); if(ans==1) { for(i=0;i<4;i++) { for(j=0;j<4;j++) printf("%d ",map[i][j]); puts(""); } num++; } map[c/4][c%4]=0; } map[b/4][b%4]=0; } map[a/4][a%4]=0; } */ // printf("%d\n",sum+1); } int main(){ int i,j,k; freopen( " out1.txt " , " w " ,stdout); num = 0 ; sum = 0 ; total = 0 ; memset(map, 0 , sizeof (map)); for (i = 0 ;i < 4 ;i ++ ) { for (j = 0 ;j < 4 ;j ++ ) p[num].x = i, p[num ++ ].y = j; } dfs2( 0 ); // printf("%d %d\n",num,total); /* for(k=0;k<total;k++) { for(i=0;i<4;i++) { for(j=0;j<4;j++) printf("%d ",right[k][i][j]); puts(""); } puts(""); } */ for (k = 0 ;k < total;k ++ ) { for (i = 0 ;i < 4 ;i ++ ) for (j = 0 ;j < 4 ;j ++ ) map[i][j] = right[k][i][j]; slove(); } printf( " %d 13579680\n " ,sum + 288 ); return 0 ;}

要运行半分钟呢，要直接输出啊……

转载于:https://www.cnblogs.com/DreamUp/archive/2010/08/20/1804943.html

相关资源：JAVA上百实例源码以及开源项目