全民数独-数图模式破解-python

本人下载玩全民数独游戏至今已经有一个多月，期间数图模式特级难度的关卡也已经连续过四十来关，游戏思路早已明了，现在突发奇想要脱坑，特意写了个程序，对游戏的逻辑进行破解，一方面希望能使我对游戏丧失兴趣，另一方面希望可以锻炼下自己的编程思维和水平。

---

游戏截图：

游戏界面.jpg
已破关数.jpg

---

逻辑思路：

1. 根据每行（列）的提示数字，列举该行（列）格子所有可能出现的情况（可行性方案）
2. 通过目前每行（列）已确定属性的格子，对可行性方案进行排除
3. 在剩余的可行性方案中，将每行中可能性一致的格子属性确定下来
4. 对每行每列都按上述步骤执行一遍
5. 判断整个画布上已确定属性的格子总数是否和行（或列）提示数字总数是否一致，是的话就结束程序，否则再重复执行2、3、4步骤

---

python编程实现：

# !/usr/bin/env python3
# -*- coding: utf-8 -*-

__author__ = '孙思锴'

from pandas import DataFrame
import copy
from itertools import combinations_with_replacement, permutations

# 定义阶数
global rankLength, canvas, backupDic  # 声明数图阶数，空画布，备选字典

def checkSuccees(hints: list) -> bool:
    """
    # 检验画布是否提示的数字
    :param hints:数字提示 eg:[[1,2],[1,2]]
    :return: 已经完成：True; 未完成：False
    """
    hintsSum = sum(sum(x) for x in hints)
    canvasSum = 0
    for rows in canvas.values.tolist():
        canvasSum += rows.count('T')
    return True if (hintsSum == canvasSum) else False


