文档章节

数独

一贱书生
 一贱书生
发布于 2017/01/20 11:28
字数 813
阅读 31
收藏 0

题目描述

问题描述:数独(Sudoku)是一款大众喜爱的数字逻辑游戏。
玩家需要根据9X9盘面上的已知数字,推算出所有剩余空格的数字,
并且满足每一行、每一列、每一个粗线宫内的数字均含1-9,并且不重复。
输入:
包含已知数字的9X9盘面数组[空缺位以数字0表示]
输出:
完整的9X9盘面数组

输入描述

包含已知数字的9X9盘面数组[空缺位以数字0表示]

输出描述

完整的9X9盘面数组

输入例子

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;

/**
 * Declaration: All Rights Reserved !!!
 */
public class Main {
    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
        Scanner scanner = new Scanner(Main.class.getClassLoader().getResourceAsStream("data3.txt"));
        while (scanner.hasNext()) {
            int[][] sudoku = new int[9][9];

            for (int i = 0; i < 9; i++) {
                sudoku[i] = new int[9];
            }

            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sudoku[i][j] = scanner.nextInt();
                }
            }

            System.out.println(solve(sudoku));
        }

        scanner.close();
    }

    /**
     * 解决数独问题
     *
     * @param sudoku 数独棋盘
     * @return 结果
     */
    private static String solve(int[][] sudoku) {
        boolean[] f = {false};
        // 未处理前
//        System.out.println(sudokuToString(sudoku));
        solve(sudoku, 0, f);

        return sudokuToString(sudoku);
    }

    private static String sudokuToString(int[][] sudoku) {
        StringBuilder b = new StringBuilder(256);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                b.append(sudoku[i][j]).append(' ');
            }

            b.setCharAt(b.length() - 1, '\n');
        }

        return b.substring(0, b.length() - 1);
    }

    /**
     * 从第row行开始解决数独问题
     *
     * @param sudoku 数独划棋盘
     * @param finish 是否已经完成
     * @param r      开始处理的行
     */
    private static void solve(int[][] sudoku, int r, boolean[] finish) {

        // 如果已经完成就
        if (finish[0] || r > 8) {
            return;
        }

        int row = r;
        int col = 0;
        boolean find = false;

        // 从r行开始找第一个未处理的格子
        for (int i = r; i < 9 && !find; i++) {
            for (int j = 0; j < 9; j++) {
                if (sudoku[i][j] == 0) {
                    row = i;
                    col = j;
                    find = true;
                    break;
                }
            }
        }

        // 找到末处理的
        if (find) {

            boolean[] used = new boolean[10];

            // 标记第row行,第col列已经使用过的数字
            for (int i = 0; i < 9; i++) {
                used[sudoku[row][i]] = true;
                used[sudoku[i][col]] = true;
            }

            // 数独划棋盘的方格
            // (0, 0),(0, 1),(0, 2)
            // (1, 0),(1, 1),(1, 2)
            // (2, 0),(2, 1),(2, 2)

            // 标记[row, col]在第几个方格中
            int x = row / 3;
            int y = col / 3;

            for (int i = x * 3; i < (x + 1) * 3; i++) {
                for (int j = y * 3; j < (y + 1) * 3; j++) {
                    used[sudoku[i][j]] = true;
                }
            }

            // used中末被标记的说明可以使用,下标为0的不使用
            for (int i = 1; i < used.length; i++) {
                // 未被标记,说明sudoku[row][col]可以为i
                if (!used[i]) {
                    sudoku[row][col] = i;
                    used[i] = true;

                    // 处理下一个未填写的位置
                    solve(sudoku, row, finish);

                    // 如果找到方案就返回
                    if (finish[0]) {
                        return;
                    }

                    // 现场还原
                    sudoku[row][col] = 0;
                    used[i] = false;
                }
            }


        }
        // 没有找到未处理的,说明已经完成了解决方案
        else {
            finish[0] = true;
            return;
        }
    }
}

© 著作权归作者所有

上一篇: 24点运算
下一篇: 人民币转换
一贱书生
粉丝 20
博文 724
码字总数 600123
作品 0
私信 提问
shenxgan/sudoku

数独生成与求解 记得第一次写数独的算法的时候是在大学期间,那时候闲来无事;在手机上玩着数独游戏,看着自己解不出来的题,想着是不是折腾折腾数独,写出一个求解数独的算法出来。 想到就做...

shenxgan
2017/04/28
0
0
PostgreSQL 生成任意基数数独 - 3

标签 PostgreSQL , 数独 背景 使用随机填充的方法,很难生成一个有解的数独。 《PostgreSQL 生成任意基数数独 - 2》 本文使用了《编程之美》中提到的另一种生成随机数独的方法,模板+映射法。...

德哥
2018/04/18
0
0
PostgreSQL 生成任意基数数独 - 2

标签 PostgreSQL , 数独 背景 《PostgreSQL 生成任意基数数独 - 1》 提供了一种方法,计算一个未完成的数独矩阵每个像素在XYB方向上还有多少个未填充的像素。 通过XYB的值,进行各种排序,选...

德哥
2018/04/18
0
0
数独完全解生成-分组轮转算法

数独(日语:数独すうどく)是一种源自18世纪末的瑞士,后在美国发展、并在日本得以发扬光大的数学智力拼图游戏。拼图是九宫格(即3格宽×3格高)的正方形状,每一格又细分为一个九宫格。在每...

9plus
2017/11/12
0
0
请问各位大神在JAVA中同一个工程下的两个包之间如何实现数据传递?

该工程是关于数独的生成与破解,该两个包为"数独挖洞算法设计"跟“数独棋盘文件管理”。其中在包“数独挖洞算法设计”中我已实现了数独的生成与破解功能,并且用二维数组的形式跟字符数组的形...

桔子大人
2015/09/16
1K
3

没有更多内容

加载失败,请刷新页面

加载更多

zk中选举Leader时的网络IO QuorumCnxManager解析

每台服务启动过程中,会启动一个QuorumCnxManager,负责各台服务器之间底层Leader选举过程中的网络通信 当集群中有服务器服务中断时,zk会重新选举leader 内部类 Message定义消息结构 包含了...

writeademo
9分钟前
2
0
使用mdBook 替代 gitbook。

###** 为什么要替代gitbook** gitbook 有个模板问题:如果md文件中有连续的大括号(比如:&{{父亲 40}}),gitbook会把{{ 父亲 40 }}中的父亲 40当做一个模板变量。如果这个变量不存在,会报...

王坤charlie
12分钟前
2
0
TL-A7HSAD采集卡硬件的处理器、NOR FLASH、DDR3

TL-A7HSAD是一款由广州创龙基于Xilinx Artix-7系列FPGA自主研发的高速数据采集卡,可配套广州创龙TMS320C6655、TMS320C6657、TMS320C6678开发板使用。该采集卡包含1个双通道250MSPS*12Bit的高...

Tronlong创龙
24分钟前
2
0
项目启动报fastjson版本可能过低

进行项目启动的过程中,之前都正常,这次启动突然就失败了: 查看日志说的是版本过低,后来查看官方网站版本,替换了最新版本: 选择了最新版本的1.2.60,1.2.62尝试后都不行,后来查看网上搜...

aiChuang
24分钟前
2
0
McDonald’s is using Alexa and Google to accepting job applications

McDonald’s today announced a new initiative the fast food chain is calling the “Apply Thru,” in which owners of Amazon Alexa or Google Assistant devices can begin job applic......

wowloop
28分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部