您当前的位置:首页 > 电脑百科 > 程序开发 > 语言 > C/C++/C#

使用C++实现数独求解器:解密数独的算法之美

时间:2023-11-05 13:41:07  来源:微信公众号  作者:鲨鱼编程

引言:

数独是一种经典的逻辑推理游戏,通过填充9x9方格中的数字,使得每一行、每一列和每一个3x3的小方格内都包含了1到9的数字,且不重复。本文将介绍如何使用C++编写一个数独求解器,通过算法实现自动解决数独难题的功能。

使用C++实现数独求解器:解密数独的算法之美

一、问题分析
数独求解问题可以看作是一个经典的递归回溯问题。我们需要设计一个算法,能够在填充数字的过程中遵循数独规则,并通过试错的方式解决数独难题。
二、算法实现
数独数据结构定义
我们可以使用一个二维数组来表示数独的初始状态和解决状态。定义一个9x9的整型数组board,其中0表示未填充的格子。
int board[9][9] = {
    {5, 3, 0, 0, 7, 0, 0, 0, 0},
    {6, 0, 0, 1, 9, 5, 0, 0, 0},
    {0, 9, 8, 0, 0, 0, 0, 6, 0},
    {8, 0, 0, 0, 6, 0, 0, 0, 3},
    {4, 0, 0, 8, 0, 3, 0, 0, 1},
    {7, 0, 0, 0, 2, 0, 0, 0, 6},
    {0, 6, 0, 0, 0, 0, 2, 8, 0},
    {0, 0, 0, 4, 1, 9, 0, 0, 5},
    {0, 0, 0, 0, 8, 0, 0, 7, 9}
};
回溯算法实现
通过递归回溯算法,我们可以遍历数独中的每一个未填充的格子,尝试填充1到9的数字,并逐步验证是否满足数独的规则。
bool solveSudoku(int row, int col) {
    if (row == 9) {
        // 数独已解决
        return true;
    }
    
    if (col == 9) {
        // 当前行已填充完毕,进入下一行
        return solveSudoku(row + 1, 0);
    }
    
    if (board[row][col] != 0) {
        // 当前格子已填充数字,进入下一列
        return solveSudoku(row, col + 1);
    }
    
    for (int num = 1; num <= 9; num++) {
        if (isValid(row, col, num)) {
            // 填充数字并进入下一列
            board[row][col] = num;
            if (solveSudoku(row, col + 1)) {
                return true;
            }
            // 回溯,尝试其他数字
            board[row][col] = 0;
        }
    }
    
    return false;
}
 
验证数独规则
在回溯算法中,我们需要编写验证函数isValid,用于判断填充的数字是否满足数独的规则。
bool isValid(int row, int col, int num) {
    // 判断当前数字是否已存在于同一行或同一列
    for (int i = 0; i < 9; i++) {
        if (board[row][i] == num || board[i][col] == num) {
            return false;
        }
    }
    
    // 判断当前数字是否已存在于同一个3x3的小方格内
    int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
    for (int i = startRow; i < startRow + 3; i++) {
        for (int j = startCol; j < startCol + 3; j++) {
            if (board[i][j] == num) {
                return false;
            }
        }
    }
    
    return true;
}
 
完整求解器实现
将上述代码整合起来,我们可以得到一个完整的数独求解器。
#include <IOStream>

using namespace std;

int board[9][9] = {
    {5, 3, 0, 0, 7, 0, 0, 0, 0},
    {6, 0, 0, 1, 9, 5, 0, 0, 0},
    {0, 9, 8, 0, 0, 0, 0, 6, 0},
    {8, 0, 0, 0, 6, 0, 0, 0, 3},
    {4, 0, 0, 8, 0, 3, 0, 0, 1},
    {7, 0, 0, 0, 2, 0, 0, 0, 6},
    {0, 6, 0, 0, 0, 0, 2, 8, 0},
    {0, 0, 0, 4, 1, 9, 0, 0, 5},
    {0, 0, 0, 0, 8, 0, 0, 7, 9}
};

bool isValid(int row, int col, int num) {
    // 判断当前数字是否已存在于同一行或同一列
    for (int i = 0; i < 9; i++) {
        if (board[row][i] == num || board[i][col] == num) {
            return false;
        }
    }
    
    // 判断当前数字是否已存在于同一个3x3的小方格内
    int startRow = (row / 3) * 3;
    int startCol = (col / 3) * 3;
    for (int i = startRow; i < startRow + 3; i++) {
        for (int j = startCol; j < startCol + 3; j++) {
            if (board[i][j] == num) {
                return false;
            }
        }
    }
    
    return true;
}

