Leetcode 37 Sudoku Solver 深搜基础题+位运算

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

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

image.png

...and its solution numbers marked in red.

强烈推荐的算法入门题,填数独,深搜方法完成,采用的标记方法依然和上一题一样,位操作。

http://blog.csdn.net/accepthjp/article/details/52448027

注意回溯

class Solution {
public:
    bool dfs(int dep,vector<vector<char>>& board,int vis[],int vis2[],int vis3[])
    {
        if(dep==81) return true; //全部填完
        int x=dep/9,y=dep%9;
        if(board[x][y]!='.')
            return dfs(dep+1,board,vis,vis2,vis3);
        else
        {
            for(int i=1;i<10;i++)
            {
                if(vis[x]&(1<<i) || vis2[y]&(1<<i) || vis3[x/3*3+y/3]&(1<<i)) continue;//不能填写该数字
                vis[x]|=(1<<i);
                vis2[y]|=(1<<i);
                vis3[x/3*3+y/3]|=(1<<i);
                if(dfs(dep+1,board,vis,vis2,vis3)) //可以填写该数字
                {
                    board[x][y]='0'+i;
                    return true;
                }
                vis[x]&=~(1<<i);
                vis2[y]&=~(1<<i);
                vis3[x/3*3+y/3]&=~(1<<i);
            }
        }
        return false; //此位置无数可填
    }
    void solveSudoku(vector<vector<char>>& board) 
    {
        int vis[9]={0},vis2[9]={0},vis3[9]={0};
        for(int i=0;i<9;i++)                     //预处理已经填好的位置
            for(int j=0;j<9;j++)
                if(board[i][j]!='.')
                {
                    int t=board[i][j]-'0';
                    vis[i]|=(1<<t);
                    vis2[j]|=(1<<t);
                    vis3[i/3*3+j/3]=(1<<t);
                }
        dfs(0,board,vis,vis2,vis3);
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏应兆康的专栏

Python Web - Flask笔记6

mysql级别的外键,还不够ORM,必须拿到一个表的外键,然后通过这个外键再去另外一张表中查找,这样太麻烦了。SQLAlchemy提供了一个relationsh...

1451
来自专栏程序员的碎碎念

ThinkPHP之数据库操作

数据库的操作是由模型来管理的,模型类的作用大多数情况是操作数据表的,如果按照系统的规范来命名模型类的话,大多数情况下是可以用模型的名字自动对应数据表的。 模型类...

2965
来自专栏同步博客

Redis命令总结及其基础知识讲述

  Redis拥有其他数据库不具备的数据结构,又拥有内存存储(这使得redis的速度非常快),远程操作(使得redis可以与多个客户端和服务器进行连接)、持久化...

823
来自专栏数据结构与算法

洛谷P1155 双栈排序(贪心)

现在进来一个\(7\),看上去很难判断\(7\)到底放在哪里,如果放\(A\),后面来个\(9\),再来个\(6\),我们就凉了。

902
来自专栏点滴积累

geotrellis使用(十一)实现空间数据库栅格化以及根据属性字段进行赋值

Geotrellis系列文章链接地址http://www.cnblogs.com/shoufengwei/p/5619419.html 目录 前言 安装空...

3687
来自专栏yw的数据分析

linux 的一些脑洞操作

把当前文件夹的文件名用","连接成一行,或者将多行转变为一行 ls | paste -s -d "," # -s 选项将输入进行一次性粘贴 ls | xarg...

3645
来自专栏生信宝典

Bookdown文档生成教程

bookdown是一款及其方便的编写技术文档或教材的工具,语法简洁,数据处理灵活。支持Rmarkdown或普通markdown通过pandoc软件转换为HTML...

5645
来自专栏IT派

Python 标准库之 LRU 缓存实现学习

LRU (Least Recently Used) 是缓存置换策略中的一种常用的算法。当缓存队列已满时,新的元素加入队列时,需要从现有队列中移除一个元素,LRU...

1212
来自专栏YouMeek

1.4 Elasticsearch DSL 常用语法介绍

课程环境 CentOS 7.3 x64 JDK 版本:1.8(最低要求),主推:JDK 1.8.0_121 Elasticsearch 版本:5.2.0 相关软...

1.4K10
来自专栏杨建荣的学习笔记

简单分析shared pool(一) (r3笔记46天)

oracle中的shared pool很重要,但是感觉知之甚少。今天想在原来的认识上能够有一点更深入的了解。 简单做了一个总结。 首先是转储一下shared ...

3417

扫码关注云+社区

领取腾讯云代金券