当前位置 博文首页 > 用心编码:sudoku(数独) - 算法
一、题目描述
游戏规则:
如下图所示:
二、分析
从最上角(0,0)开始将81个宫格进行编号(0-80),通过转换可以将数字为所在行,所在列和所在小矩阵。
也就是说,通过数字 n,我们可以计算出该数字映射到 9 * 9 宫格的位置。
行列:row = n / 9;col = n % 9;
小宫格:
行范围:(row / 3) * 3 ~(row / 3) * 3 + 3;
列范围:(col / 3) * 3 ~ (col / 3) * 3 + 3
三、代码
import java.util.*;
public class Sudoku2 {
static final int size = 9;
static int[][] sudoku = new int[size][size];
static boolean flag;
public static void main(String[] args) throws Exception{
// Scanner sc = new Scanner(new File("src/case/sudoku.txt"));
Scanner sc = new Scanner(System.in);
String line = "";
while(sc.hasNext()){
sc.next();
for(int i = 0;i < size;i++){
line = sc.next();
for(int j = 0;j < size;j++){
sudoku[i][j] = Character.getNumericValue(line.charAt(j));
}
}
flag = false;
dfs(0);
print();
}
}
// dfs
static void dfs(int n){
if(n > 80 || flag){
flag = true;
return;
}
if(sudoku[n / 9][n % 9] != 0){
dfs(n+1);
if(flag){
return;
}
} else {
for(int curNum = 1;curNum <= 9;curNum++){
if(isOk(n,curNum)){
sudoku[n / 9][n % 9] = curNum;
dfs(n+1);
if(flag){
return;
}
sudoku[n / 9][n % 9] = 0;
}
}
}
}
// n : 0 - 80,枚举 1 - 9
static boolean isOk(int n,int curNUm){
int row = n / 9; // 当前行
int col = n % 9; // 当前列
for(int i = 0;i < size;i++){
if(sudoku[row][i] == curNUm){
return false;
}
if(sudoku[i][col] == curNUm){
return false;
}
}
int x = (row / 3) * 3; // 子矩阵
int y = (col / 3) * 3;
for(int i = x;i < x + 3;i++){
for(int j = y;j < y + 3;j++){
if(sudoku[i][j] == curNUm){
return false;
}
}
}
return true;
}
// 打印
static void print(){
for(int i = 0;i < size;i++){
for(int j = 0;j < size;j++){
System.out.print(sudoku[i][j]);
}
System.out.println();
}
}
}
cs