bool solveSudoku(int row, int col) {
    if (row == 9) {
        // 数独已解决
        return true;
    }
    
    if (col == 9) {
        // 当前行已填充完毕,进入下一行
        return solveSudoku(row + 1, 0);
    }
    
    if (board[row][col] != 0) {
        // 当前格子已填充数字,进入下一列
        return solveSudoku(row, col + 1);
    }
    
    for (int num = 1; num <= 9; num++) {
        if (isValid(row, col, num)) {
            // 填充数字并进入下一列
            board[row][col] = num;
            if (solveSudoku(row, col + 1)) {
                return true;
            }
            // 回溯,尝试其他数字
            board[row][col] = 0;
        }
    }
    
    return false;
}

void printBoard() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
}

int mAIn() {
    if (solveSudoku(0, 0)) {
        cout << "数独已解决:" << endl;
        printBoard();
    } else {
        cout << "数独无解" << endl;
    }
    
    return 0;
}
三、算法分析与优化
复杂度分析
数独求解器的时间复杂度取决于回溯的次数,最坏情况下需要尝试9的81次方次操作,但在实际应用中,由于数独问题的特殊性,通常可以在较少的回溯步骤内解决。
算法优化
为了提高数独求解器的效率,我们可以考虑以下优化措施:
启发式搜索:在回溯算法中使用启发式搜索策略,选择填充数字时优先选择可能性最小的格子,以减少回溯的次数。
剪枝操作:在验证数独规则时,可以使用剪枝操作,减少不必要的验证过程。例如,可以使用位运算来快速判断某一行、某一列或某一小方格内是否已存在某个数字。
五、总结
本文介绍了如何使用C++编写一个数独求解器,通过回溯算法实现自动解决数独难题的功能。我们讨论了算法的实现细节,并提出了一些优化措施以提高求解器的效率。数独求解器是一个典型的递归回溯问题,通过深入理解数独规则和合理设计算法,我们能够解决各种难度的数独问题。


