《每周一道算法题》（九）有效的数独

一题目

36. 有效的数独

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

image.png

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1:

输入:
[
  ["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"]
]
输出: true

示例 2:

输入:
[
  ["8","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"]
]
输出: false

解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明:

一个有效的数独（部分已被填充）不一定是可解的。

只需要根据以上规则，验证已经填入的数字是否有效即可。

给定数独序列只包含数字 1-9 和字符 '.' 。

给定数独永远是 9x9 形式的。

二解题思路一

2.1 计算每个数字所在九宫格的位置

image.png

假设row是行号，col是列号，box_index是九宫格的位置，则

boxIndex = (row / 3) * 3 + col / 3;

比如低7列第2行

核心代码如下

/// 有效的数独
- (BOOL)isValidSudoku:(NSArray<NSArray *> *)board {
    NSMutableArray<NSMutableArray *> *rows = [NSMutableArray array];
    NSMutableArray<NSMutableArray *> *cols = [NSMutableArray array];
    NSMutableArray<NSMutableArray *> *boxes = [NSMutableArray array];
    // 赋值数据
    for (int i = 0; i < 9; i++) {
        [rows addObject:[NSMutableArray array]];
        [cols addObject:[NSMutableArray array]];
        [boxes addObject:[NSMutableArray array]];
    }
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            NSString *num = board[row][col];
            if ([num isEqualToString:@"."]) {
                continue;
            }
            
            if ([rows[row] containsObject:num]) {
                return false;
            }
            if ([cols[col] containsObject:num]) {
                return false;
            }
            // 计算每个数字所在九宫格的位置
            int boxIndex = (row / 3) * 3 + col / 3;
            if ([boxes[boxIndex] containsObject:num]) {
                return false;
            }
            
            // 表示未出现过,则添加进数组中
            [rows[row] addObject:num];
            [cols[col] addObject:num];
            [boxes[boxIndex] addObject:num];
        }
    }
    return true;
}

测试代码

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view, typically from a nib.
    NSArray<NSArray *> *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"]];
    
    NSArray<NSArray *> *board1 = @[
                                  @[@"8",@"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"]];
    
    BOOL result = [self isValidSudoku:board];
    BOOL result1 = [self isValidSudoku:board1];
    
    NSLog(@"result = %d, result2 = %d",result,result1);
}

运行结果

2019-12-08 20:39:43.251030+0800 09_ValidSudoku[44098:1854283] result = 1, result2 = 0

三解题思路二

数组使用bool类型值变量

/// 有效的数独
- (BOOL)isValidSudoku2:(NSArray<NSArray *> *)board {
    NSMutableArray<NSMutableArray *> *rows = [NSMutableArray array];
    NSMutableArray<NSMutableArray *> *cols = [NSMutableArray array];
    NSMutableArray<NSMutableArray *> *boxes = [NSMutableArray array];
    
    // 赋值数据 - bool类型数据
    for (int i = 0; i < 9; i++) {
        NSMutableArray<NSNumber *> *bools = [NSMutableArray array];
        for (int j = 0; j < 9; j++) {
            [bools addObject:@(0)];
        }
        [rows addObject:bools.mutableCopy];
        [cols addObject:bools.mutableCopy];
        [boxes addObject:bools.mutableCopy];
    }
    
    int temNum = 0;
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            NSString *num = board[row][col];
            if ([num isEqualToString:@"."]) {
                continue;
            }
            temNum = num.intValue - 1;
            if ([rows[row][temNum] intValue]) {    // 表示之前第row行,temNum列出现过num元素
                return false;
            }
            if ([cols[col][temNum] intValue]) {    // 表示之前第col行,temNum列出现过num元素
                return false;
            }
            // 计算每个数字所在九宫格的位置
            int boxIndex = (row / 3) * 3 + col / 3;
            if ([boxes[boxIndex][temNum] intValue]) {
                return false;
            }
            
            // 表示未出现过,在temNum位置置为1
            rows[row][temNum] = @(1);
            cols[col][temNum] = @(1);
            boxes[boxIndex][temNum] = @(1);
        }
    }
    return true;
}

