Su Doku题号：96 难度： 25 中英对照

Su Doku (Japanese meaning number place) is the name given to a popular puzzle concept. Its origin is unclear, but credit must be attributed to Leonhard Euler who invented a similar, and much more difficult, puzzle idea called Latin Squares. The objective of Su Doku puzzles, however, is to replace the blanks (or zeros) in a 9 by 9 grid in such that each row, column, and 3 by 3 box contains each of the digits 1 to 9. Below is an example of a typical starting puzzle grid and its solution grid.

 0 0 39 0 00 0 1 0 2 03 0 58 0 6 6 0 00 0 14 0 0 0 0 87 0 00 0 6 1 0 20 0 07 0 8 9 0 00 0 82 0 0 0 0 28 0 00 0 5 6 0 92 0 30 1 0 5 0 00 0 93 0 0

 4 8 39 6 72 5 1 9 2 13 4 58 7 6 6 5 78 2 14 9 3 5 4 87 2 91 3 6 1 3 25 6 47 9 8 9 7 61 3 82 4 5 3 7 28 1 46 9 5 6 8 92 5 34 1 7 5 1 47 6 93 8 2

A well constructed Su Doku puzzle has a unique solution and can be solved by logic, although it may be necessary to employ "guess and test" methods in order to eliminate options (there is much contested opinion over this). The complexity of the search determines the difficulty of the puzzle; the example above is considered easy because it can be solved by straight forward direct deduction.

The 6K text file, sudoku.txt (right click and 'Save Link/Target As...'), contains fifty different Su Doku puzzles ranging in difficulty, but all with unique solutions (the first puzzle in the file is the example above).

By solving all fifty puzzles find the sum of the 3-digit numbers found in the top left corner of each solution grid; for example, 483 is the 3-digit number found in the top left corner of the solution grid above.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;

public final class p96 {
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" );
}
static int[][] map=new int[9][9];
static public String run(){
String fileName="p096_sudoku.txt";
int ans=0;
String line;
int index=0;
if(line.startsWith("Grid")){
index=0;
continue;
}
for(int i=0;i<9;i++)
map[index][i]=line.charAt(i)-'0';
index++;
if(index>=9){
//已经读取了9行，现在解这个数独
ans+=solve();
index=0;
}
}
}catch(IOException e){
e.printStackTrace();
return null;
}
return Integer.toString(ans);
}
static public class Pair{
public int x,y;
public Pair(int x,int y){this.x=x;this.y=y;}
}
static ArrayList<Pair> empty;
static public final int solve(){
empty=new ArrayList<Pair>();
//把空的位置放进一个list
for(int i=0;i<9;i++) for(int j=0;j<9;j++){
if(map[i][j]==0)
}
if(dfs(0))
;
else
return 0;
return map[0][0]*100+10*map[0][1]+map[0][2];
}
static public final boolean dfs(int index){
//填写empty第index位的格子
if(index>=empty.size()) return true;//已经填完
int i=empty.get(index).x;
int j=empty.get(index).y;
for(int x=1;x<=9;x++){
map[i][j]=x;//填入x
if(check(i,j))//目前填入无误
if(dfs(index+1))//填下一个
return true;
map[i][j]=0;//回退到未填入的情况
}
return false;
}
static public final boolean check(int i,int j){
//判断map上的ij位置填写是否正确
//行列判断
boolean cnt[]=new boolean[10];
for(int k=0;k<10;k++) cnt[k]=false;
for(int k=0;k<9;k++){
if(map[i][k]==0) continue;
if(cnt[map[i][k]]) return false;
cnt[map[i][k]]=true;
}
for(int k=0;k<10;k++) cnt[k]=false;
for(int k=0;k<9;k++){
if(map[k][j]==0) continue;
if(cnt[map[k][j]]) return false;
cnt[map[k][j]]=true;
}
//小正方形判断
for(int k=0;k<10;k++) cnt[k]=false;
//正方形起始位置
int is=i/3*3;
int js=j/3*3;
for(int k=is;k<is+3;k++) for(int t=js;t<js+3;t++){
if(map[k][t]==0) continue;
if(cnt[map[k][t]]) return false;
cnt[map[k][t]]=true;
}
return true;
}
}

24702
923ms