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

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 3
9 0 0
0 0 1
0 2 0
3 0 5
8 0 6
6 0 0
0 0 1
4 0 0
0 0 8
7 0 0
0 0 6
1 0 2
0 0 0
7 0 8
9 0 0
0 0 8
2 0 0
0 0 2
8 0 0
0 0 5
6 0 9
2 0 3
0 1 0
5 0 0
0 0 9
3 0 0

4 8 3
9 6 7
2 5 1
9 2 1
3 4 5
8 7 6
6 5 7
8 2 1
4 9 3
5 4 8
7 2 9
1 3 6
1 3 2
5 6 4
7 9 8
9 7 6
1 3 8
2 4 5
3 7 2
8 1 4
6 9 5
6 8 9
2 5 3
4 1 7
5 1 4
7 6 9
3 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.


Solution

利用dfs(深度优先搜索)进行填数独。 方法是将所有空格放到一个$ArrayList$的列表$empty$中,随后调用$dfs(0)$。 $dfs(index)$表示现在填充$empty$列表中第$index$位,具体流程如下: 1. 如果$empty$中所有空格已经填完了,那么说明填充无误,可以退出$dfs$ 2. 现在开始填写$empty[index]$所表示的位置,枚举填入$x$($x$在$1-9$之间)的情况: 3. 将$x$填入后,是否产生矛盾,若无矛盾则继续填写$index+1$位置,若有矛盾则尝试下一个可能的$x$

Code

import java.io.BufferedReader;
import java.io.FileReader;
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;
		try(FileReader fr=new FileReader(fileName);
				BufferedReader in = new BufferedReader(fr);){
			String line;
			int index=0;
			while((line=in.readLine())!=null){
				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)
    			empty.add(new Pair(i,j));
    	}
    	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