def checkBackup(hints: list, axial='R', index=0):
    """
    生成备选方案
    1、检查备选字典backupDic里有没有行（列）的相应可行性方案（检查DataFrame长度是否大于0）
    2、没有的话，根据提示数字生成该行的所有可行性方案（保存为DataFrame）
    3、有的话，则从备选字典backupDic中获取可行性方案（DataFrame）
    4、根据目前画布上已填入的信息canvas[行]，从可行性（DataFrame）中筛选掉部分可行性方案
    5、将剩下到可行性方案（DataFrame）更新到备选字典backupDic，下次还要用
    6、对可行性方案（DataFrame）逐列进行遍历，将明确为空或不为空的格子标志“F”或“T”，不明确格子标注为N（表示未确定）
    7、更新画布上对应的行（列）信息
    :param hints:提示数值[1,2]
    :param axial:轴向 R-行；C-列
    :param index:索引
    :return: None
    """
    # 1、检查备选字典backupDic里有没有行（列）的相应可行性方案（检查DataFrame长度是否大于0）
    backup_DF = backupDic[axial + str(index)]
    if not len(backup_DF):
        lis = []  # 二维列表，用于存放所有可能性方案
        # 根据提示数字，创建一个list雏形，用T代表非空白格子、F代表空白格子。
        # list雏形前后有个F，表示可用于插入剩下的空白格子，最后面再删除
        li = ['F']
        for hint in hints:
            li += ["T" for _ in range(hint)] + ["F"]

        falseNum = rankLength - sum(hints) - len(hints) + 1  # 剩下未使用的空白格子数量
        nullPostNum = li.count('F')  # list雏形中可用于继续放置空白格子的位置个数

        # 对剩下空白格子在list雏形中的情况进行排列组合
        # 列出剩下空白格子在排序的所有可能性
        options = [x for x in range(falseNum + 1)]
        # 已知list雏形中可用于继续放置空白格子的位置个数，将各种可能性生成排列组合
        all_combination = combinations_with_replacement(options, nullPostNum)
        # 由于未使用空白格子的总数是固定，因此可再筛选排列组合中，元素和匹配的可选项
        options_combination = [x for x in all_combination if sum(x) == falseNum]

        # 由于前面的组合是有序的，现在重新打乱排序，再去重。
        # 举例，前面可能会生成（0,1）这么一种情况，但不会生成（1，0），现在我们需要再组合排序，将（1,0）这种组合情况一起加进来
        result_combination = []  # 剩下空白格子在list雏形中可能出现方式的排列组合
        for y in options_combination:
            result_combination += list(set([z for z in permutations(y)]))

        # 获取list雏形中，可用于插入空白格子位置的索引
        index_list = [i for i, x in enumerate(li) if x == 'F']  # 获取行li中里面可用于插入空白的位置索引列表
        index_list.reverse()  # 倒序，因为将元素插入list需要从后边开始插入，否则list索引会乱

        # 对前面我们空白格子组成插入方式的排列组合进行遍历，将我们的画布行的可能性方案一一列出来
        for items in result_combination:
            new_li = copy.copy(li)  # 复制行li模板
            num = -1  # 定义索引位置，插入索引得从后面开始
            for false_index in index_list:
                new_li[false_index:false_index] = ['F' for _ in range(items[num])]
                num -= 1
            new_li = new_li[1:-1]  # 去除行li一开始添加的两个空格
            # 至此，行的一种可能性方案产生
            lis.append(new_li)
        print(axial + str(index), '初次生成的可能性方案：', lis)
        backup_DF = DataFrame(lis)  # 生成DataFrame，以便于后面进行数据处理

    # 获取行的可能性方案后，还需要结合当前画布上，已经存在的元素，再排除掉些可能性方案
    if axial == "R":
        datalist = canvas.loc[index, :].values.tolist()
    elif axial == "C":
        datalist = canvas.loc[:, index].values.tolist()

    # 先判断下画布行上是否存在有未确定的格子，有的话才需要更新备选答案字典和画布，没有就直接跳过
    if 'N' in datalist:
        # print('当前', axial + str(index), '画布情况：', datalist)
        # 根据画布的已确定的格子，过滤掉对应可能性方案中冲突的方案
        filterBackup(backup_DF, datalist)
        # 将行的可能性方案更新备选字典backupDic，以便于下次可以直接使用
        backupDic[axial + str(index)] = backup_DF
        # 将可行性方案中，列元素完全相同的格子确定下来，更新回画布上
        updateCanvas(axial=axial, index=index)


def filterBackup(df: DataFrame, li: list):
    """
    根据画布的行和列，过滤掉备选方案中冲突的可能项
    :param df: 备选方案
    :param li: 画布行（列）
    :return:
    """
    for index_canvas, item in enumerate(li):
        # 如果画布行中的元素明确是T或F，则对DataFrame进行过滤
        if all([(item in ['T', 'F']), (len(df) != len(df[df[index_canvas] == item]))]):
            # print('画布元素索引：', index_canvas, '确定的元素值：', item, '备选方案删除前：\n', df)
            df.drop(df[(df[index_canvas] != item)].index, inplace=True)
            # print('画布元素索引：', index_canvas, '确定的元素值：', item, '备选方案删除后：\n', df)


def updateCanvas(axial: str, index: int):
    """
    更新画布信息
    1、先从备选字典backupDic中提取所有可能性方案DataFrame
    2、对画布行上的每个元素进行遍历，如果有尚不确定的格子（N）,这根据格子的坐标，查找可行性方案中对应的列
    3、假如可行性行方案对于的列，所有元素一致，那么久可以确定画布行上的格子属性
    :param axial:轴向
    :param index: 索引
    :return: None
    """
    backup_DF = backupDic[axial + str(index)]
    # 获取画布行
    if axial == 'R':
        datalist = canvas.loc[index, :].values.tolist()
    elif axial == 'C':
        datalist = canvas.loc[:, index].values.tolist()

    # 对每个元素进行遍历，
    for index_item, item in enumerate(datalist):
        # 如果元素为N（表示不确定），则在可能性方案中，检索对应列的看看能否确定格子，如果可以，则更新画布
        if item == "N":  # 画布上某格子不确定
            # 获取该格子的所有可行性方案list
            backup_list = backup_DF[index_item].values.tolist()
            # 如果全部元素一致，说明能确定格子的属性
            if backup_list.count(backup_list[0]) == len(backup_list):
                # 更新画布格子
                if axial == 'R':
                    canvas.loc[index, index_item] = backup_list[0]
                elif axial == 'C':
                    canvas.loc[index_item, index] = backup_list[0]


