37. 解数独
2021/9/7 23:36:42
本文主要是介绍37. 解数独,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
https://leetcode-cn.com/problems/sudoku-solver/
难度困难936收藏分享切换为英文接收动态反馈
编写一个程序,通过填充空格来解决数独问题。
数独的解法需 遵循如下规则:
- 数字
1-9
在每一行只能出现一次。 - 数字
1-9
在每一列只能出现一次。 - 数字
1-9
在每一个以粗实线分隔的3x3
宫内只能出现一次。(请参考示例图)
数独部分空格内已填入了数字,空白格用 '.'
表示。
示例:
输入:board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] 输出:[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]] 解释:输入的数独如上图所示,唯一有效的解决方案如下所示:
提示:
board.length == 9
board[i].length == 9
board[i][j]
是一位数字或者'.'
- 题目数据 保证 输入数独仅有一个解
通过次数97,696提交次数145,663
class Solution { int [][] line = new int[9][9]; int [][] column = new int[9][9]; int [][][] block = new int[3][3][9]; boolean valid = false; List<int[]> blank = new ArrayList<int[]>(); public void solveSudoku(char[][] board) { for(int i=0;i<9;i++) { for(int j=0;j<9;j++) { if(board[i][j]=='.') { blank.add(new int[]{i,j}); } else { int x = board[i][j]-'0'-1; line[i][x] = column[j][x] = block[i/3][j/3][x]=1; } } } dfs(board, 0); } void dfs(char[][] board,int index) { if(index == blank.size()) { valid = true; return; } int[] blank_ = blank.get(index); int i = blank_[0]; int j = blank_[1]; for(int d =0 ;d < 9 && !valid;++d) { if(line[i][d]!=1 && column[j][d]!=1 && block[i/3][j/3][d]!=1) { line[i][d] = column[j][d] = block[i/3][j/3][d] = 1; board[i][j] = (char)(d+'0'+1); dfs(board,index+1); line[i][d] = column[j][d] = block[i/3][j/3][d] = 0; } } } }
这篇关于37. 解数独的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)