Java题解 | HJ44 #Sudoku#

描述

问题描述：数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个粗线宫内的数字均含1-9，并且不重复。

输入：包含已知数字的9X9盘面数组（空缺位以数字0表示）

输出：完整的9X9盘面数组

输入描述:包含已知数字的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

解法

• 由“满足每一行、每一列、每一个粗线宫内的数字均含1-9，并且不重复”的特点，可以推断出行、列、宫能填入剩余空格的数字的候选人列表；
• 先从第1个空格的候选人列表选出1个候选人，而后从第2个空格的候选人列表选出1个候选人。如果上述候选人能够满足填入条件，则尝试下一个空格；如果不能满足填入条件，从第2个空格的候选人列表尝试选出另外候选人；如果还不能满足填入条件，从第1个空格的候选人列表尝试其他候选人；
• 怎么查当前格子在哪个九宫格？((x/3)*3, (y/3)*3)即为九宫格左上角的坐标。

/*
 * Copyright (c) waylau.com, 2022\. All rights reserved.
 */

package com.waylau.nowcoder.exam.oj.huawei;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * HJ44 Sudoku.
 * 问题描述：数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字，
 * 推算出所有剩余空格的数字，并且满足每一行、每一列、每一个粗线宫内的数字均含1-9，并且不重复
 * 输入：包含已知数字的9X9盘面数组（空缺位以数字0表示）
 * 输出：完整的9X9盘面数组
 * 输入描述:包含已知数字的9X9盘面数组（空缺位以数字0表示）
 * 输出描述:完整的9X9盘面数组
 *
 * @author Way Lau
 * @since 2022-08-23
 */
public class HJ044Sudoku {
    private static final int N = 9;

    public static void main(String[] args) {
        // 输入
        Scanner in = new Scanner(System.in);

        List zeroGridList = new ArrayList();

        // 输入的数组arr[n][m]的值0表示空格
        int[][] arr = new int[N][N];
        int index = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int gridValue = in.nextInt();
                arr[i][j] = gridValue;

                if (gridValue == 0) {
                    zeroGridList.add(new Grid(index, i, j));
                    index++;
                }
            }
        }

        // 执行
        Stack gridStack = new Stack();

        // 记录下个格子
        int nextIdex = 0;
        while (nextIdex < zeroGridList.size()) {
            nextIdex = doSudoku(arr, gridStack,
                    zeroGridList.get(nextIdex), false);
        }

        // 输出
        for (int i = 0; i < N; i++) {
            StringBuilder sb = new StringBuilder();

            for (int j = 0; j < N; j++) {
                sb.append(arr[i][j]);
                sb.append(" ");
            }

            System.out.println(sb.toString().trim());
        }

        // 关闭
        in.close();
    }

    private static int doSudoku(int[][] arr,
            Stack gridStack, Grid zeroGrid,
            boolean isPreviousGrid) {
        Queue candidates = zeroGrid.candidates;

        // 如果是从栈里面找出来的格子，说明之前已经查过候选人，无需重新再查
        if (!isPreviousGrid) {
            candidates = selectCandidate(arr, zeroGrid.x,
                    zeroGrid.y);
            zeroGrid.candidates = candidates;
        }

        if (!candidates.isEmpty()) {
            // 从候选里面取一个
            int candidate = candidates.poll();
            arr[zeroGrid.x][zeroGrid.y] = candidate;
            gridStack.add(zeroGrid);

            return zeroGrid.index + 1;
        } else {
            // 找不到候选人，说明前面的空格填的有问题
            // 回退到上一个格子找后续的候选人
            Grid previousGrid = gridStack.pop();
            arr[previousGrid.x][previousGrid.y] = 0;

            return doSudoku(arr, gridStack, previousGrid,
                    true);
        }

    }

    // 查找候选人列表
    private static Queue selectCandidate(
            int[][] arr, int x, int y) {
        Queue candidates = new ArrayBlockingQueue(
                N);

        for (int candidate = 1; candidate <= N; candidate++) {
            // 先探行，再探列，再探九宫格
            for (int j = 0; j < N; j++) {
                if (!contains(arr[x], candidate)
                        && !containsColumn(arr, y,
                                candidate)
                        && !containsGrid(arr, x, y,
                                candidate)) {
                    candidates.add(candidate);

                    break;
                }
            }
        }

        return candidates;
    }

    // 判断是否包含在行里
    private static boolean contains(int[] a, int val) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] == val) {
                return true;
            }
        }
        return false;
    }

    // 判断是否包含在列里
    private static boolean containsColumn(int[][] a,
            int column, int val) {
        for (int i = 0; i < a.length; i++) {
            if (a[i][column] == val) {
                return true;
            }
        }
        return false;
    }

    // 是否包含在九宫格里面
    private static boolean containsGrid(int[][] a, int x,
            int y, int val) {
        // 找到所在九宫格的左上角
        int gridX = (x / 3) * 3;
        int gridY = (y / 3) * 3;

        for (int i = gridX; i < gridX + 3; i++) {
            for (int j = gridY; j < gridY + 3; j++) {
                if (a[i][j] == val) {
                    return true;
                }
            }
        }

        return false;
    }

    private static class Grid {
        public int index;

        public int x;

        public int y;

        public Queue candidates = new ArrayBlockingQueue(
                N);

        public Grid(int index, int x, int y) {
            this.index = index;
            this.x = x;
            this.y = y;
        }
    }
}

参考引用

• 本系列归档至
• 《Java 数据结构及算法实战》：
• 《数据结构和算法基础（Java 语言实现）》（柳伟卫著，北京大学出版社出版）：