运行结果

2019-12-08 22:31:52.520964+0800 09_ValidSudoku[46472:1972554] result = 1, result2 = 0

四解题思路三

使用字节运算

image.png

举例如下
1.比如 row = 0, col = 0, num = 5，则将5所在位置1 << (num - 1)，即1左移4位处置为1.

9 8 7 6 5 4 3 2 1 
0 0 0 0 1 0 0 0 0

2.比如 row = 0, col = 1, num = 3，则将3所在位置1 << (num - 1)，即1左移2位处置为1.

9 8 7 6 5 4 3 2 1 
0 0 0 0 0 0 1 0 0

然后再将值进行累加，即 000010000 + 000000100

核心算法如下

/// 有效的数独
- (BOOL)isValidSudoku3:(NSArray<NSArray *> *)board {
    NSMutableArray<NSNumber *> *rows = [NSMutableArray array];
    NSMutableArray<NSNumber *> *cols = [NSMutableArray array];
    NSMutableArray<NSNumber *> *boxes = [NSMutableArray array];
    
    // 赋值数据
    for (int i = 0; i < 9; i++) {
        [rows addObject:@(0)];
        [cols addObject:@(0)];
        [boxes addObject:@(0)];
    }
    
    /** 解释说明 第一行第一列为5的时候
     9 8 7 6 5 4 3 2 1
     0 0 0 0 0 0 0 0 0
     0 0 0 0 1 0 0 0 0 &
     -------------------
     0 0 0 0 0 0 0 0 0 如果为零,表示5之前没有出现过,否则出现过
     */
    int temNum = 0;
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            NSString *num = board[row][col];
            if ([num isEqualToString:@"."]) {
                continue;
            }
            temNum = 1 << (num.intValue - 1);   // 比如5,则1左移4位
            if ((rows[row].intValue & temNum) != 0) {
                return false;
            }
            if ((cols[col].intValue & temNum) != 0) {
                return false;
            }
            // 计算每个数字所在九宫格的位置
            int boxIndex = (row / 3) * 3 + col / 3;
            if ((boxes[boxIndex].intValue & temNum) != 0) {
                return false;
            }
            
            // 表示未出现过,在temNum位置置为1
            // 比如 row = 0,col = 0, num = 5,则在第5个位置为1,即1左移4位, 0 0 0 0 1 0 0 0 0
            rows[row] = @(rows[row].intValue + (1 << (num.intValue - 1)));
            cols[col] = @(cols[col].intValue + (1 << (num.intValue - 1)));
            boxes[boxIndex] = @(boxes[boxIndex].intValue + (1 << (num.intValue - 1)));
        }
    }
    return true;
}

运行结果如下

2019-12-10 22:47:37.233659+0800 09_ValidSudoku[51403:2236090] result = 1, result2 = 0

到此为止，每周一道算法题就告一段落了，喜欢我的文章可以阅读我的其他文章。

本文参考MJ老师的每周一道算法题

项目链接地址- 09_ValidSudoku

每周一道算法题 - 笔记

最后编辑于：2020.03.14 17:43:26

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,919评论 6赞 502
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,567评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 163,316评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,294评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,318评论 6赞 390
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,245评论 1赞 299
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,120评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,964评论 0赞 275
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,376评论 1赞 313
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,592评论 2赞 333
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,764评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,460评论 5赞 344
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,070评论 3赞 327
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,697评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,846评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,819评论 2赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,665评论 2赞 354

《每周一道算法题》（九）有效的数独

一 题目

36. 有效的数独

二 解题思路一

2.1 计算每个数字所在九宫格的位置

三 解题思路二

四 解题思路三

推荐阅读更多精彩内容

一题目

二解题思路一

三解题思路二

四解题思路三