C++实现LeetCode(37.求解数独)

[LeetCode] 37. Sudoku Solver 求解数独

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.


A sudoku puzzle...


...and its solution numbers marked in red.

Note:

  • The given board contain only digits 1-9and the character '.'.
  • You may assume that the given Sudoku puzzle will have a single unique solution.
  • The given board size is always 9x9.

这道求解数独的题是在之前那道 Valid Sudoku 的基础上的延伸,之前那道题让我们验证给定的数组是否为数独数组,这道让求解数独数组,跟此题类似的有 Permutations,Combinations, N-Queens 等等,其中尤其是跟 N-Queens 的解题思路及其相似,对于每个需要填数字的格子带入1到9,每代入一个数字都判定其是否合法,如果合法就继续下一次递归,结束时把数字设回 '.',判断新加入的数字是否合法时,只需要判定当前数字是否合法,不需要判定这个数组是否为数独数组,因为之前加进的数字都是合法的,这样可以使程序更加高效一些,整体思路是这样的,但是实现起来可以有不同的形式。一种实现形式是递归带上横纵坐标,由于是一行一行的填数字,且是从0行开始的,所以当i到达9的时候,说明所有的数字都成功的填入了,直接返回 ture。当j大于等于9时,当前行填完了,需要换到下一行继续填,则继续调用递归函数,横坐标带入 i+1。否则看若当前数字不为点,说明当前位置不需要填数字,则对右边的位置调用递归。若当前位置需要填数字,则应该尝试填入1到9内的所有数字,让c从1遍历到9,每当试着填入一个数字,都需要检验是否有冲突,使用另一个子函数 isValid 来检验是否合法,假如不合法,则跳过当前数字。若合法,则将当前位置赋值为这个数字,并对右边位置调用递归,若递归函数返回 true,则说明可以成功填充,直接返回 true。不行的话,需要重置状态,将当前位置恢复为点。若所有数字都尝试了,还是不行,则最终返回 false。检测当前数组是否合法的原理跟之前那道 Valid Sudoku 非常的相似,但更简单一些,因为这里只需要检测新加入的这个数字是否会跟其他位置引起冲突,分别检测新加入数字的行列和所在的小区间内是否有重复的数字即可,参见代码如下:

解法一:

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        helper(board, 0, 0);
    }
    bool helper(vector<vector<char>>& board, int i, int j) {
        if (i == 9) return true;
        if (j >= 9) return helper(board, i + 1, 0);
        if (board[i][j] != '.') return helper(board, i, j + 1);
        for (char c = '1'; c <= '9'; ++c) {
            if (!isValid(board, i , j, c)) continue;
            board[i][j] = c;
            if (helper(board, i, j + 1)) return true;
            board[i][j] = '.';
        }
        return false;
    }
    bool isValid(vector<vector<char>>& board, int i, int j, char val) {
        for (int x = 0; x < 9; ++x) {
            if (board[x][j] == val) return false;
        }
        for (int y = 0; y < 9; ++y) {
            if (board[i][y] == val) return false;
        }
        int row = i - i % 3, col = j - j % 3;
        for (int x = 0; x < 3; ++x) {
            for (int y = 0; y < 3; ++y) {
                if (board[x + row][y + col] == val) return false;
            }
        }
        return true;
    }
};

还有另一种递归的写法,这里就不带横纵坐标参数进去,由于递归需要有 boolean 型的返回值,所以不能使用原函数。因为没有横纵坐标,所以每次遍历都需要从开头0的位置开始,这样无形中就有了大量的重复检测,导致这种解法虽然写法简洁一些,但击败率是没有上面的解法高的。这里的检测数组冲突的子函数写法也比上面简洁不少,只用了一个 for 循环,用来同时检测行列和小区间是否有冲突,注意正确的坐标转换即可,参见代码如下:

解法二:

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        helper(board);
    }
    bool helper(vector<vector<char>>& board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') continue;
                for (char c = '1'; c <= '9'; ++c) {
                    if (!isValid(board, i, j, c)) continue;
                    board[i][j] = c;
                    if (helper(board)) return true;
                    board[i][j] = '.';
                }
                return false;
            }
        }
        return true;
    }
    bool isValid(vector<vector<char>>& board, int i, int j, char val) {
        for (int k = 0; k < 9; ++k) {
            if (board[k][j] != '.' && board[k][j] == val) return false;
            if (board[i][k] != '.' && board[i][k] == val) return false;
            int row = i / 3 * 3 + k / 3, col = j / 3 * 3 + k % 3;
            if (board[row][col] != '.' && board[row][col] == val) return false;
        }
        return true;
    }
};