Tags:C++   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
C++常见避坑指南
C++ 从入门到放弃?本文主要总结了在C++开发或review过程中常见易出错点做了归纳总结,希望借此能增进大家对C++的了解,减少编程出错,提升工作效率,也可以作为C++开发的避坑攻略。...【详细内容】
2024-04-03  Search: C++  点击:(4)  评论:(0)  加入收藏
C++ 之父反驳白宫警告:自诞生第一天起,C++ 的目标就一直是提高安全性
整理 | 郑丽媛上个月,美国白宫国家网络主任办公室(ONCD)在一份主题为《回到基础构件:通往安全软件之路》的 19 页 PDF 报告中,呼吁开发人员停止使用容易出现内存安全漏洞的编程语...【详细内容】
2024-03-25  Search: C++  点击:(4)  评论:(0)  加入收藏
八个 C++ 开源项目,帮助初学者进阶成长
通过参与或阅读开源项目的源代码,你可以获得丰富的实践机会。实际的项目代码比简单的教程更具挑战性,可以帮助你深入理解 C++ 的各种概念和技术。1.ThreadPool一个简单的 C++1...【详细内容】
2024-03-22  Search: C++  点击:(21)  评论:(0)  加入收藏
C++多线程编程:解锁性能与并发的奥秘
今天我们将深入探讨C++中的多线程编程,揭示多线程如何解锁性能潜力,提高程序的并发性能。什么是多线程?在计算机科学中,多线程是指一个进程(程序的执行实例)中的多个线程同时执行...【详细内容】
2024-02-03  Search: C++  点击:(68)  评论:(0)  加入收藏
C++代码优化攻略
今天我们将深入探讨C++性能优化的世界。在当今软件开发的浪潮中,高性能的代码是必不可少的。无论是开发桌面应用、移动应用,还是嵌入式系统,性能都是关键。1. 选择合适的数据结...【详细内容】
2024-01-26  Search: C++  点击:(113)  评论:(0)  加入收藏
C++质数检测器的设计与实现​
质数,作为数学中的一个基本概念,一直以其独特的性质吸引着众多研究者和爱好者。质数是指大于1的自然数中,除了1和它本身以外不再有其他因数的数。在实际应用中,质数检测也扮演着...【详细内容】
2024-01-15  Search: C++  点击:(110)  评论:(0)  加入收藏
指针变量在C/C++中的内存占用
在编程领域,尤其是C和C++这类底层语言中,指针是一个核心概念,它允许程序直接操作内存地址。然而,关于指针本身在内存中占用的空间大小,却常常让初学者感到困惑。本文将深入探讨这...【详细内容】
2024-01-09  Search: C++  点击:(94)  评论:(0)  加入收藏
C++的面向对象编程:深入解析与理解
当我们谈论C++时,面向对象编程(OOP)是一个无法回避的话题。那么,C++的面向对象究竟是什么?为什么它如此重要?本文将从基本概念到实际应用,为您详细解析C++中的面向对象编程。一、面...【详细内容】
2024-01-03  Search: C++  点击:(95)  评论:(0)  加入收藏
有什么好用的C/C++源代码混淆工具?
开始使用ipaguard前言iOS加固保护是直接针对ios ipa二进制文件的保护技术,可以对iOS APP中的可执行文件进行深度混淆、加密。使用任何工具都无法逆向、破解还原源文件。对APP...【详细内容】
2023-12-29  Search: C++  点击:(117)  评论:(0)  加入收藏
C++中new与malloc:内存分配机制深度解析
本文旨在深入探讨C++中new和malloc两种内存分配机制的区别。通过对比它们在内存分配、初始化、错误处理、调用构造函数/析构函数、类型转换和使用便捷性等方面的不同,我们将...【详细内容】
2023-12-27  Search: C++  点击:(126)  评论:(0)  加入收藏
▌简易百科推荐
C++常见避坑指南
C++ 从入门到放弃?本文主要总结了在C++开发或review过程中常见易出错点做了归纳总结,希望借此能增进大家对C++的了解,减少编程出错,提升工作效率,也可以作为C++开发的避坑攻略。...【详细内容】
2024-04-03  腾讯技术工程    Tags:C++   点击:(4)  评论:(0)  加入收藏
C++ 之父反驳白宫警告:自诞生第一天起,C++ 的目标就一直是提高安全性
整理 | 郑丽媛上个月,美国白宫国家网络主任办公室(ONCD)在一份主题为《回到基础构件:通往安全软件之路》的 19 页 PDF 报告中,呼吁开发人员停止使用容易出现内存安全漏洞的编程语...【详细内容】
2024-03-25    CSDN  Tags:C++   点击:(4)  评论:(0)  加入收藏
八个 C++ 开源项目,帮助初学者进阶成长
通过参与或阅读开源项目的源代码,你可以获得丰富的实践机会。实际的项目代码比简单的教程更具挑战性,可以帮助你深入理解 C++ 的各种概念和技术。1.ThreadPool一个简单的 C++1...【详细内容】
2024-03-22  AI让生活更美好  微信公众号  Tags:C++   点击:(21)  评论:(0)  加入收藏
C# 中15个值得收藏的开源项目推荐
在开源的世界里,C# 编程语言也占有一席之地。这些开源项目涵盖了多个领域,从框架、库到工具,它们为C#开发者提供了丰富的资源和工具,帮助他们更高效地开发、测试和部署应用程序...【详细内容】
2024-03-20  程序员编程日记  微信公众号  Tags:C#   点击:(29)  评论:(0)  加入收藏
C#异步编程:Task.Run vs. async-await,掌握基础与高级用法
概述:C#中的异步编程有两主要方式:Task.Run用于在后台线程执行同步操作,而async-await更适用于清晰表达异步流程。基础用法展示了它们的简单应用,高级用法则演示了它们的结合使...【详细内容】
2024-03-09  架构师老卢  今日头条  Tags:C#   点击:(22)  评论:(0)  加入收藏
C++多线程编程:解锁性能与并发的奥秘
今天我们将深入探讨C++中的多线程编程,揭示多线程如何解锁性能潜力,提高程序的并发性能。什么是多线程?在计算机科学中,多线程是指一个进程(程序的执行实例)中的多个线程同时执行...【详细内容】
2024-02-03     AI让生活更美好  Tags:C++   点击:(68)  评论:(0)  加入收藏
C++代码优化攻略
今天我们将深入探讨C++性能优化的世界。在当今软件开发的浪潮中,高性能的代码是必不可少的。无论是开发桌面应用、移动应用,还是嵌入式系统,性能都是关键。1. 选择合适的数据结...【详细内容】
2024-01-26  AI让生活更美好  微信公众号  Tags:C++   点击:(113)  评论:(0)  加入收藏
C# 线程本地存储为什么线程间值不一样
为什么用 ThreadStatic 标记的字段,只有第一个线程拿到了初始值,其他线程都是默认值,让我能不能帮他解答一下,尼玛,我也不是神仙什么都懂,既然问了,那我试着帮他解答一下,也给后面类...【详细内容】
2024-01-26  一线码农聊技术  微信公众号  Tags:C#   点击:(66)  评论:(0)  加入收藏
C++质数检测器的设计与实现​
质数,作为数学中的一个基本概念,一直以其独特的性质吸引着众多研究者和爱好者。质数是指大于1的自然数中,除了1和它本身以外不再有其他因数的数。在实际应用中,质数检测也扮演着...【详细内容】
2024-01-15  鲨鱼编程  微信公众号  Tags:C++   点击:(110)  评论:(0)  加入收藏
C# 登顶!超越Java或非空想
整理丨诺亚出品 | 51CTO技术栈(微信号:blog51cto)近日,TIOBE编程社区公布年度编程语言,此次摘得这一桂冠的是C#。这也是C#在TIOBE二十多年评选历史中首次赢得这一年度大奖。C#虽...【详细内容】
2024-01-15    51CTO  Tags:C#   点击:(112)  评论:(0)  加入收藏
站内最新
站内热门
站内头条