if __name__ == "__main__":
    rankLength = 16  # 声明数图阶数
    rowsHint = [[3, 2, 2, 1],
                [2, 1, 1, 1],
                [1, 3, 3, 1, 1],
                [2, 4, 4],
                [2, 1, 1, 2, 1, 1],
                [4, 1, 2, 1],
                [5, 3, 3],
                [2, 4, 2],
                [1, 3, 1, 3],
                [1, 2, 3, 2, 1],
                [3, 1, 7, 1],
                [1, 1, 1, 1, 1, 2],
                [1, 2, 1, 3, 1],
                [2, 4, 1],
                [1, 4, 2, 2, 2],
                [1, 7, 2, 3]]  # 行提示
    colsHint = [[1,2,1,3,2],
                [2,5,1,1],
                [2,4,3,2],
                [1,2,2,3],
                [2,3,1,4],
                [2,2,2,2],
                [2,2,4,1],
                [1,1,6,1,2],
                [3,2,3,2],
                [1,3,1,1,2],
                [1,1,1,6],
                [1,2,4],
                [2,5,1],
                [2,3,2,2],
                [1,2,2,3,2],
                [1,2,1,1,1]]  # 列提示

    # 初始化画布和备选字典backupDic
    canvas = DataFrame([["N" for _ in range(rankLength)] for _ in range(rankLength)])
    # 生成备选字典，每个行、列都有一个备选字典，
    backupDic = {('R' + str(row)): DataFrame() for row in range(rankLength)}
    backupDic.update({('C' + str(col)): DataFrame() for col in range(rankLength)})

    # 给每个行和列生成备选字典backupDic，根据画布上已有的信息和备选字典backupDic推断出格子的属性
    for j in range(20):
        for index, hints in enumerate(rowsHint):
            checkBackup(hints=hints, axial="R", index=index)
        for index, hints in enumerate(colsHint):
            checkBackup(hints=hints, axial="C", index=index)
        print('\n第', j + 1, '次循环生成的画布答案：\n', canvas)
        if checkSuccees(rowsHint):  # 判断画布是否已经完成填写，是的话退出死循环
            break

    # 为方便美观，下面进行处理再输出
    print('\n最终答案如下：')
    for i in range(rankLength + 1):
        print(i, end='\t')
    print('')
    for index, i in enumerate(canvas.values.tolist()):
        print(index + 1, end='\t')
        for j in i:
            if j == 'T':
                value = '⏹'
            elif j == 'F':
                value = 'X'
            else:
                value = ' '
            print(value, end='\t')
        print('')

---

程序运行说明：

程序运行需要输入下面三个参数
rankLength = 16 # 声明数图阶数，即该模式的行（或列）有多少个格子
rowsHint = [] # 行的提示数字，二维列表
colsHint = [] # 列的提示数字，二维列表

---

程序运行结果：

程序运行结果

• 16阶的难度，程序运行时长2秒不到，其他阶的我没测试过时间，但依旧也可以正常运行。
• 程序运行结果如果提示索引越界，那十有八九是参数输错了，再重新检查下

---

后言：

1. 程序大家看看就得了，我这里只是提供一种实现思路，并不是提倡大家破解游戏后再完，那就没意思了。
2. 程序运行需要手动录入提示数字，这里有点浪费时间。
3. 我手机屏幕小，点格子时经常点错位子没发现，于是一步错步步错，后面就崩了重玩，气死我了。
4. 玩游戏讲究的是过程，而不是结果。