[leetcode] sudoku solver:暴力还是优化

2024-04-09 01:08

本文主要是介绍[leetcode] sudoku solver:暴力还是优化,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. backtracking

Sudoku是典型的backtracking问题,有关backtracking的问题《The Algorithm Design Manual》 7.1章解释的最详细易懂。Backtracking的定义如下:

Backtracking is a systemic way to iterate through all the possible configurations of a search space.

简而言之,backtracking就是通过遍历所有组合,并从中找出符合条件的结果集的一种方法。因此,一种非常直观的backtracking算法可以描述如下:

// array: 保存了[0, step-1]每一步的选择
// step: 当前是第几步backtracking(array, step)
{// 判断前step步的选择是否可以构成一个结果if (is_a_solution(array, step)) {process_solution(array, step);} else {step++;// 获取下一步的所有选择condidates = construct_candidates(array, step);foreach c in condidates {// 对每一种选择,继续递归下去array[step] = c;make_move(array, step);backtracking(array, step);unmake_move(array, step);}}
}

其中重要函数有这样几个:

  • is_a_solution:判断当前组合是否是一个期望的结果
  • process_solution:处理结果,例如打印出来
  • construct_candidates:获取下一步的所有选择。注意,这里并没有说明如何选择下一步该如何进行,大多数情况下,这个函数还应当有选择下一步的功能
  • make_move:向前进一步。通常这意味着在array中填充这一步的所选择的的值
  • unmake_move:向后退一步。通常这意味着在array中将这一步的值清空

对于数独问题,套用上面的算法,大概步骤如下:

#define DIMENSION 3;
bool solve(vector<vector<char> > &board, int step) {// 1. is_a_solutionif (step == DIMENSION*DIMENSION*9) return true;// 2. get next square and its all candidatesint row = 0, col = 0;   // position to move next, start from 0;set<char> possible_values;get_next_square(board, row, col, possible_values, step);for (set<char>::iterator it = possible_values.begin(); it != possible_values.end(); ++it) {board[row][col] = *it;				// make_moveif (solve(board, step+1)) return true;board[row][col] = EMPTY;			// unmake_move}return false;
}

2. 如何选择下一步

backtracking主要有两种应用:

  • 获取所有组合。典型问题:
    • Letter Combinations of a Phone Number:给出电话号码,求电话号码对应的所有字符串
    • Generate Parentheses:求所有n对括号"()"组成的字符串
    • Combination Sum:给定一组数字和一个target值,求所有和等于target的组合(组合中每个数字可以出现多次)
    • Combination Sum2:和Combination Sum问题一样,区别是组合中每个数字只能出现一次
    • Permutations:求一组数字的全排列
    • Permutations2:和Permutations问题一样,区别是给定的一组数字有重复,并且要求结果集中不能有重复的组合
  • 从所有的组合中找出符合条件的结果集。典型问题:
    • Sudoku Solver:数独解

第一类问题需要遍历所有解,有些特殊的情况无非是结果集中需要去重,这些都可以通过精细地选择”下一步的值“来做到。例如,在每一步中,可以对”这一步可选的值“做排序,相同的值只选一次,这样可以解决绝大多数”结果集去重“问题(例如Combination Sum2和Permutations2)

第二类问题与第一类问题有着根本不同。第二类问题可以在遍历一组组合的过程中,如果发现当前的组合已经不可能满足条件,则无需遍历完,即可在中途丢提当前的组合,直接跳到下一种组合。

考虑数独问题,首先,如果我们在构造一个组合的过程中,发现某个格子填入任何值都不可能满足条件,那么当前的组合无需再计算下去,必然是之前某些步出错。无需再计算当前还没有填充的其他格子的值,直接丢弃当前解,跳到上一步尝试其他值即可。

说道这里,其实还有一个最关键的问题没有细说,那就是如何选择下一步?

例如sudoku问题,最直观的做法是随机选择一个还是空白的格子,还能再优化吗?考虑这样的情况:假设当前空白的格子中,有一个格子有5种可能的值,有一个格子只有1个可能的值,那么应当先选择哪个格子?显然,选择只有1个可能值的格子更好。填充了这个格子,能够减少其他未填充格子的可选择值,也就降低了unmake_move的次数。

