问题描述：数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个3X3粗线宫内的数字均含1-9，并且不重复。
例如：
输入
输出
数据范围：输入一个 9*9 的矩阵
[编程题]Sudoku
- 热度指数：92430 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
包含已知数字的9X9盘面数组[空缺位以数字0表示]
输出描述:
完整的9X9盘面数组
示例1
输入
0 9 2 4 8 1 7 6 3 4 1 3 7 6 2 9 8 5 8 6 7 3 5 9 4 1 2 6 2 4 1 9 5 3 7 8 7 5 9 8 4 3 1 2 6 1 3 8 6 2 7 5 9 4 2 7 1 5 3 8 6 4 9 3 8 6 9 1 4 2 5 7 0 4 5 2 7 6 8 3 1
输出
5 9 2 4 8 1 7 6 3 4 1 3 7 6 2 9 8 5 8 6 7 3 5 9 4 1 2 6 2 4 1 9 5 3 7 8 7 5 9 8 4 3 1 2 6 1 3 8 6 2 7 5 9 4 2 7 1 5 3 8 6 4 9 3 8 6 9 1 4 2 5 7 9 4 5 2 7 6 8 3 1
import java.util.Scanner;
import java.util.ArrayList;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
// 创建数独棋盘
int[][] suduqp = new int[9][9];
ArrayList<int[]> zeroList = new ArrayList<>();
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
int number = in.nextInt();
suduqp[i][j] = number;
// 提取空位
if (number == 0) zeroList.add(new int[]{i, j});
}
}
}
// 填充方法
play(suduqp, zeroList, 0);
// 打印填充好的棋盘
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(suduqp[i][j] + " ");
}
System.out.println();
}
}
public static boolean play(int[][] suduqp,
ArrayList<int[]> zeroList,
Integer times) {
// 如果次数超过集合数，说明已经完成填充
if (times >= zeroList.size()) return true;
// 先定位
int[] position = zeroList.get(times);
int x = position[0];
int y = position[1];
// 判断是否可以填充数字，九个数字
for (int j = 1; j <= 9; j++) {
if (isPrimeNumber(j, suduqp, x, y)) {
// 可以填充，则先填充，并找下一个
suduqp[x][y] = j;
// 这里 times 不能习惯性用 ++，
// 因为会赋值当前 times，导致回溯后，无法正确却找到位置
boolean type = play(suduqp, zeroList, times + 1);
if (type) return true;
// 失败则回溯
suduqp[x][y] = 0;
}
}
return false;
}
public static boolean isPrimeNumber(Integer number,
int[][] suduqp,
Integer x,
Integer y) {
// 判断行 x 固定
for (int i = 0; i < 9; i++) {
if (suduqp[x][i] == number) return false;
}
// 判断列 y 固定
for (int i = 0; i < 9; i++) {
if (suduqp[i][y] == number) return false;
}
// 判断九宫格
int row = x / 3 * 3, col = y / 3 * 3;
for (int i = row; i < row + 3; i++) {
for (int j = col; j < col + 3; j++) {
if (suduqp[i][j] == number) return false;
}
}
return true;
}
}
发表于 2024-07-20 19:44:55
回复(0)
import java.util.*;
public class Main {
public static Stack<Integer> stackI = new Stack<>();
public static Stack<Integer> stackJ = new Stack<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[][] data = new int[9][9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
data[i][j] = sc.nextInt();
}
}
sudu(data);
for (int[] datum : data) {
for (int d : datum) {
System.out.print(d + " ");
}
System.out.println();
}
}
private static void sudu(int[][] data) {
// 回溯法求解
Map<Integer, Integer> map = new LinkedHashMap<>();
for (int i = 0; i < 9; i++) {
map.put(i, 0);
}
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (data[i][j] == 0) {
map.put(i, map.get(i) + 1);
}
}
}
List<String> strTmp = new ArrayList<>();
map.entrySet().stream().sorted(Map.Entry.comparingByValue()).forEach(v -> strTmp.add(v.toString()));
map.clear();
for (int i = 0; i < 9; i++) {
String[] str_s = strTmp.get(i).split("=");
map.put(Integer.parseInt(str_s[0]), Integer.parseInt(str_s[1]));
}
for (Integer i : map.keySet()) {
for (int j = 0; j < 9; j++) {
if (data[i][j] == 0) {
addData(data, i, j, 1);
}
}
}
}
private static void addData(int[][] data, int i, int j, int k) {
if (k > 9) {
int ITmp = stackI.pop();
int JTmp = stackJ.pop();
int kTmp = data[ITmp][JTmp] + 1;
data[ITmp][JTmp] = 0;
data[i][j] = 0;
addData(data, ITmp, JTmp, kTmp);
addData(data, i, j, 1);
return;
}
boolean flag = true;
for (; k <= 9; k++) {
data[i][j] = k;
if (checkisOK(data, i, j)) {
stackI.push(i);
stackJ.push(j);
flag = false;
break;
}
}
if (flag) { // i， j 插不进去 ，出栈
int ITmp = stackI.pop();
int JTmp = stackJ.pop();
int kTmp = data[ITmp][JTmp] + 1;
data[ITmp][JTmp] = 0;
data[i][j] = 0;
addData(data, ITmp, JTmp, kTmp);
addData(data, i, j, 1);
}
}
// 判断行、列、块是否满足插入
private static boolean checkisOK(int[][] data, int i, int j) {
for (int k = 0; k < 9; k++) {
if (k != j && data[i][j] == data[i][k]) {
return false;
}
if (k != i && data[i][j] == data[k][j]) {
return false;
}
}
int row = i / 3 * 3;
int col = j / 3 * 3;
for (int k = row; k < row + 3; k++) {
for (int l = col; l < col + 3; l++) {
if (k == i && l == j) {
continue;
}
if (data[k][l] == data[i][j]) {
return false;
}
}
}
return true;
}
}
编辑于 2024-04-14 13:09:18
回复(0)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int[][] db = new int[10][10];//保存原始数据
List<int[]> arr = new ArrayList<>();//记录0元素的位置
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) {
db[i][j] = in.nextInt();
if ( db[i][j] == 0){
arr.add(new int[]{i,j});
}
}
}
dfs(arr, db);
//打印
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) {
System.out.print(db[i][j]+" ");
}
System.out.println();
}
}
}
private static boolean dfs(List<int[]> arr, int[][] db) {
for (int j = 0; j < arr.size(); j++) {
int hang = arr.get(j)[0];
int lie =arr.get(j)[1];
//1-9去计算是否符合
for (int i = 1; i <= 9; i++) {
if (check(db, hang, lie,i)){
db[hang][lie] = i;
List<int[]> temp = new ArrayList<>();
temp.addAll(arr);
temp.remove(j);
if (dfs(temp,db)){
return true;
}else {
db[hang][lie] = 0;//回溯
}
}
}
return false;
}
return true;
}
//行,列,3*3判断
private static boolean check(int[][] db,int x,int y,int current){
for (int i = 1; i <= 9; i++) {
//行
if (db[x][i] == current)return false;
//列
if (db[i][y] == current)return false;
}
//3*3 1 4
int hang = (x-1)/3 *3 +1; //3*3的起始行
int lie = (y-1)/3 *3 +1; //3*3的起始列
for (int i = hang; i < hang+3; i++) {
for (int j = lie; j < lie+3; j++) {
if (db[i][j] == current){
return false;
}
}
}
return true;
}
}
编辑于 2024-01-20 15:37:44
回复(0)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
final int N = 9;
Scanner in = new Scanner(System.in);
int[][] board = new int[N][N];
List<int[]> empty = new ArrayList<>();
boolean[][] rowFlag = new boolean[N][10];
boolean[][] columnFlag = new boolean[N][10];
boolean[][][] squareFlag = new boolean[3][3][10];
int[] done = new int[]{0};
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int value = in.nextInt();
board[i][j] = value;
if (value == 0) {
empty.add(new int[]{i, j});
} else {
rowFlag[i][value] = true;
columnFlag[j][value] = true;
squareFlag[i/3][j/3][value] = true;
}
}
}
in.close();
dfs(board, empty, rowFlag, columnFlag, squareFlag, 0, done);
}
private static void dfs(int[][] board, List<int[]> empty, boolean[][] rowFlag,
boolean[][] columnFlag, boolean[][][] squareFlag,
int index, int[] done) {
if (index == empty.size()) {
done[0] = 1;
for (int[] arr : board) {
for (int x : arr) {
System.out.print(x + " ");
}
System.out.println();
}
return;
}
int[] arr1 = empty.get(index);
int x1 = arr1[0], y1 = arr1[1];
for (int value = 1; value <= 9 && done[0] == 0; value++) {
if (rowFlag[x1][value] || columnFlag[y1][value]
|| squareFlag[x1/3][y1/3][value]) {
continue;
}
rowFlag[x1][value] = columnFlag[y1][value] = squareFlag[x1/3][y1/3][value] = true;
board[x1][y1] = value;
dfs(board, empty, rowFlag, columnFlag, squareFlag, index+1, done);
rowFlag[x1][value] = columnFlag[y1][value] = squareFlag[x1/3][y1/3][value] = false;
board[x1][y1] = 0;
}
}
}
发表于 2023-03-01 18:35:50
回复(0)
解析：
1.遍历0的位置
2.将0的位置依次填入1-9数字
3.对0位置填入的1-9数字进行游戏规则判断，适合则填入
4.递归调用，判断填入位置后新的矩阵是否有解，有解返回true,无解则回溯
5.输出游戏结果
详解见注释
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 定义一个二维数组，用于存放数独
int[][] sudo = new int[9][9];
// 获取输入的数独矩阵，并加入到数组中
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
sudo[i][j] = in.nextInt();
}
}
// 开始sudo游戏
playSudoGame(sudo);
// 输出游戏结果
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (j >= 0 && j < 8) {
System.out.print(sudo[i][j] + " ");
} else if (j == 8) {
System.out.print(sudo[i][j]);
}
}
// 一行遍历完，换行
System.out.println();
}
}
/**
* 开始数独游戏.
*/
private static boolean playSudoGame(int[][] sudo) {
// 依次进行遍历，找到数组中为0的位置，进行游戏规则判断
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (sudo[i][j] != 0) {
// 遍历位置不为0，则跳过该位置，继续遍历下一个，
continue;
}
// 遍历位置为0，将数字1-9依次填入该位置，通过游戏规则判断填入的数字是否符合规范，如符合则填入该数字
for (int m = 1; m <= 9; m++) {
// 判断填充的数字是否符合规范，规范则进行将数字填入数独矩阵位置处
if (isPassGameNorm(sudo, i, j, m)) {
sudo[i][j] = m;
// 进行递归调用，继续在填入数字矩阵后的新矩阵进行遍历下一个0的位置;
if (playSudoGame(sudo)) {
// 遍历后返回true，则表示填写的数字存在解，则返回true
return true;
} else {
// 如果没有合适的，就进行回溯
sudo[i][j] = 0;
}
}
}
// 1-9 9个数字都尝试完成，但没有找到可以填写的正确结果，则无解，返回false
return false;
}
}
// 遍历完都没有返回false,则表示找到了正确的结果，及返回true
return true;
}
/**
* 数独游戏规范，判断填入的数字是否符合规范，符合规范返回true,反之返回false.
*/
private static boolean isPassGameNorm(int[][] sudo, int i, int j, int m) {
// 判断所在位置的行是否存在该数字，存在则不规范，不存在则规范
for (int x = 0; x < 9; x++) {
if (sudo[i][x] == m) {
return false;
}
}
// 判断所在位置的列是否存在该数字，存在则不规范，不存在则规范
for (int x = 0; x < 9; x++) {
if (sudo[x][j] == m) {
return false;
}
}
// 计算所在位置3x3宫格遍历的其实位置和终点位置
int row = (i / 3) * 3;
int col = (j / 3) * 3;
// 判断所在位置存在的3x3宫格内是否存在该数字，存在则不规范，不存在则规范
for (int x = row; x < row + 3; x++) {
for (int y = col; y < col + 3; y++) {
if (sudo[x][y] == m) {
return false;
}
}
}
// 当没有出现不符合规范时，返回true
return true;
}
}
发表于 2023-02-10 11:02:49
回复(0)
都是递归的方法，个人会更喜欢第二种
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
/**
* @author YXQ
* @create 2022/8/3 17:34
*/
//思路：每个0的位置可以填1-9的数字，然后填上之后，检验这个数字是否有效，
// 若有效，继续填写下一个为0的位置，若1-9都填写完了还是无效，则证明这样填无效 可能是上一层错了（回溯）也可能是此数独无解
// 验证有效的方式：三个维度有效：在x,y,以及3x3的小框内不存在*****重复*****数字，这个验证方式很重要
// 如上分析 这道题就和n皇后题差不多了
public class Main {
// ****************第一种*************************************
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
// int[][] arr=new int[9][9];
// for(int i=0;i<9;i++){
// for (int j=0;j<9;j++){
// arr[i][j]=sc.nextInt();
// }
// sc.nextLine();
// }
// dfs(arr);
// for (int i=0;i<9;i++){
// for (int j=0;j<9;j++){
// System.out.print(arr[i][j]+" ");
// }
// System.out.println();
// }
// }
// public static boolean dfs(int[][] arr){
// for (int i=0;i<9;i++){
// for(int j=0;j<9;j++){
// if(arr[i][j]!=0) continue;
// for(int k=1;k<=9;k++){
// if(isValid(arr,i,j,k)){
// arr[i][j]=k;
// if(dfs(arr))return true;
// arr[i][j]=0;
// }
// }
// return false;
// }
// }
// return true;
// }
// ****************************************第二种**********
// public static void main(String[] args) {
// Scanner sc=new Scanner(System.in);
// int[][] arr=new int[9][9];
// List<int[]>list=new ArrayList<>();
// for(int i=0;i<9;i++){
// for (int j=0;j<9;j++){
// arr[i][j]=sc.nextInt();
// if(arr[i][j]==0)list.add(new int[]{i,j});
// }
// sc.nextLine();
// }
// dfs(arr,list,0);
// for (int i=0;i<9;i++){
// for (int j=0;j<9;j++){
// System.out.print(arr[i][j]+" ");
// }
// System.out.println();
// }
// }
// public static boolean dfs(int[][] arr,List<int[]>list,int index){
// if(index>=list.size())return true;
// for (int i=1;i<=9;i++){
// int x=list.get(index)[0];
// int y=list.get(index)[1];
// if(isValid(arr,x,y,i)){
// // System.out.println("x:"+x+"y:"+y);
// // System.out.println(i);
// arr[x][y]=i;
// if(dfs(arr,list,index+1))return true;
// arr[x][y]=0;
// }
// }
// return false;
// }
//
// ***********************************************第三种***********
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int[][] arr=new int[9][9];
List<int[]>list=new ArrayList<>();
for(int i=0;i<9;i++){
for (int j=0;j<9;j++){
arr[i][j]=sc.nextInt();
if(arr[i][j]==0)list.add(new int[]{i,j});
}
sc.nextLine();
}
dfs(arr,list,0);
for (int i=0;i<9;i++){
for (int j=0;j<9;j++){
System.out.print(res[i][j]+" ");
}
System.out.println();
}
}
static int[][]res=new int[9][9];
public static void dfs(int[][] arr,List<int[]>list,int index){
if(index>=list.size()){
for (int i=0;i<arr.length;i++){
res[i]= Arrays.copyOf(arr[i],arr[i].length);
}
return;
};
for (int i=1;i<=9;i++){
int x=list.get(index)[0];
int y=list.get(index)[1];
if(isValid(arr,x,y,i)){
// System.out.println("x:"+x+"y:"+y);
// System.out.println(i);
arr[x][y]=i;
dfs(arr,list,index+1);
arr[x][y]=0;
}
}
}
public static boolean isValid(int[][] arr,int i,int j,int k){
// 判断一行是否重复
for(int x=0;x<9;x++){
if(arr[x][j]==k)return false;
}
for (int y=0;y<9;y++){
if(arr[i][y]==k)return false;
}
int row=i/3*3,col=j/3*3;
for (int x=row;x<row+3;x++){
for(int y=col;y<col+3;y++){
if(arr[x][y]==k)return false;
}
}
return true;
}
}
发表于 2022-08-03 22:08:20
回复(0)
回溯算法
import java.util.*;
public class Main {
public static int[][] sudo = new int[9][9];//创建数组
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
sudo[i][j]=sc.nextInt();//创建数独
}
}
if(backTracking(sudo)){
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(j==8){
//最后一位数需要换行输出
System.out.println(sudo[i][j]);
}else{
System.out.print(sudo[i][j]+" ");
}
}
}
}
}
}
public static boolean backTracking(int[][] sudo){
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){//遍历数组
if(sudo[i][j]!=0){//如果不需要填数字直接continue
continue;
}
for(int k=1;k<=9;k++){//循环填数字
if(isValid(i,j,k,sudo)){//判断填入数字是否符合要求
sudo[i][j]=k;//填数字
if(backTracking(sudo)){//递归
return true;
}
sudo[i][j]=0;//回溯
}
}
return false;//如果没有符合要求的数字返回false
}
}
return true;
}
public static boolean isValid(int row,int col,int k,int[][] sudo){
for(int i=0;i<9;i++){//检查行
if(sudo[row][i]==k){
return false;
}
}
for(int i=0;i<9;i++){//检查列
if(sudo[i][col]==k){
return false;
}
}
int startRow = (row/3)*3;
int endCol = (col/3)*3;
for(int i=startRow;i<startRow+3;i++){//检查九宫格
for(int j=endCol;j<endCol+3;j++){
if(sudo[i][j]==k){
return false;
}
}
}
return true;
}
}
发表于 2022-07-29 15:49:37
回复(0)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[][] intvals = new int[9][9]; //所有的数
int nowvalue = 0;
List<Integer> list = new ArrayList<Integer>(); //所有要填写的数的位置
for (int i = 0; i < 81; i++) {
nowvalue = sc.nextInt();
intvals[i/9][i%9] = nowvalue;
if(nowvalue==0){
list.add(i); //所有要填写的
}
}
List<List> listalllist = new ArrayList<List>(); //存放所有标记为0的点不能放的值，每条数据对应一个点
for (int i = 0; i < list.size(); i++) {
List<Integer> listcanbe = new ArrayList<Integer>();
listalllist.add(listcanbe);
}
//现在来放值 遍历它能放的所有值 如果都不能满足要求，则回退到上一个点。然后把当前点可以存放的位置放到最开始
// 记录前面所有点放的值在它自己对应的list里的位置
// 这样要么所有点都放进去值，要么回退到第一个值 第一个值遍历完所有的值 还不能搞定的话 就直接报错了
Stack stack = new Stack<>();
boolean blall =true;
for (int i = 0; i < list.size(); i++) {//所有的点 从前到后
boolean bl = false;
int num = 1;
if(listalllist.get(i).size()!=0){ //长度为0 则从1开始，长度不为0 则从它的值的下一个开始（排列必然是1到9的）
num = (int) (listalllist.get(i)).get( (listalllist.get(i)).size()-1 )+1;
}
for (int j = num; j < 10; j++) {
if(canputnum(intvals,list,i,j)){ //判断能不能放
stack.push(j);
intvals[list.get(i)/9][list.get(i)%9] = j;
bl =true; //找到了 则去下一个值
break;
}else{
listalllist.get(i).add(j); //所有不能放的值 从1开始 最多到9
}
}
if(!bl){//没找到 则要将栈里的值取出来 ，然后再将这个值扔到她对应的不能放的值中
//同时将当前的不能放的值清空
if(i==0){
blall = false;
break;
}else{
listalllist.get(i-1).add(stack.pop()); // 上一个的值要要把栈里的清理掉
intvals[list.get(i)/9][list.get(i)%9] = 0; //当前放的值清0
listalllist.get(i).clear(); //当前不能放的值全清空
i = i-2;
}
}
}
for (int i = 0; i < 81; i++) {
if(i%9==8){
System.out.println(intvals[i/9][i%9]);
}else{
System.out.print(intvals[i/9][i%9]+" ");
}
}
}
public static boolean canputnum(int[][] intvals,List<Integer> list, int i,int j){ //第i 个值 要放的值为j
for (int k = 0; k < 9; k++) { //行 判断
if (intvals[list.get(i) / 9][k] == j) {
return false;
}
}
for (int k = 0; k < 9; k++) { //列判断
if (intvals[k][list.get(i) % 9] == j) {
return false;
}
}
for (int l = 0; l < 3; l++) {
for (int m = 0; m < 3; m++) {
//int xxx = (list.get(i) / 9) / 3*3 + l;
// int yyy = (list.get(i) % 9) / 3*3 + m;
//if (intvals[(list.get(i) / 9) / 3 + l][(list.get(i) % 9) / 3 + m] == j) {
if (intvals[(list.get(i) / 9) / 3*3 + l][(list.get(i) % 9) / 3*3 + m] == j) {
return false;
}
}
}
return true;
}
}
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[][] intvals = new int[9][9]; //所有的数
int nowvalue = 0;
List<Integer> list = new ArrayList<Integer>(); //所有要填写的数的位置
for (int i = 0; i < 81; i++) {
nowvalue = sc.nextInt();
intvals[i/9][i%9] = nowvalue;
if(nowvalue==0){
list.add(i); //所有要填写的
}
}
List<List> listalllist = new ArrayList<List>(); //存放所有标记为0的点不能放的值，每条数据对应一个点
for (int i = 0; i < list.size(); i++) {
List<Integer> listcanbe = new ArrayList<Integer>();
listalllist.add(listcanbe);
}
//现在来放值 遍历它能放的所有值 如果都不能满足要求，则回退到上一个点。然后把当前点可以存放的位置放到最开始
// 记录前面所有点放的值在它自己对应的list里的位置
// 这样要么所有点都放进去值，要么回退到第一个值 第一个值遍历完所有的值 还不能搞定的话 就直接报错了
Stack stack = new Stack<>();
boolean blall =true;
for (int i = 0; i < list.size(); i++) {//所有的点 从前到后
boolean bl = false;
int num = 1;
if(listalllist.get(i).size()!=0){ //长度为0 则从1开始，长度不为0 则从它的值的下一个开始（排列必然是1到9的）
num = (int) (listalllist.get(i)).get( (listalllist.get(i)).size()-1 )+1;
}
for (int j = num; j < 10; j++) {
if(canputnum(intvals,list,i,j)){ //判断能不能放
stack.push(j);
intvals[list.get(i)/9][list.get(i)%9] = j;
bl =true; //找到了 则去下一个值
break;
}else{
listalllist.get(i).add(j); //所有不能放的值 从1开始 最多到9
}
}
if(!bl){//没找到 则要将栈里的值取出来 ，然后再将这个值扔到她对应的不能放的值中
//同时将当前的不能放的值清空
if(i==0){
blall = false;
break;
}else{
listalllist.get(i-1).add(stack.pop()); // 上一个的值要要把栈里的清理掉
intvals[list.get(i)/9][list.get(i)%9] = 0; //当前放的值清0
listalllist.get(i).clear(); //当前不能放的值全清空
i = i-2;
}
}
}
for (int i = 0; i < 81; i++) {
if(i%9==8){
System.out.println(intvals[i/9][i%9]);
}else{
System.out.print(intvals[i/9][i%9]+" ");
}
}
}
public static boolean canputnum(int[][] intvals,List<Integer> list, int i,int j){ //第i 个值 要放的值为j
for (int k = 0; k < 9; k++) { //行 判断
if (intvals[list.get(i) / 9][k] == j) {
return false;
}
}
for (int k = 0; k < 9; k++) { //列判断
if (intvals[k][list.get(i) % 9] == j) {
return false;
}
}
for (int l = 0; l < 3; l++) {
for (int m = 0; m < 3; m++) {
//int xxx = (list.get(i) / 9) / 3*3 + l;
// int yyy = (list.get(i) % 9) / 3*3 + m;
//if (intvals[(list.get(i) / 9) / 3 + l][(list.get(i) % 9) / 3 + m] == j) {
if (intvals[(list.get(i) / 9) / 3*3 + l][(list.get(i) % 9) / 3*3 + m] == j) {
return false;
}
}
}
return true;
}
}
发表于 2022-07-10 12:41:56
回复(0)
java 建立行约束、列约束、方格约束，同时记录空缺位置进行回溯
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
// 记录每行 每列 每个方格该位置的元素是否出现
private static boolean[][] row;
private static boolean[][] col;
private static boolean[][][] board;
private static int[][] matrix = new int[9][9];
private static boolean flag = false;
// 空缺列表
private static List<int[]> list;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
matrix[i][j] = in.nextInt();
}
}
row = new boolean[9][10];
col = new boolean[9][10];
board = new boolean[3][3][10];
list = new ArrayList<>();
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(matrix[i][j] == 0){
list.add(new int[]{i,j});
continue;
}
// 记录该元素已经在该行 该列 该单元格出现
row[i][matrix[i][j]] = col[j][matrix[i][j]] = board[i/3][j/3][matrix[i][j]] = true;
}
}
dfs(0);
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
System.out.print(matrix[i][j]);
if(j < 8) System.out.print(" ");
}
System.out.println();
}
}
}
// 回溯
public static void dfs(int cnt){
if(cnt == list.size()){
flag = true;
return ;
}
int[] cur = list.get(cnt);
int i = cur[0], j = cur[1];
for(int digit=1;digit<=9 && !flag;digit++){ // 枚举(i,j)填写的数字
if(!row[i][digit] && !col[j][digit] && !board[i/3][j/3][digit]){
row[i][digit] = col[j][digit] = board[i/3][j/3][digit] = true;
// 将数组中该位置的元素改为digit
matrix[i][j] = digit;
dfs(cnt+1);
//matrix[i][j] = 0;
row[i][digit] = col[j][digit] = board[i/3][j/3][digit] = false;
}
}
}
}
发表于 2022-06-20 11:23:51
回复(0)
java DFS
import java.util.*;
public class Main {
public static boolean correct(int[][] martix, int[] arr, int val) {
int row = arr[0], col = arr[1];
for (int i = 0; i < 9; i++) {
if (martix[row][i] == val || martix[i][col] == val) {
return false;
}
}
int x = row / 3, y = col / 3;
for (int i = x * 3; i < x * 3 + 3; i++) {
for (int j = y * 3; j < y * 3 + 3; j++) {
if (martix[i][j] == val) {
return false;
}
}
}
return true;
}
public static boolean dfs(int[][] martix, List<int[]> pl, int index) {
if (index == pl.size()) {
return true;
}
int[] arr = pl.get(index);
for (int i = 1; i <= 9; i++) {
if (correct(martix, arr, i)) {
martix[arr[0]][arr[1]] = i;
if (dfs(martix, pl, index + 1)) {
return true;
}
martix[arr[0]][arr[1]] = 0;
}
}
return false;
}
public static void main(String[] args) throws Exception {
Scanner in = new Scanner(System.in);
int[][] martix = new int[9][9];
List<int[]> pl = new ArrayList<int[]>();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
martix[i][j] = in.nextInt();
if (martix[i][j] == 0) {
pl.add(new int[] { i, j });
}
}
}
if (dfs(martix, pl, 0)) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(martix[i][j] + " ");
}
System.out.println();
}
}
}
}
发表于 2022-04-16 21:02:19
回复(0)
3*3是可以的，但一个用列不过
import java.util.*;
public class Main {public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[][] map=new int[9][9];
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
map[i][j]=in.nextInt();
}
}
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(map[i][j]==0){
int s[]=new int[10];
int x=i/3;
int y=j/3;
for(int k=x*3;k<x*3+3;k++){
for(int z=y*3;z<y*3+3;z++){
s[map[k][z]]=map[k][z];
}
}
for(int k1=1;k1<10;k1++){
if(s[k1]==0)map[i][j]=k1;
}
}
}
}
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
System.out.print(map[i][j]+" ");
}
System.out.println();
}
}
}
发表于 2022-04-12 16:04:33
回复(0)
import java.util.Scanner;
/**
* dfs解数独
* 从左往右，从上往下遍历每个格子
* 在空格处 循环1-9，检查能不能放，能放->放入，继续递归。不能放->回溯到上一个空格
* 当最后一行遍历完了，说明格子都填满了，直接结束。
*/
public class Main {
//定义数独数组，9行9列
public static int[][] arr = new int[9][9];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNextInt()){
//初始化数独数组
for (int i = 0;i < 9;i++){
for (int j = 0; j < 9;j++){
arr[i][j] = sc.nextInt();
}
}
//调用dfs方法
dfs(0,0);
//打印结果
for (int i = 0;i < 9;i++){
for (int j = 0; j < 9;j++){
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
}
}
/**
* dfs填数独
* @param x 当前的行
* @param y 当前的列
* @return
*/
public static boolean dfs(int x,int y){
//x的范围是0-8，如果x到9，说明数组已经全填完了，直接结束,返回true
if (x == 9){
return true;
}
//y的范围是0-8，如果到9，说明当前行已经遍历完所有列了，跳到下一行
if (y == 9){
return dfs(x+1,0);
}
//当前格子已经填了数字了，跳到下一个格子
if (arr[x][y] != 0){
return dfs(x,y+1);
}
//走到这一步说明当前这个格子是空的，还要判断一下是否能填数字
//循环1-9
for (int i = 1;i <= 9;i++){
//当前格子能填数字i
if (check(x,y,i)){
//填上
arr[x][y] = i;
//继续递归，如果能成功，返回true
if (dfs(x,y+1)){
return true;
}
//如果走到这一步，说明后面的某个格子填入失败了，回溯到这一步，把当前格子改回空格，继续循环
arr[x][y] = 0;
}
}
//如果循环完了没有数字能填入，结束当前dfs，返回false
return false;
}
/**
* 检查当前这个格子能不能填数字num
* @param x 当前行
* @param y 当前列
* @param num 准备填入的数字
* @return
*/
public static boolean check(int x ,int y , int num){
//循环遍历,拿传入的数字与每行，每列比较
for (int i = 0;i < 9 ;i++){
//与当前行其他数字比较
if (arr[x][i] == num){
return false;
}
//与当前列其他数字比较
if (arr[i][y] == num){
return false;
}
}
//循环遍历，那传入的数字与每个小九宫格里的数字比较
for (int i = (x/3)*3;i < (x/3)*3+3 ; i++){
for (int j = (y/3)*3; j < (y/3)*3+3;j++){
if (arr[i][j] == num){
return false;
}
}
}
return true;
}
}
发表于 2021-12-04 17:19:08
回复(2)
最典型的深度优先搜索题，刷题还是力扣好用😥
import java.util.Scanner;
public class Main {
static boolean[][] rowBit = new boolean[9][9];
static boolean[][] colBit = new boolean[9][9];
static boolean[][] boxBit = new boolean[9][9];
public static void main(String args[]) {
int[][] question = new int[9][9];
Scanner scan = new Scanner(System.in);
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
int t = scan.nextInt();
question[row][col] = t;
if (t == 0)
continue;
setBit(row, col, t, true);
}
}
if (!solveSudoku(question, 0, 0))
System.out.println("无解");
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
System.out.print(question[row][col]+" ");
}
System.out.println();
}
}
public static boolean solveSudoku(int[][] q, int i, int j) {
for (; i < 9; i++) {
for (j = 0;j < 9; j++) {
// 找到空位
if (q[i][j] == 0) {
// 找一个可以填的数填入，递归
for (int test = 1; test < 10; test++) {
if (!rowBit[i][test-1] && !colBit[j][test-1] && !boxBit[getBox(i, j)][test-1]) {
q[i][j] = test;
setBit(i, j, test, true);
if (solveSudoku(q, i, j))
return true;
q[i][j] = 0;
setBit(i, j, test, false);
}
// 没有任何数可以填入
if (test == 9)
return false;
}
}
}
}
return true;
}
public static int getBox(int row, int col) {
return (row / 3) * 3 + col / 3;
}
public static void setBit(int i, int j, int test, boolean f) {
rowBit[i][test-1] = f;
colBit[j][test-1] = f;
boxBit[getBox(i, j)][test-1] = f;
}
}
发表于 2021-08-19 00:06:29
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[][] grid = new int[9][9];
boolean[][] rowMap = new boolean[9][9];
boolean[][] colMap = new boolean[9][9];
boolean[][] gridMap = new boolean[9][9];
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
grid[i][j] = sc.nextInt();
if(grid[i][j] != 0) {
rowMap[i][grid[i][j]-1] = true;
colMap[j][grid[i][j]-1] = true;
gridMap[(i/3)*3+j/3][grid[i][j]-1] = true;
}
}
}
dfs(0, 0, grid, rowMap, colMap, gridMap);
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
System.out.print(grid[i][j]);
if(j != 8)
System.out.print(" ");
}
System.out.println();
}
}
public static boolean dfs(int row, int col, int[][] grid, boolean[][] rowMap, boolean[][] colMap, boolean[][] gridMap) {
if(row == 9)
return true;
if(col == 9)
return dfs(row+1, 0, grid, rowMap, colMap, gridMap);
if(grid[row][col] != 0)
return dfs(row, col+1, grid, rowMap, colMap, gridMap);
for(int k = 1; k <= 9; k++) {
if(!rowMap[row][k-1] && !colMap[col][k-1] && !gridMap[(row/3)*3+col/3][k-1]) {
grid[row][col] = k;
rowMap[row][k-1] = true;
colMap[col][k-1] = true;
gridMap[(row/3)*3+col/3][k-1] = true;
if(dfs(row, col+1, grid, rowMap, colMap, gridMap))
return true;
grid[row][col] = 0;
rowMap[row][k-1] = false;
colMap[col][k-1] = false;
gridMap[(row/3)*3+col/3][k-1] = false;
}
}
return false;
}
}
编辑于 2021-03-12 19:50:02
回复(0)
回溯、检查每行每列，还要记住检查3*3格子 ，答案多种不唯一不影响AC
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
int[][] numbers = new int[9][9];
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int[][] indexs = new int[81][2];
int nextRow = 0;
char c;
for (int i = 0, j = 0; j < 9; ) {
c = (char) in.read();
if (c == ' ') continue;
if (c == '\n' || c == '\r') {
j++;
i = 0;
continue;
}
numbers[j][i] = Integer.valueOf(c + "");
if (numbers[j][i] == 0) {
indexs[nextRow][0] = j;
indexs[nextRow][1] = i;
nextRow++;
}
i++;
}
int num;
boolean isOK;
int[] vals;
int m, n;
for (int i = 0; i < nextRow; ) {
num = numbers[indexs[i][0]][indexs[i][1]];
numbers[indexs[i][0]][indexs[i][1]] = 0;
vals = new int[10];
for (int j = 0; j < 9; j++) {
vals[numbers[indexs[i][0]][j]] = 1;
}
for (int j = 1; j < 10; j++) {
if (vals[j] == 0 && num < j) {
isOK = true;
for (int k = 0; k < 9; k++) {
//横列
if (j == numbers[indexs[i][0]][k]) {
isOK = false;
break;
}
//竖列
if (j == numbers[k][indexs[i][1]]) {
isOK = false;
break;
}
//粗线框要唯一！！！
//粗线框要唯一！！！
//粗线框要唯一！！！
//0：00, 1：01, 2：02
//4：10, 5：11, 6：12
//7：20, 8：21, 9：22
m = k / 3 + (indexs[i][0] / 3) * 3;
n = k % 3 + (indexs[i][1] / 3) * 3;
if (j == numbers[m][n]) {
isOK = false;
break;
}
}
if (isOK) {
numbers[indexs[i][0]][indexs[i][1]] = j;
break;
}
}
}
if (numbers[indexs[i][0]][indexs[i][1]] == 0) {
i--;//回溯
} else {
i++;
}
}
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
sb.append(numbers[i][j]);
sb.append(" ");
}
sb.append("\n");
}
sb.delete(sb.length() - 1, sb.length());
System.out.println(sb);
}
}
编辑于 2021-02-25 18:51:48
回复(0)
小白落泪，别人写的难看懂。自己吭吭哧哧写写，再debug下。终于给出的用例和自己改的用例都通过了。提交显示超时。。。。
时间就这么流走了！！！！
发表于 2021-01-26 18:06:12
回复(2)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Hj44 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
Integer[][] mat = new Integer[9][9];
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
mat[i][j] = in.nextInt();
//更新相关点的信息
//Integer[][] 第0行是位置 第一行到第四行是 同一行 同一列 同一个方块儿 最后一行是可能的选择
// System.out.println("Starting...");
mat = solveFunc(mat);
printFunc(mat);
}
}
private static Integer[][] solveFunc(Integer[][] mat ) {
Stack<Integer[][]> matStack = new Stack<>();
matStack.push(mat);
int depth = 0;
while(!matStack.isEmpty()){
Integer[][] newMat = matStack.pop();
HashMap<Integer, Integer[][]> connectArray = construct(newMat);
if (connectArray == null) continue;
//推理函数
boolean success = kenanFunc(connectArray, newMat);
if(!success) continue;
if(success && isCorrect(newMat)){
return newMat;
}
int minKey = findMin(connectArray);
if(minKey == -1) continue;
Integer[] myChoice = connectArray.get(minKey)[4];
depth += 1;
for (Integer newChoice:myChoice) {
// System.out.print("depth is "+ depth);
// System.out.println(" Position is " + minKey + ",newChoice is " + newChoice);
matStack.push(copyFunc(newMat, minKey, newChoice));
}
}
return mat;
}
private static boolean kenanFunc(HashMap<Integer, Integer[][]> connectArray, Integer[][] mat) {
//初始化推理
Iterator<Integer> iterator = connectArray.keySet().iterator();
while(!connectArray.isEmpty() && iterator.hasNext()){
Integer nowKey= iterator.next();
Integer[][] infos = connectArray.get(nowKey);
Integer[] myChoice = infos[4];
for (int i = 0; i < 3; i++) {
replaceFunc(connectArray, nowKey, infos[i+1]);
}
if(connectArray.get(nowKey)[4].length==1){
Integer[] pos = infos[0];
mat[pos[0]][pos[1]] = infos[4][0];
removeKey(connectArray,convert(infos[0]));
iterator = connectArray.keySet().iterator();
}else if(connectArray.get(nowKey)[4].length==0)
return false;
else if((connectArray.get(nowKey)[4].length-1) > connectArray.get(nowKey)[1].length+connectArray.get(nowKey)[2].length+connectArray.get(nowKey)[3].length)
return false;
}
return true;
}
private static Integer[][] copyFunc(Integer[][] mat, Integer minKey, Integer newChoice) {
Integer[][] newMat = new Integer[9][9];
for (int d = 0; d < mat.length; d++) {
newMat[d] = Arrays.copyOf(mat[d], 9);
}
int[] tempPos = convert(minKey);
newMat[tempPos[0]][tempPos[1]] = newChoice.intValue();
return newMat;
}
private static boolean isCorrect(Integer[][] mat) {
if(haveZero(mat))
return false;
//某列的元素
HashSet<Integer> integers = new HashSet();
for (int i = 0; i < mat.length; i++) {
integers.addAll(Arrays.asList(mat[i]));
if(integers.size()!=9)
return false;
else
integers.clear();
}
//某列的元素
for (int j = 0; j < mat[0].length; j++) {
for (int i = 0; i < mat.length; i++) {
integers.add(mat[i][j]);
}
if(integers.size()!=9)
return false;
else
integers.clear();
}
integers.clear();
//某个方块的元素
for (int xSec = 0; xSec < 3; xSec++) {
for (int ySec = 0; ySec < 3; ySec++) {
int [] sec1 = {0,1,2,9,10,11,18,19,20};
for (int d = 0; d < sec1.length;d++){
sec1[d] = sec1[d] + xSec*27 + ySec *3;
}
for (int g:sec1) {
int[] pos = convert(g);
int i = pos[0],j=pos[1];
integers.add(mat[i][j]);
}
if(integers.size()!=9)
return false;
else
integers.clear();
}
}
return true;
}
private static void printFunc(Integer[][] mat) {
//输出结果
for(int i=0;i<9;i++) {
System.out.print(mat[i][0]);
for (int j = 1; j < 9; j++) {
System.out.print(" ");
System.out.print(mat[i][j]);
}
if(i<8)
System.out.println("");
}
}
private static void removeKey(HashMap<Integer, Integer[][]> connectArray, Integer myKey) {
for (int i = 1; i < 4; i++) {
for(Integer youKey:connectArray.get(myKey)[i]){
Integer[][] tempHash = connectArray.get(youKey);
ArrayList<Integer> temp = new ArrayList(Arrays.asList(tempHash[i]));
if(temp.contains(myKey)){
temp.remove(myKey);
tempHash[i] =temp.toArray(new Integer[temp.size()]);
connectArray.put(youKey, tempHash);
}
}
}
connectArray.remove(myKey);
}
public static HashMap<Integer, Integer[][]> construct(Integer[][] mat){
HashMap<Integer, Integer[][]> connectArray= new HashMap(128);
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(mat[i][j] == 0){
Integer[][] t = findInfo(mat, convert(new Integer[]{i,j}));
connectArray.put(convert(t[0]), t);
}
return connectArray;
}
public static Integer[][] findInfo(Integer[][] mat, int start){
ArrayList<Integer> colNeigh = new ArrayList<>();
ArrayList<Integer> rowNeigh = new ArrayList<>();
ArrayList<Integer> sqaureNeigh = new ArrayList<>();
HashSet<Integer> pValues = new HashSet();
pValues.addAll(Arrays.asList(new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9}));
int[] point = convert(start);
int x = point[0], y = point[1];
//一行的零点
for(int i = x, j = 0;j<9;j++){
if(mat[i][j] == 0 && j!=y){
colNeigh.add(convert(new Integer[]{i,j}));
}else if(pValues.contains(mat[i][j])){
pValues.remove(mat[i][j]);
}
}
//一列的元素
for(int i = 0, j = y;i<9;i++){
if(mat[i][j] == 0 && i!=x){
rowNeigh.add(convert(new Integer[]{i,j}));
}else if(pValues.contains(mat[i][j])){
pValues.remove(mat[i][j]);
}
}
//一个方块的元素
int xSec = point[0]/3, ySec = point[1]/3;
int [] sec1 = {0,1,2,9,10,11,18,19,20};
for (int d = 0; d < sec1.length;d++){
sec1[d] = sec1[d] + xSec*27 + ySec *3;
}
for (int g:sec1) {
int[] pos = convert(g);
int i = pos[0],j=pos[1];
if(mat[i][j] == 0 && !(i == x && j == y)){
sqaureNeigh.add(g);
}else if(pValues.contains(mat[i][j])){
pValues.remove(mat[i][j]);
}
}
//加入HashMap中
Integer[][] info = new Integer[5][];
info[0] = new Integer[]{x,y};
info[1] = rowNeigh.toArray(new Integer[rowNeigh.size()]);
info[2] = colNeigh.toArray(new Integer[colNeigh.size()]);
info[3] = sqaureNeigh.toArray(new Integer[sqaureNeigh.size()]);
info[4] = pValues.toArray(new Integer[pValues.size()]);
return info;
}
public static int findMin(HashMap<Integer, Integer[][]>connectArray){
int minKey = -1;
int minValue = Integer.MAX_VALUE;
for (Integer key:connectArray.keySet()) {
if(connectArray.get(key)[4].length<minValue){
minValue = connectArray.get(key)[4].length;
minKey = key;
}
}
return minKey;
}
public static void replaceFunc(HashMap<Integer, Integer[][]>connectArray, Integer myKey, Integer[] infosn) {
int flagPosCount = 1;
//一行的邻居
Integer[] myChoice = connectArray.get(myKey)[4];
for(Integer youKey: infosn){
Integer[] yourChoice = connectArray.get(youKey)[4];
if(Arrays.equals(myChoice, yourChoice)) {
flagPosCount++;
}
}
if(flagPosCount==myChoice.length){
for(Integer you: infosn){
Integer[] yourChoice = connectArray.get(you)[4];
if(! Arrays.equals(myChoice, yourChoice)){
Integer[] yourChoiceAlter = alterFunc(yourChoice,myChoice);
Integer[][] temp = connectArray.get(you);
temp[4] = yourChoiceAlter;
connectArray.replace(you, temp);
}
}
}
}
public static Integer[] alterFunc(Integer[] more, Integer[] less) {
HashSet<Integer> temp = new HashSet();
temp.addAll(Arrays.asList(more));
for (Integer i: less)
if(temp.contains(i))
temp.remove(i);
return temp.toArray(new Integer[temp.size()]);
}
private static boolean haveZero(Integer[][] newMat) {
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(newMat[i][j] == 0){
return true;
}
return false;
}
public static int[] convert(Integer i) {
return new int[]{i/9, i%9};
}
public static int convert(Integer[] a) {
return a[0]*9 + a[1];
}
}
发表于 2021-01-16 16:09:30
回复(1)
出题者的测试样例的输出应该都是按从左到右，从上到下的顺序来进行补全的，所以即使有些样例答案不唯一，我的破代码还是全部通过了😶
import java.util.Scanner;
import java.util.ArrayList;
class Point{
public int x;
public int y;
Point(int x, int y)
{
this.x = x;
this.y = y;
}
}
public class Main
{
public static ArrayList<Integer> FindRemain(int x, int y, int[][] input)
{
int[] has = new int[9];
//寻找横轴
for(int i=0;i<9;i++)
{
int curnum = input[y][i];
if(curnum==0)
{
continue;
}
if(has[curnum-1]==0)
{
has[curnum-1]=1;
}
}
//寻找纵轴
for(int i=0;i<9;i++)
{
int curnum = input[i][x];
if(curnum==0)
{
continue;
}
if(has[curnum-1]==0)
{
has[curnum-1]=1;
}
}
//寻找所在的3x3
int xstart = (x/3)*3;
int ystart = (y/3)*3;
for(int i=ystart;i<ystart+3;i++)
{
for(int j=xstart;j<xstart+3;j++)
{
int curnum = input[i][j];
if(curnum==0)
{
continue;
}
if(has[curnum-1]==0)
{
has[curnum-1]=1;
}
}
}
ArrayList<Integer> out = new ArrayList<>();
for(int i=0;i<has.length;i++)
{
if(has[i]==0)
out.add(i+1);
}
return out;
}
public static ArrayList<Point> test(int[][] input)
{
//寻找所有的空位
ArrayList<Point> points = new ArrayList<>();
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(input[i][j]==0)
{
Point temp = new Point(j,i);
points.add(temp);
}
}
}
return points;
}
public static boolean isEnd = false;
public static void Try(int[][] input, ArrayList<Point> list, int index)
{
//是否到最后一个数字了，不用isEnd进行判断则可以输出所有的可能结果
if(isEnd)
{
return;
}
if(list.size()==index)
{
print(input);
isEnd = true;
}
else
{
Point cur = list.get(index);
ArrayList<Integer> remain = FindRemain(cur.x, cur.y, input);
//如果remain不为空，则代表这个位置还有几种补全的可能
for(int i=0;i<remain.size();i++)
{
input[cur.y][cur.x] = remain.get(i);
Try(input, list, index+1);
input[cur.y][cur.x] = 0;
}
}
}
public static void print(int[][] input)
{
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(j==0)
System.out.print(input[i][j]);
else
System.out.print(" "+input[i][j]);
}
if(i!=9)
System.out.println();
}
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
while(sc.hasNextInt())
{
int[][] input = new int[9][9];
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
input[i][j] = sc.nextInt();
}
}
isEnd = false;
Try(input, test(input), 0);
}
sc.close();
}
}
发表于 2020-08-31 13:29:22
回复(0)
问题信息
难度：
26条回答
2051收藏
28221浏览
通过挑战的用户
查看代码-
2022-11-21 10:44:46 -
2022-09-20 23:08:44 -
2022-09-17 16:26:10
-
2022-09-16 16:52:23 -
2022-09-16 14:52:37
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
