数独游戏(dfs)

在这里插入图片描述

代码注释如下
#include <iostream>
using namespace std;
const int N = 10;
bool col[N][N], rol[N][N], cell[3][3][N];
char g[N][N];
bool dfs(int x, int y) {    //用bool这样在找到一个方案就可以迅速退出
    if(y == 9)  x++, y = 0;     //若y超出边界,则第二行开始y = 0,x++
    if(x == 9)  {
        for(int i = 0; i < 9; i++) 
            cout << g[i] << endl;
        return true;//这里返回true让下面for里面中间的dfs直接结束,不在回溯,少枚举很多情况
        //并且是输出唯一解
    }
    if(g[x][y] != '.')  return dfs(x, y + 1);
    //g[x][y] == '.'
    for(int i = 0; i < 9; i++) {
        if(!col[y][i] && !rol[x][i] && !cell[x / 3][y / 3][i]) {
            g[x][y] = i + '1';
            col[y][i] = rol[x][i] = cell[x / 3][y / 3][i] = true;
            if(dfs(x, y + 1))   return true;//剪枝,dfs返回值是true上面输出了答案,不用再回溯,并且
            //这一枝递归直接结束。
            //恢复操作
            g[x][y] = '.';
            col[y][i] = rol[x][i] = cell[x / 3][y / 3][i] = false;
        }
    }
    return false;//如果某个方案失败,需要返回false让上面回溯
    //不加这个也不会输出结果,因为如果这一枝递归没成功,返回false上面才能回溯
}
int main() {
    for(int i = 0; i < 9; i++) {     
        cin >> g[i];
        for(int j = 0; j < 9; j++) {
            if(g[i][j] != '.') {
                int x = g[i][j] - '1';  //1-9映射到0-8(方便cell的下取整操作)
                rol[i][x] = true;
                col[j][x] = true;
                cell[i / 3][j / 3][x] = true;
            }
        }   
    }
    dfs(0, 0);
    return 0;
}

补充

//这样写也是对的,只不过没有剪枝,时间复杂度高些
bool dfs(int x, int y)
{
    if (y == 9) x ++, y = 0;
    if (x == 9)
    {
        for (int i = 0; i < 9; i ++ ) cout << g[i] << endl;
        return true;
    }

    if (g[x][y] != '.') return dfs(x, y + 1);

    for (int i = 0; i < 9; i ++ )
        if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i])
        {
            g[x][y] = i + '1';
            row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
            dfs(x, y + 1);//不同点
            row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
            g[x][y] = '.';
        }
        //没有返回值
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/425033.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

LeetCode---【链表的操作】

目录 206反转链表【链表结构基础】21合并两个有序链表【递归】我的答案【错误】自己修改【超出时间限制】在官方那里学到的【然后自己复写,错误】对照官方【自己修改】 160相交链表【未理解题目目的】在b站up那里学到的【然后自己复写,错误】【超出时间限制】对照官方【自己修改…

【微服务生态】Nginx

文章目录 一、概述二、Nginx 的安装三、常用命令四、Nginx 配置4.1 反向代理配置&#xff08;1&#xff09;反向代理实例1&#xff08;2&#xff09;反向代理实例2 4.2 负载均衡配置4.3 动静分离4.4 集群配置 五、nginx 原理与优化参数配置 一、概述 本次为简易版&#xff0c;…

【Web】速谈FastJson反序列化中JdbcRowSetImpl的利用

目录 简要原理分析 exp 前文&#xff1a;【Web】速谈FastJson反序列化中TemplatesImpl的利用 简要原理分析 前文的TemplatesImpl链存在严重限制&#xff0c;即JSON.parseObject()需要开启Feature.SupportNonPublicField fastjson的第二条链JdbcRowSetImpl&#xff0c;主要…

Android Gradle开发与应用 (三) : Groovy语法概念与闭包

1. Groovy介绍 Groovy是一种基于Java平台的动态编程语言&#xff0c;与Java是完全兼容&#xff0c;除此之外有很多的语法糖来方便我们开发。Groovy代码能够直接运行在Java虚拟机&#xff08;JVM&#xff09;上&#xff0c;也可以被编译成Java字节码文件。 以下是Groovy的一些…

STM32标准库开发——WDG看门狗

WDG&#xff08;Watchdo&#xff09;看门狗介绍 独立看门狗&#xff0c;独立运行&#xff0c;有自己的专门时钟——内部低速时钟LSI&#xff0c;只要在最晚喂狗时间前喂狗就不会导致自动复位 窗口看门狗&#xff0c;用的是APB1的时钟&#xff0c;不是独立的时钟。喂狗时间比较严…

汽车虚拟仿真技术的实现、应用和未来

汽车虚拟仿真技术是一种利用计算机模拟汽车运行的技术&#xff0c;以实现对汽车行为的分析、评估和改进。汽车虚拟仿真技术是汽车工业中重要的开发设计和测试工具&#xff0c;可以大大缩短产品研发周期、降低研发成本和提高产品质量。本文将从汽车虚拟仿真技术的实现过程、应用…

【详识JAVA语言】类和对象

