题解 | #Sudoku#

Sudoku

https://www.nowcoder.com/practice/78a1a4ebe8a34c93aac006c44f6bf8a1

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static class Pos {
        int row;
        int col;

        public Pos(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[][] nums = new int[9][9];
        //记录空位
        List<Pos> list = new ArrayList<>();
        //填数据
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[0].length; j++) {
                nums[i][j] = in.nextInt();
                if (nums[i][j] == 0) {
                    list.add(new Pos(i, j));
                }
            }
        }

        //写数独
        write(nums, list, 0);

        //输出结果
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(nums[i][j]);
                if (j != 8) {
                    System.out.print(" ");
                } else {
                    if (i != 8) {
                        System.out.println();
                    }
                }
            }

        }


    }

    public static boolean write(int[][] nums, List<Pos> list, int index) {
        //全部填完,代表数独完成
        if (index == list.size()) {
            return true;
        }

        //没填完就取出当前位置进行分析
        Pos pos = list.get(index);


        //先看看这个位置能填什么数
        Set<Integer> set = new HashSet<>();
        for (int i = 1; i < 10; i++) {
            set.add(i);
        }

        //去掉横着的和竖着的
        for (int i = 0; i < 9; i++) {
            set.remove(nums[pos.row][i]);
            set.remove(nums[i][pos.col]);
        }

        //去掉方格内的
        int startR = pos.row / 3 * 3;
        int startC = pos.col / 3 * 3;
        for (int i = startR; i < startR + 3 ; i++) {
            for (int j = startC; j < startC + 3 ; j++) {
                set.remove(nums[i][j]);
            }
        }

        //剩下的set就是可以填进去的数
        for (Integer tryNum : set) {
            nums[pos.row][pos.col] = tryNum;
            if (write(nums, list, index + 1)) {
                return true;
            }
        }

        //都填了都不行,说明之前的数不对,回溯
        nums[pos.row][pos.col] = 0;
        return false;


    }
}

#数独#
全部评论

相关推荐

joe2333:怀念以前大家拿华为当保底的日子
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务