但是这样一定比随机选择更快吗?细心的读者能够发现,这样的选择方式,在每次选择下一步的时候,会花费相当的时间去查找”可选择值最少“的空白格子。每一步,我们对所有空白格子,计算它们的可选择值;计算可选择值的过程是查看当前行、当前列、当前9格。其实,这和随机选择一样,最后都会得到时间代价O(n^4)的算法。

3. 更多的优化

其实这里还有继续优化的空间,这里不详细展开,只说一下大概的思路。
  • 使用数组保留每个空白格子的可选值。每当有空白格被填入了数字,重新计算受影响的空白格的可选值(当前行、当前列、当前9格)
  • 不那么严格的选择。例如,我们可以只计算每个9格中的空白格的数量,从空白格最少的9格中,随机选出一个空白格,作为下一步要填充的格子。这是一种不那么严格的选择,好处是每个9格的空白格数量可以快速地计算出,同时保证了unmake_move的次数比随机选择要大大减少。

4. 暴力破解 VS 精细选择

每一步随机选择一个空白格,这其实就是一种暴力破解的方法,这里还有另一种暴力破解的方法,经过计算就会发现,其实两者的算法复杂度基本相当。前文提到的精细选择,如果精细选择的过程没有优化,算法的复杂度其实没有变化,有兴趣的同学可以自己证明和验证。



这篇关于[leetcode] sudoku solver:暴力还是优化的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/886831

相关文章

MyBatisPlus如何优化千万级数据的CRUD

《MyBatisPlus如何优化千万级数据的CRUD》最近负责的一个项目,数据库表量级破千万,每次执行CRUD都像走钢丝,稍有不慎就引起数据库报警,本文就结合这个项目的实战经验,聊聊MyBatisPl... 目录背景一、MyBATis Plus 简介二、千万级数据的挑战三、优化 CRUD 的关键策略1. 查

SpringBoot中HTTP连接池的配置与优化

《SpringBoot中HTTP连接池的配置与优化》这篇文章主要为大家详细介绍了SpringBoot中HTTP连接池的配置与优化的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录一、HTTP连接池的核心价值二、Spring Boot集成方案方案1:Apache HttpCl

PyTorch高级特性与性能优化方式

《PyTorch高级特性与性能优化方式》:本文主要介绍PyTorch高级特性与性能优化方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、自动化机制1.自动微分机制2.动态计算图二、性能优化1.内存管理2.GPU加速3.多GPU训练三、分布式训练1.分布式数据

MySQL中like模糊查询的优化方案

《MySQL中like模糊查询的优化方案》在MySQL中,like模糊查询是一种常用的查询方式,但在某些情况下可能会导致性能问题,本文将介绍八种优化MySQL中like模糊查询的方法,需要的朋友可以参... 目录1. 避免以通配符开头的查询2. 使用全文索引(Full-text Index)3. 使用前缀索

C#实现高性能Excel百万数据导出优化实战指南

《C#实现高性能Excel百万数据导出优化实战指南》在日常工作中,Excel数据导出是一个常见的需求,然而,当数据量较大时,性能和内存问题往往会成为限制导出效率的瓶颈,下面我们看看C#如何结合EPPl... 目录一、技术方案核心对比二、各方案选型建议三、性能对比数据四、核心代码实现1. MiniExcel

MySQL索引的优化之LIKE模糊查询功能实现

《MySQL索引的优化之LIKE模糊查询功能实现》:本文主要介绍MySQL索引的优化之LIKE模糊查询功能实现,本文通过示例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前缀匹配优化二、后缀匹配优化三、中间匹配优化四、覆盖索引优化五、减少查询范围六、避免通配符开头七、使用外部搜索引擎八、分

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

SpringBoot首笔交易慢问题排查与优化方案

《SpringBoot首笔交易慢问题排查与优化方案》在我们的微服务项目中,遇到这样的问题:应用启动后,第一笔交易响应耗时高达4、5秒,而后续请求均能在毫秒级完成,这不仅触发监控告警,也极大影响了用户体... 目录问题背景排查步骤1. 日志分析2. 性能工具定位优化方案:提前预热各种资源1. Flowable

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis