Sudoku__牛客网

Java

洋007

java的：

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static boolean[][] line = new boolean[9][10];
    private static boolean[][] column = new boolean[9][10];
    private static boolean[][][] block = new boolean[3][3][10];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[][] board = new int[9][9];
        List<int[]> posList = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                board[i][j] = in.nextInt();
                if (board[i][j] == 0) {
                    posList.add(new int[] {i, j});
                } else {
                    line[i][board[i][j]] = true;
                    column[j][board[i][j]] = true;
                    block[i / 3][j / 3][board[i][j]] = true;
                }
            }
        }
        List<int[][]> result = new ArrayList<>();
        dfs(result, board, posList, 0);
        if (!result.isEmpty()) {
            int[][] ans = result.get(0);
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (j > 0) {
                        System.out.print(" ");
                    }
                    if (j == 8) {
                        System.out.println(ans[i][j]);
                    } else {
                        System.out.print(ans[i][j]);
                    }
                }
            }
        }
    }

    private static void dfs(List<int[][]> result, int[][] board,
                            List<int[]> posList, int step) {
        if (step == posList.size()) {
            generateBoard(result, board);
            return;
        }
        int[] pos = posList.get(step);
        int row = pos[0];
        int col = pos[1];
        for (int i = 1; i <= 9; i++) {
            if (!line[row][i] && !column[col][i] && !block[row / 3][col / 3][i]) {
                board[row][col] = i;
                line[row][i] = true;
                column[col][i] = true;
                block[row / 3][col / 3][i] = true;
                dfs(result, board, posList, step + 1);
                line[row][i] = false;
                column[col][i] = false;
                block[row / 3][col / 3][i] = false;
                board[row][col] = 0;
            }
        }
    }

    private static void generateBoard(List<int[][]> result, int[][] board) {
        int[][] newBoard = new int[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                newBoard[i][j] = board[i][j];
            }
        }
        result.add(newBoard);
    }
}

发表于 2025-10-10 22:33:47 回复(0)

Java

米兰牛牛

import java.util.Scanner;

import java.util.*;

/* 虽然展现的是二维数组，但是也可以把二位数组转换为一维数组来操作，在一维数组中3*3的小方格数字的下标可以通过横坐标和纵坐标来计算，比如第一个3*3的小方格数字下标和一维数组的对应关系是a11 = 0 * 9 + 0；a12 = 0 * 9 + 1；a13 = 0 * 9 + 2；a21 = 1 * 9 + 0；a22 = 1 * 9 + 1； a23 = 1 * 9 + 2；a31 = 2 * 9 + 0；a32 = 2 * 9 + 1； a33 = 2* 9 + 2；

因此：二维数组Aij 下标和一维数组Bk下标的对应关系是 k =( i -1)* 9 +( j-1)

然后把整个二维数组看作是3*3的小方格，依次遍历小方格（注意遍历的步长是3）。

*/

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int[] list = new int[81];

int count = 0;

while (in.hasNextInt()) {

list[count] = in.nextInt();

count++;

}

