“数独”是当下炙手可热的智力游戏。一般认为它的起源是“拉丁方块”，是大数学家欧拉于1783年发明的。
如图[1.jpg]所示：6x6的小格被分为6个部分（图中用不同的颜色区分）,每个部分含有6个小格（以下也称为分组）。
开始的时候，某些小格中已经填写了字母（ABCDEF之一）。需要在所有剩下的小格中补填字母。
全部填好后，必须满足如下约束：
1. 所填字母只允许是A,B,C,D,E,F 中的某一个。
2. 每行的6个小格中，所填写的字母不能重复。
3. 每列的6个小格中，所填写的字母不能重复。
4. 每个分组（参见图中不同颜色表示）包含的6个小格中，所填写的字母不能重复。
为了表示上的方便，我们用下面的6阶方阵来表示图[1.jpg]对应的分组情况（组号为0~5）：
000011
022013
221113
243333
244455
445555
用下面的数据表示其已有字母的填写情况：
02C
03B
05A
20D
35E
53F
很明显，第一列表示行号，第二列表示列号，第三列表示填写的字母。行号、列号都从0开始计算。
一种可行的填写方案（此题刚好答案唯一）为：
EF C B D A
AC E D F B
DA B E C F
FB D C A E
BD F A E C
CE A F B D
你的任务是：编写程序，对一般的拉丁方块问题求解，如果多解，要求找到所有解。
【输入、输出格式要求】
用户首先输入6行数据，表示拉丁方块的分组情况。
接着用户输入一个整数n (n<36), 表示接下来的数据行数
接着输入n行数据，每行表示一个预先填写的字母。
程序则输出所有可能的解（各个解间的顺序不重要）。
每个解占用7行。
即，先输出一个整数，表示该解的序号（从1开始），接着输出一个6x6的字母方阵，表示该解。
解的字母之间用空格分开。
如果找不到任何满足条件的解，则输出“无解”
例如：用户输入：
000011
022013
221113
243333
244455
445555
6
02C
03B
05A
20D
35E
53F
则程序输出：
1
EF C B D A
AC E D F B
DA B E C F
FB D C A E
BD F A E C
CE A F B D
再如，用户输入：
001111
002113
022243
022443
544433
555553
7
04B
05A
13D
14C
24E
50C
51A
则程序输出：
1
DC E F B A
EF A D C B
AB F C E D
BE D A F C
FD C B A E
CA B E D F
2
DC E F B A
EF A D C B
AD F B E C
BE C A F D
FB D C A E
CA B E D F
3
DC F E B A
AE B D C F
FD A C E B
BF E A D C
EB C F A D
CA D B F E
4
DC F E B A
BE A D C F
AD C F E B
FB E A D C
EF B C A D
CA D B F E
5
DC F E B A
EF A D C B
AB C F E D
BE D A F C
FD B C A E
CA E B D F
6
DC F E B A
EF A D C B
AB D F E C
BE C A F D
FD B C A E
CA E B D F
7
DC F E B A
EF A D C B
AD B F E C
BE C A F D
FB D C A E
CA E B D F
8
DC F E B A
FE A D C B
AD B C E F
BF E A D C
EB C F A D
CA D B F E
9
DC F E B A
FE A D C B
AF C B E D
BD E A F C
EB D C A F
CA B F D E
读完题后是特别郁闷的，为什么一个暴力搜索搞这么严肃.要求怪多的
总结了下网上的解题方式。
说下解题思路：
准备三个数组
①初始数组，用来存放一开始输入的6*6颜色信息。
②存放6*6位置的各个字母
③6种颜色，每种颜色6个格字，存放每种颜色的位子信息
遍历方式：
每个位置尝试填入
A、B、C、D、E、F
需要判断，这个位置是否可以填入这个字母:
①当前的颜色，是否存在字母重复
②当前的行和列是否存在字母重复。
这里存放位置信息使用了一个JAVA内部类Point主要是为了存放方便，他的简介↓↓↓
public class Point{
int x;
int y;
public Point(int x,int y){
this.x=x;
this.y=y;
}
}
全部代码
package testBlue;
import java.util.*;
import java.awt.*;
public class Main {
//初始数组中，就是存放的各个颜色的位置信息
static int[][] m = new int[6][6];
//存放6*6 各个位置的字母信息，-1：代表没有字母，0代表A，1代表B,2代表B..............
static int[][] zimu= new int[6][6];
// 000011
// 022013
// 221113
// 243333
// 244455
// 445555
//每种颜色有6个格子。有6种颜色。
//po[0][0]代表颜色0 的第一个坐标x=0,y=0。、po[1][0]代表颜色1的第一个坐标x=0,y=4........
static Point[][] po = new Point[6][6];
public static void init(){
Scanner input = new Scanner(System.in);
for(int i=0;i<6;i++){//把输出的那些0001111的啥6*6数组的颜色信息放进初始数组
String temp = input.next();
for(int j=0;j<6;j++){
m[i][j]=temp.charAt(j)-'0';
zimu[i][j]=-1;//将字母数组初始字母设置为-1；代表什么都没有放置
}
}
for(int x=0;x<6;x++){//x，代表每种颜色，
int index=0;//↓↓↓↓↓↓每次遍历找到一种颜色的所有位置填入 po 数组
for(int i=0;i<6;i++){//遍历初始数组，
for(int j=0;j<6;j++){
if(m[i][j]==x){
po[x][index++] = new Point(i,j);
}
}
}
}
int n = input.nextInt();
for(int i=0;i<n;i++){//设置zimu数组设置初始字母
char[] temp = input.next().toCharArray();
int x =temp[0]-'0';
int y =temp[1]-'0';
zimu[x][y] = temp[2]-'A';
}
}
public static void DFS(int index){
if(index==36){//不停的突破到了最后，36找到了一个正确结果
printArr();
return;
}
int x =index/6;
int y = index%6;
if(zimu[x][y]==-1){//是没有设置过字母的位置
for(int i=0;i<6;i++){//尝试 A、B、C、D、E、F六个字母的填入
if(checkCR(x,y,i)&&checkCO(x,y,i)){//行列不冲突并且相应的颜色位置不冲突
zimu[x][y]=i;//填入这个字母
DFS(index+1);//填入下个位置
zimu[x][y]=-1;//递归回溯的时候复原数组
}
}
}else{//在初始状态下已经设置过字母了
DFS(index+1);
}
}
static int COUNT=1;//记录总结果数量
public static void printArr(){//按照设计好的数字输出成字母
char[] numC ={'A','B','C','D','E','F'};
System.out.println(COUNT++);
for(int i=0;i<6;i++){
for(int j=0;j<6;j++){
System.out.print(numC[zimu[i][j]]+" ");
}
System.out.println();
}
}
public static boolean checkCR(int row,int col,int c){//看看他所在的颜色里，有没重复的
int corow = m[row][col];//获取这是哪个颜色
for(int i=0;i<6;i++){
int x=po[corow][i].x;//获取该颜色在zimu数组的坐标值
int y=po[corow][i].y;
if(zimu[x][y]==c){
return false;
}
}
return true;
}
public static boolean checkCO(int row,int col,int c){//看看每行每列有没冲突的
for(int i=0;i<6;i++){
if(zimu[row][i]==c){
return false;
}
if(zimu[i][col]==c){
return false;
}
}
return true;
}
public static void main(String[] args) {
init();//输入参数
//递归深度遍历。6*6个位置。 //0==zimu[0][0]//1==zimu[0][1]//6==zimu[1][0];
//35==zimu[5][5];
DFS(0);
}
}