面向对象的初步认知 什么是面向对象 Java是一门纯面向对象的语言(Object Oriented Program&#xff0c;简称OOP)&#xff0c;在面向对象的世界里&#xff0c;一切皆为对象。面向对象是解决问题的一种思想&#xff0c;主要依靠对象之间的交互完成一件事情。用面向对象的思想来…

排序算法——快速排序的非递归写法

快速排序的非递归 我们写快速排序的时候&#xff0c;通常用的递归的方法实现快速排序&#xff0c;那么有没有非递归的方法实现快速排序呢&#xff1f;肯定是有的。思想还是一样的&#xff0c;不过非递归是看似是非递归其实还是递归。 思路解释 快速排序的非递归使用的是栈这…

【yolov8部署实战】VS2019+Onnxruntime环境部署yolov8-seg分割模型|含详细注释源码

0、前言 在之前博客中已经实现用onnxruntime来部署yolov8的目标检测模型&#xff08;cpu和gpu皆可&#xff09;。感兴趣的可以看看&#xff1a;【yolov8部署实战】VS2019环境下使用Onnxruntime环境部署yolov8目标检测|含源码 今天为大家带来的是yolov8-seg分割模型用onnxrunt…

Maven(黑马学习笔记)

初识Maven 什么是Maven Maven是Apache旗下的一个开源项目&#xff0c;是一款用于管理和构建java项目的工具。 官网&#xff1a;https://maven.apache.org/ Apache 软件基金会&#xff0c;成立于1999年7月&#xff0c;是目前世界上最大的最受欢迎的开源软件基金会&#xff0…

springer模板参考文献不显示

Spring期刊模板网站&#xff0c;我的问题是23年12月的版本 https://www.springernature.com/gp/authors/campaigns/latex-author-support/see-where-our-services-will-take-you/18782940 参考文献显示问好&#xff0c;在sn-article.tex文件中&#xff0c;这个sn-mathphys-num…

【MySQL】索引(重点)-- 详解

一、索引 没有索引&#xff0c;可能会有什么问题&#xff1f; 索引 &#xff1a;提高数据库的性能&#xff0c;索引是物美价廉的东西了。不用加内存&#xff0c;不用改程序&#xff0c;不用调 sql &#xff0c;只要执行正确的 create index &#xff0c;查询速度就可能提高成…

Java集合-ArraysLIst集合

集合是“由若干个确定的元素锁构成的整体”&#xff0c;在程序中&#xff0c;一般代表保存若干个元素(数据)的某种容器类。在Java中&#xff0c;如果一个Java对象可以在内部持有(保存)若干其他Java对象&#xff0c;并对外提供访问接口&#xff0c;我们把这种Java对象的容器称为…

Sora模型风口,普通人如何抓住-最新AI系统ChatGPT网站源码,AI绘画系统

一、前言说明 PandaAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;那么如何搭建部署AI创作ChatGPT&#xff1f;小编这里写一个详细图文教程吧。已支持…

python标识符、变量和常量

一、保留字与标识符 1.1保留字 保留字是指python中被赋予特定意义的单词&#xff0c;在开发程序时&#xff0c;不可以把这些保留字作为变量、函数、类、模块和其它对象的名称来使用。 比如&#xff1a;and、as、def、if、import、class、finally、with等 查询这些关键字的方…

通过 Jenkins 经典 UI 创建一个基本流水线

通过 Jenkins 经典 UI 创建一个基本流水线 点击左上的 新建任务。 在 输入一个任务名称字段&#xff0c;填写你新建的流水线项目的名称。 点击 流水线&#xff0c;然后点击页面底部的 确定 打开流水线配置页 点击菜单的流水线 选项卡让页面向下滚动到 流水线 部分 在 流水线 …

软考55-上午题-【数据库】-数据库设计步骤1

一、数据库设计的步骤 新奥尔良法&#xff0c;四个主要阶段&#xff1a; 1、用户需求分析&#xff1a;手机用户需求&#xff0c;确定系统边界&#xff1b; 2、概念设计&#xff08;概念结构设计&#xff09;&#xff1a;是抽象概念模型&#xff0c;较理想的是采用E-R方法。 …

uniapp聊天记录本地存储(详细易懂)

目录 目录 1、通过websocket拿取数据 2、获取聊天数据 3、聊天信息存储 、更新 4、读取聊天记录 5、发送信息&#xff0c;信息获取 6、最终效果 1.聊天信息的存储格式 2、样式效果 写聊天项目&#xff0c;使用到了本地存储。需要把聊天信息保存在本地&#xff0c;实时获…

如何限制一个账号只在一处登陆

大家好&#xff0c;我是广漂程序员DevinRock&#xff01; 1. 需求分析 前阵子&#xff0c;和问答群里一个前端朋友&#xff0c;随便唠了唠。期间他问了我一个问题&#xff0c;让我印象深刻。 他问的是&#xff0c;限制同一账号只能在一处设备上登录&#xff0c;是如何实现的…

Vue中如何实现动态路由?

在前端开发中&#xff0c;Vue.js 是一个极为流行的 JavaScript 框架&#xff0c;提供了灵活性和易用性&#xff0c;使得开发者可以快速构建单页面应用&#xff08;SPA&#xff09;。在 Vue 中&#xff0c;我们经常需要处理动态路由的情况&#xff0c;比如根据用户的操作或者权限…