for(int i = 0;i < 9;i += 3){

for(int j = 0; j < 9; j += 3 ){

covent(i,j,list);

}

for (int i = 0; i < list.length; i++ ) {

System.out.print(list[i] + " ");

if ((i + 1) % 9 == 0) {

System.out.println();

}

public static void covent(int ii, int jj, int[] list) {

List<Integer> list1 = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);

List<Integer> list2 = new ArrayList<Integer>();

List<Integer> index0 = new ArrayList<Integer>();

int a = ii + 3;

int b = jj + 3;

for (int i = ii; i < a; i++) {

for (int j = jj; j < b; j++) {

if(list[i * 9 + j] == 0){

index0.add(i *9 + j);

}else{

list2.add(list[i *9 + j]);

}

List<Integer> diff = new ArrayList<>();

for(Integer i: list1){

if(!list2.contains(i)){

diff.add(i);

}

for(int i = 0;i < diff.size();i++){

list[index0.get(i)] = diff.get(i);

}

发表于 2025-08-10 12:28:34 回复(0)

Java

Sen🍓🍀

import java.util.*;

// @@@ 回溯：暴力穷举(类似N皇后,理解回溯模版)
public class Main {
    public static List<List<Integer>> res = new ArrayList<>(); // 最终结果集合
    public static List<Integer> path = new ArrayList<>(); // 一次结果

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[][] grid = new int[9][9]; // 棋盘
        List<int[]> unsolve = new ArrayList<>(); // 存放要填的位置
        for (int i = 0; i < 9; i++) { // 输入
            for (int j = 0; j < 9; j++) {
                int x = in.nextInt();
                grid[i][j] = x;
                if (x == 0) unsolve.add(new int[] {i, j});
            }
        }

        backtrack(grid, unsolve, 0, false); // dfs

        for (int i = 0; i < unsolve.size(); i++) { // 填充方案数字
            grid[unsolve.get(i)[0]][unsolve.get(i)[1]] = res.get(0).get(i);
        }

        for (int i = 0; i < 9; i++) { // 打印
            for (int j = 0; j < 9; j++) {
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }

    }

    // 回溯
    public static void backtrack(int[][] grid, List<int[]> unsolve, int k, boolean find) {
        if (find || k == unsolve.size()) { // 递归出口(找到一个解就可以return)
            if (!find) {
                find = true;
                res.add(new ArrayList<>(path));
            }
            return;
        }

        for (int num = 1; num <= 9; num++) {
            if (find) return;
            int x = unsolve.get(k)[0], y = unsolve.get(k)[1];
            if (check(grid, x, y, num)) {
                grid[x][y] = num; // 选择
                path.add(num);
                backtrack(grid, unsolve, k + 1, find); // 下一层
                grid[x][y] = 0;   // 撤销选择
                path.remove(path.size() - 1);
            }
        }
    }

    // 判断当前位置(x,y)是否可放数字num
    public static boolean check(int[][] grid, int x, int y, int num) {
        int m = grid.length, n = grid[0].length;
        // 该行不重复
        for (int j = 0; j < n; j++) {
            if (j != y && grid[x][j] == num) return false;
        }
        // 该列不重复
        for (int i = 0; i < m; i++) {
            if (i != x && grid[i][y] == num) return false;
        }
        // 该小方形不重复 (x/3*3,y/3*3左上角)
        for (int i = x / 3 * 3, dx = 0; dx < 3; dx++) {
            for (int j = y / 3 * 3, dy = 0; dy < 3; dy++) {
                if ((i + dx != x || j + dy != y) && grid[i + dx][j + dy] == num)  return false;
            }
        }
        return true;
    }
}

发表于 2025-03-21 22:12:35 回复(0)

Java

聪明的牛油果在刷题

import java.util.Scanner;

// 注意类名必须为 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[][] data = new int[9][9];

            //取出数据放在data中
            for (int i = 0 ; i < 9 ; i++) {
                for (int j = 0 ; j < 9 ; j++) {
                    data[i][j] = in.nextInt();
                }
            }
            process(data, 0, 0);
            //打印数据
            for (int i = 0 ; i < 9 ; i++) {
                for (int j = 0 ; j < 9 ; j++) {
                    System.out.print(data[i][j] + " ");
                }
                System.out.println();
            }
        }
    }

    public static boolean process(int[][] data, int x, int y) {
        //x超出范围 说明所有格子全部填写正确 返回true
        if (x == 9) {
            return true;
        }
        // 查询下次要去格子的x和y
        int[] zhenXY = zhenXY(x, y + 1);
        if (data[x][y] != 0) {
            //如果当前格子不为0 前往下一个格子
            return process(data, zhenXY[0], zhenXY[1]);
        } else {
            //当前格子为 0 循环填入 1-9 判断
            for (int i = 1 ; i <= 9 ; i++) {
                if (isTrue(data, x, y, i)) {
                    //当前格子填入i
                    data[x][y] = i;
                    //当前格子填入i后 后续操作是否有错误
                    boolean pan = process(data, zhenXY[0], zhenXY[1]);

                    if (!pan) {
                        //有错误 当前格子填回0
                        data[x][y] = 0;
                    }else{
                        //无错误 返回正确结果
                        return true;
                    }
                }
            }

        }
        return false;
    }

    // 返回下次要去格子的x和y
    public static int[] zhenXY(int x, int y) {
        if (y == 9) {
            x++;
            y = 0;
        }
        return new int[] {x, y};
    }

    //判断 x y 格子 填写 k 时 是否正确
    public static boolean isTrue(int[][] data, int x, int y, int k) {
        for (int i = 0 ; i < 9 ; i++) {
            //遍历该格子同一列
            if (data[i][y] == k) {
                return false;
            }
            //遍历该格子同一行
            if (data[x][i] == k) {
                return false;
            }
        }
        //遍历该格子所在的九宫格
        int m = x / 3 * 3, n = y / 3 * 3;
        for (int i = m ; i < m + 3 ; i++) {
            for (int j = n ; j < n + 3 ; j++) {
                if (data[i][j] == k) {
                    return false;
                }
            }
        }
        return true;
    }



}

发表于 2025-02-20 14:47:37 回复(0)

Java

绿豆冰沙

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)

Java

乐观的话题终结者在吐槽

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)

Java

今生能进大厂吗

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)

Java

牛客268032525号

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)

Java

陈一月的编程岁月

解析：

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)

Java

Cyan_Mu

都是递归的方法，个人会更喜欢第二种

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)

Java

牛客738194984号

回溯算法

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)

Java

牛客853495459号

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;
}
}

发表于 2022-07-10 12:41:56 回复(0)

Java

刻苦的大熊猫在度假

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

牛客123456789.号

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)

Java

牛客662389935号

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)

Java

奥因克

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)

Java

鬼梗

最典型的深度优先搜索题，刷题还是力扣好用😥

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)

Java

ncc2814

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)

Sudoku

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题