经典dfs、回溯（9x9数独（java版本））

题目：牛客网的一个acm练习赛 https://ac.nowcoder.com/acm/contest/625/E

思路：
先说错误的思路，先用dfs，遍历所有的可能，最后走完所有格子，再判断每一个坐标在行、列、小数独块里是否符合条件，如果符合条件再输出，简单来说就是先尝试，后判断。其实这种做法是正确的，说它是错误的是因为太慢了，跑半天都跑不出来。
所以正确的做法是用剪枝，每次走一格都判断一次这个格子在行、列、小数独块里是否符合条件，如果符合条件就继续往下走，不符合就倒回去，这样的话不符合条件的可能就不用继续往下走浪费时间了。

伪代码：其实挺简单，就那个小数独块比较麻烦：
为了方便遍历，我把所有的坐标都封装在一个类里面
经典dfs、回溯（9x9数独（java版本））
dfs（int cur）
{
if(这个坐标值为0，开始常识)
{
for(从一到九尝试)
{
if(check（）如果在行、列、小数独块里都符合条件继续往下走，不符合换另外一个数)
{
dfs（cur+1）
}
}
}
如果这个值不为0，继续往下走
dfs（cur+1）
}

boolean check(int x,int y,int k)
{
1、先判断在行和列中是否符合条件，不符合return false，符合继续判断
2、为了方便我在main方法中就把9个小数独块分开装好了，并且放在了全局变量里
（1）先判断这个坐标在哪一个小数独里
（2）然后判断这个小数独是否符合条件
}

完整版java代码如下（代码写得不太好，可能有点累赘，仅供参考）（个人建议没必要把重点放在代码上，主要是思路，你把思路理顺了，写代码只是时间问题）：
import java.util.ArrayList;
import java.util.Scanner;

public class Main
{
static int[][] arr=new int[9][9];
static Dian[] ds=new Dian[81];
static ArrayList<ArrayList> al;
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int k=0;
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
ds[k]=new Dian(i, j);
k++;
arr[i][j]=sc.nextInt();
}
}
int[] book=new int[81];
ArrayList ks=new ArrayList();
al=new ArrayList<ArrayList>();
for(int i=0;i<ds.length;i++)
{
if(i%3==0)
{
al.add(ks);
ks=new ArrayList();
}
if(book[i]0)
{
book[i]=1;
book[i+9]=1;
book[i+18]=1;
ks.add(ds[i]);
ks.add(ds[i+9]);
ks.add(ds[i+18]);
}
}
dfs(0);
}
public static void dfs(int cur)
{
if(curds.length)
{
if(true)
{
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(j!=8)
System.out.print(arr[i][j]+" ");
else
System.out.println(arr[i][j]);
}
}
}
return ;
}

   		int x=ds[cur].x;
   		int y=ds[cur].y;
   		if(arr[x][y]==0)
   		{
   			for(int k=1;k<=9;k++)
   			{
   				if(check(x, y, k))
   				{
   					arr[x][y]=k;
   					dfs(cur+1);
   					arr[x][y]=0;
   				}
   			}
   		}
   		else
   			dfs(cur+1);

}
private static boolean check(int x, int y, int k) 
{
	//判断行和列
	int[] book=new int[10];
	book[k]++;
	for(int i=0;i<9;i++)
		book[arr[i][y]]++;
	for(int i=1;i<=9;i++)
		if(book[i]>1)
			return false;
	book=new int[10];
	book[k]++;
	for(int j=0;j<9;j++)
		book[arr[x][j]]++;
	for(int i=1;i<=9;i++)
		if(book[i]>1)
			return false;
	//判断块
	int flag=-1;
	for(int i=0;i<al.size();i++)
	{
		ArrayList<Dian> dds = al.get(i);
		for(Dian d:dds)
			if(d.x==x&&d.y==y)
				flag=i;
	}
	book=new int[10];
	book[k]++;
	for(int i=0;i<al.get(flag).size();i++)
	{
		Dian d=al.get(flag).get(i);
		book[arr[d.x][d.y]]++;
	}
	for(int i=1;i<=9;i++)
		if(book[i]>1)
			return false;
	return true;
}

}
class Dian
{
int x;
int y;
Dian(int x, int y)
{
this.x = x;
this.y = y;
}
Dian()
{
}

}

经典dfs、回溯（9x9数独（java版本））

相关推荐