到此这篇关于C++实现LeetCode(37.求解数独)的文章就介绍到这了,更多相关C++实现求解数独内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现LeetCode(32.最长有效括号)

    [LeetCode] 32. Longest Valid Parentheses 最长有效括号 Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. Example 1: Input: "(()" Output: 2 Explanation: The longest valid

  • C++实现LeetCode(36.验证数独)

    [LeetCode] 36. Valid Sudoku 验证数独 Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits 1-9without repetition. Each column must contain the digits 1-9 wi

  • C++实现LeetCode(33.在旋转有序数组中搜索)

    [LeetCode] 33. Search in Rotated Sorted Array 在旋转有序数组中搜索 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If f

  • C++实现LeetCode(28.实现strStr()函数)

    [LeetCode] 28. Implement strStr() 实现strStr()函数 Implement strStr(). Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Example 1: Input: haystack = "hello", needle = "ll" Output: 2 E

  • C++实现LeetCode(31.下一个排列)

    [LeetCode] 31. Next Permutation 下一个排列 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sor

  • C++实现LeetCode(30.串联所有单词的子串)

    [LeetCode] 30. Substring with Concatenation of All Words 串联所有单词的子串 You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words ex

  • C++实现LeetCode(29.两数相除)

    [LeetCode] 29. Divide Two Integers 两数相除 Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer division should truncate

  • C++实现LeetCode(37.求解数独)

    [LeetCode] 37. Sudoku Solver 求解数独 Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must

  • Python图像识别+KNN求解数独的实现

    Python-opencv+KNN求解数独 最近一直在玩数独,突发奇想实现图像识别求解数独,输入到输出平均需要0.5s. 整体思路大概就是识别出图中数字生成list,然后求解. 输入输出demo 数独采用的是微软自带的Microsoft sudoku软件随便截取的图像,如下图所示: 经过程序求解后,得到的结果如下图所示: 程序具体流程 程序整体流程如下图所示: 读入图像后,根据求解轮廓信息找到数字所在位置,以及不包含数字的空白位置,提取数字信息通过KNN识别,识别出数字:无数字信息的在list中

  • JavaScript遍历求解数独问题的主要思路小结

    数独规则 数独游戏,经典的为9×9=81个单元格组成的九宫格,同时也形成了3×3=9个小九宫格,要求在81个小单元格中填入数字1~9,并且数字在每行每列及每个小九宫格中都不能重复. 数独技巧 直观法 候选数法 相关二十格:一个数字只与其所在行列及小九宫格的二十格相关 我的思路 精心设计了有效性判定函数,最多一次遍历81个小单元格就能做出方案的有效性判定. 同理设计了相关20格判定,一次0~9的循环就完成有效性判定. 用数组模拟堆栈,为搜索提供回溯信息. 利用对象具有map性质,来辅助判断方案的有

  • java使用回溯法求解数独示例

    复制代码 代码如下: import java.util.Calendar;import java.util.Date; public class Matrix { private int matrix[][]; private long timeAfter=0;  private long timeBefore =0; public Matrix(int m[][]) {  matrix = new int[9][9];  for (int i=0; i<9 ; i++)   for(int j

  • C# 数独求解算法的实现

    前言 数独是一种有趣的智力游戏,但是部分高难度数独在求解过程中经常出现大量单元格有多个候选数字可以填入,不得不尝试填写某个数字然后继续推导的方法.不幸的是这种方法经常出现填到一半才发现有单元格无数可填,说明之前就有单元格填错了把后面的路堵死了.这时就需要悔步,之前的单元格换个数重新试.然而更坑的是究竟要悔多少步呢?不知道.要换数字的时候该换哪个呢?也不知道.手算时就需要大量草稿纸记录填写情况,不然容易忘了哪些试过哪些没试过. 在朋友那里玩他手机上的数独的时候就发现这个问题很烦,到这里其实就不是一

  • 基于Matlab制作一个数独求解器

    目录 1.完整效果 2.数独求解(错误示范) 3.数独求解(升维) 4.数字识别 5.GUI / APP 讲解一个完整的小项目,顺便说明如何使用整数规划求解数独. 1.完整效果 2.数独求解(错误示范) 首先我们先尝试如果只满足行.列.3x3块加和均为45的等式约束是否有效.即约束为: 每行和为45: 每列和为45: 每个3x3块和为45: 其中对此编写如下代码: sudokuMat=[1 0 5 0 2 0 0 0 0 0 0 0 7 4 3 0 0 5 3 0 7 0 0 0 0 0 9 0

  • 利用JavaScript做数独的完整实现过程

    目录 前言 怎么解数独 填第一个格子 填第二个格子 填第三个格子 填第九个格子 综上所述 通过代码来实现 动态展示做题过程 九宫格样式 做题逻辑 总结 前言 最近看到老婆天天在手机上玩数独,突然想起 N 年前刷 LeetCode 的时候,有个类似的算法题(37.解数独),是不是可以把这个算法进行可视化. 说干就干,经过一个小时的实践,最终效果如下: 怎么解数独 解数独之前,我们先了解一下数独的规则: 数字 1-9 在每一行只能出现一次. 数字 1-9 在每一列只能出现一次. 数字 1-9 在每一

  • Java实现求解一元n次多项式的方法示例

    本文实例讲述了Java实现求解一元n次多项式的方法.分享给大家供大家参考,具体如下: 项目需要做趋势预测,采用线性拟合.2阶曲线拟合和指数拟合的算法,各种线性拟合算法写成矩阵大概是这么个形式: 其中x是横坐标采样值,y是纵坐标采样值,i是采样点序列号,a是系数,N是采样点个数,n是阶数,所以线性拟合最后就转成了一个解高阶方程组的问题. 不知道有没有什么好用的java矩阵运算的包,我很不擅长搜集这种资料,所以只好捡起了已经放下多年的线性代数,自己写了个java程序用增广矩阵的算法来解高阶方程组.直

  • 简单实现java数独游戏

    本文实例为大家分享了java数独游戏的具体代码,供大家参考,具体内容如下 打算把javaFx需要的组件装好以后直接用javaFx的,但似乎eclipse的版本不对,安装了也不能用... 数独代码是在之前寒假受命写的,学了一个月java的成果,现在看来有些不足但毕竟是第一个程序,就直接放上来,数独终盘的实现直接用了暴力,时间复杂度有点高,懒得改了直接放代码 终盘实现: import java.util.Random; public class SudokuPuzzleGenerator { pri

随机推荐