1. intro：巅峰极客的一道逆向
刷巅峰极客2020里的rev题fu!kpy，复杂得不行但是看到if d[1][0] != '8' or d[1][7] != '2'和if check(h1) != 45 or check(h2) != 45 or check(h9) != 45这种内容，结合flag相关的部分可以确认是flag{9*9}的数独。
# uncompyle6 version 2.11.5
# Python bytecode 2.7 (62211)
# Decompiled from: Python 2.7.16 (default, Apr 6 2019, 01:42:57)
# [GCC 8.3.0]
# Embedded file name: test233_ol.py
# Compiled at: 2020-03-20 13:22:50
(lambda __g, __print: [ [ (lambda __after: if __name__ == '__main__':
[ (lambda __after: if len(input) != 87:
(__print('Error len!'), (exit(), __after())[1])[1]__after())(lambda : [ [ [ [ (lambda __after: if fmt1 != 'flag{' or fmt2 != '}':
(__print('Error fmt!'), (exit(0), __after())[1])[1]__after())(lambda : (
d.append(context[0:9]), (d.append(context[9:18]), (d.append(context[18:27]), (d.append(context[27:36]), (d.append(context[36:45]), (d.append(context[45:54]), (d.append(context[54:63]), (d.append(context[63:72]), (d.append(context[72:81]), [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ (lambda __after: if d[0][2] != '5' or d[0][3] != '3':
(__print('Error!'), (exit(), __after())[1])[1]__after())(lambda : (lambda __after: if d[1][0] != '8' or d[1][7] != '2':
(__print('Error!'), (exit(), __after())[1])[1]__after())(lambda : (lambda __after: if d[2][1] != '7' or d[2][4] != '1' or d[2][6] != '5':
(__print('Error!'), (exit(), __after())[1])[1]__after())(lambda : (lambda __after: if d[3][0] != '4' or d[3][5] != '5' or d[3][6] != '3':
(__print('Error!'), (exit(), __after())[1])[1]__after())(lambda : (lambda __after: if d[4][1] != '1' or d[4][4] != '7' or d[4][8] != '6':
(__print('Error!'), (exit(), __after())[1])[1]__after())(lambda : (lambda __after: if d[5][2] != '3' or d[5][3] != '2' or d[5][7] != '8':
(__print('Error!'), (exit(), __after())[1])[1]__after())(lambda : (lambda __after: if d[6][1] != '6' or d[6][3] != '5' or d[6][8] != '9':
(__print('Error!'), (exit(), __after())[1])[1]__after())(lambda : (lambda __after: if d[7][2] != '4' or d[7][7] != '3':
(__print('Error!'), (exit(), __after())[1])[1]__after())(lambda : (lambda __after: if d[8][5] != '9' or d[8][6] != '7':
(__print('Error!'), (exit(), __after())[1])[1]__after())(lambda : (lambda __after: if check(h1) != 45 or check(h2) != 45 or check(h3) != 45 or check(h4) != 45 or check(h5) != 45 or check(h6) != 45 or check(h7) != 45 or check(h8) != 45 or check(h9) != 45:
(__print('Error!'), (exit(), __after())[1])[1]__after())(lambda : (lambda __after: if check(l1) != 45 or check(l2) != 45 or check(l3) != 45 or check(l4) != 45 or check(l5) != 45 or check(l6) != 45 or check(l7) != 45 or check(l8) != 45 or check(l9) != 45:
(__print('Error!'), (exit(), __after())[1])[1]__after())(lambda : (lambda __after: if check(k1) != 45 or check(k2) != 45 or check(k3) != 45 or check(k4) != 45 or check(k5) != 45 or check(k6) != 45 or check(k7) != 45 or check(k8) != 45 or check(k9) != 45:
(__print('Error!'), (exit(), __after())[1])[1]__after())(lambda : (lambda __after: if check1(h1) != 1 or check1(h2) != 1 or check1(h3) != 1 or check1(h4) != 1 or check1(h5) != 1 or check1(h6) != 1 or check1(h7) != 1 or check1(h8) != 1 or check1(h9) != 1:
(__print('Error!'), (exit(), __after())[1])[1]__after())(lambda : (lambda __after: if check1(l1) != 1 or check1(l2) != 1 or check1(l3) != 1 or check1(l4) != 1 or check1(l5) != 1 or check1(l6) != 1 or check1(l7) != 1 or check1(l8) != 1 or check1(l9) != 1:
(__print('Error!'), (exit(), __after())[1])[1]__after())(lambda : (lambda __after: if check1(k1) != 1 or check1(k2) != 1 or check1(k3) != 1 or check1(k4) != 1 or check1(k5) != 1 or check1(k6) != 1 or check1(k7) != 1 or check1(k8) != 1 or check1(k9) != 1:
(__print('Error!'), (exit(), __after())[1])[1]__after())(lambda : (
__print('Yes! You got it!'), __after())[1]))))))))))))))) for __g['k9'] in [context[60] + context[61] + context[62] + context[69] + context[70] + context[71] + context[78] + context[79] + context[80]] ][0] for __g['k8'] in [context[57] + context[58] + context[59] + context[66] + context[67] + context[68] + context[75] + context[76] + context[77]] ][0] for __g['k7'] in [context[54] + context[55] + context[56] + context[63] + context[64] + context[65] + context[72] + context[73] + context[74]] ][0] for __g['k6'] in [context[33] + context[34] + context[35] + context[42] + context[43] + context[44] + context[51] + context[52] + context[53]] ][0] for __g['k5'] in [context[30] + context[31] + context[32] + context[39] + context[40] + context[41] + context[48] + context[49] + context[50]] ][0] for __g['k4'] in [context[27] + context[28] + context[29] + context[36] + context[37] + context[38] + context[45] + context[46] + context[47]] ][0] for __g['k3'] in [context[6] + context[7] + context[8] + context[15] + context[16] + context[17] + context[24] + context[25] + context[26]] ][0] for __g['k2'] in [context[3] + context[4] + context[5] + context[12] + context[13] + context[14] + context[21] + context[22] + context[23]] ][0] for __g['k1'] in [context[0] + context[1] + context[2] + context[9] + context[10] + context[11] + context[18] + context[19] + context[20]] ][0] for __g['l9'] in [context[8] + context[17] + context[26] + context[35] + context[44] + context[53] + context[62] + context[71] + context[80]] ][0] for __g['l8'] in [context[7] + context[16] + context[25] + context[34] + context[43] + context[52] + context[61] + context[70] + context[79]] ][0] for __g['l7'] in [context[6] + context[15] + context[24] + context[33] + context[42] + context[51] + context[60] + context[69] + context[78]] ][0] for __g['l6'] in [context[5] + context[14] + context[23] + context[32] + context[41] + context[50] + context[59] + context[68] + context[77]] ][0] for __g['l5'] in [context[4] + context[13] + context[22] + context[31] + context[40] + context[49] + context[58] + context[67] + context[76]] ][0] for __g['l4'] in [context[3] + context[12] + context[21] + context[30] + context[39] + context[48] + context[57] + context[66] + context[75]] ][0] for __g['l3'] in [context[2] + context[11] + context[20] + context[29] + context[38] + context[47] + context[56] + context[65] + context[74]] ][0] for __g['l2'] in [context[1] + context[10] + context[19] + context[28] + context[37] + context[46] + context[55] + context[64] + context[73]] ][0] for __g['l1'] in [context[0] + context[9] + context[18] + context[27] + context[36] + context[45] + context[54] + context[63] + context[72]] ][0] for __g['h9'] in [context[72:81]] ][0] for __g['h8'] in [context[63:72]] ][0] for __g['h7'] in [context[54:63]] ][0] for __g['h6'] in [context[45:54]] ][0] for __g['h5'] in [context[36:45]] ][0] for __g['h4'] in [context[27:36]] ][0] for __g['h3'] in [context[18:27]] ][0] for __g['h2'] in [context[9:18]] ][0] for __g['h1'] in [context[0:9]] ][0])[1])[1])[1])[1])[1])[1])[1])[1])[1])
for __g['d'] in [[]] ][0]
for __g['context'] in [input[5:-1]] ][0]
for __g['fmt2'] in [input[-1]] ][0]
for __g['fmt1'] in [input[0:5]] ][0])
for __g['input'] in [raw_input('Input your flag:')] ][0]__after())(lambda : None) for __g['check1'], check1.__name__ in [(lambda arg: (lambda __l: [ (lambda __after: if len(list(set(__l['arg']))) != 9:
01)(lambda : None) for __l['arg'] in [arg] ][0])({}), 'check1')] ][0] for __g['check'], check.__name__ in [(lambda arg: (lambda __l: [ sum(map(int, __l['arg'])) for __l['arg'] in [arg] ][0])({}), 'check')] ][0])(globals(), __import__('__builtin__', level=0).__dict__['print'])
熟练的用numpy画出格子，然后发现这道题太难了我不会做。这个时候需要搜一下……
[[0. 0. 5. 3. 0. 0. 0. 0. 0.]
[8. 0. 0. 0. 0. 0. 0. 2. 0.]
[0. 7. 0. 0. 1. 0. 5. 0. 0.]
[4. 0. 0. 0. 0. 5. 3. 0. 0.]
[0. 1. 0. 0. 7. 0. 0. 0. 6.]
[0. 0. 3. 2. 0. 0. 0. 8. 0.]
[0. 6. 0. 5. 0. 0. 0. 0. 9.]
[0. 0. 4. 0. 0. 0. 0. 3. 0.]
[0. 0. 0. 0. 0. 9. 7. 0. 0.]]
2. 知识点引入：backtracking
回溯算法（backtracking）是暴力搜索算法的一种。正是由于回溯算法具有“强大的”暴力搜索的能力，它被应用于一些游戏问题，例如：N 皇后、解数独、祖玛游戏、24 点游戏、走迷宫、生成迷宫。许多复杂的、规模较大的问题都可以使用回溯搜索算法得到所有可行解，进而得到最优解，因此回溯算法有“通用解题方法”的美称，回溯算法也是经典的人工智能的基础算法。
由于回溯算法的时间复杂度很高，因此，在遍历的时候，如果能够提前知道这一条分支不能搜索到满意的结果，这一分支就可以跳过，这一步操作就是在一棵树上剪去一个枝叶，被人们很形象地称之为剪枝。
结论，backtracking可以较好地解数独题。(喂）
2.1. 算法入门-全排列
「力扣」上第 46 号问题：“全排列”。
题目描述：给定一个没有重复数字的序列，返回其所有可能的全排列。
在一个树形问题上做一次深度优先遍历。为了理解回溯的过程画个流程图如下。
graph TB;
0--1:depth+=1,state=0b001-->A(1)
A--2:depth+=1,state=0b011-->B("[1,2]")
B--3:depth+=1,state=0b111-->C("[1,2,3]")
C--4:depth-=1,state=0b011-->B
B--5:-depth-=1,state=0b001-->A
A--6:depth+=1,state=0b101-->D("[1,3]")
D--7:depth+=1,state=0b111-->E("[1,3,2]")
E--8:depth-=1,state=0b101-->D
D--9:depth-=1,state=0b001-->A
0(start)
image.png
抄的py3代码如下（）。
def permute(nums):
def dfs(nums, size, depth, path, state, res):
# depth满足时递归终止
if depth == size:
res.append(path)
return
for i in range(size):
#print(i,bin(state),path,res)
#state判断第i位的元素是否已经使用过，位运算优化
if ((state >> i) & 1) == 0:
dfs(nums, size, depth + 1, path + [nums[i]], state ^ (1 << i), res)
size = len(nums)
if size == 0:
return []
res = []
dfs(nums, size, 0, [], 0, res)
return res
permute([1,2,3])
2.2. 解数独
乐扣37题，解数独。空白格用 '.' 表示。
数独的规则：
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
和原py题一样按照「行优先」的顺序依次枚举每一个空白格中填的数字，通过递归 + 回溯的方法枚举所有可能的填法。
- 初始化state[row,line,palace]，表明哪些数字已经被使用过了。
- 尝试去填充数组。如果行、列、 或 3*3 的方格内出现已经被使用过的数字则不填充，否则尝试填充。
- 填充失败则回溯。
- 深度满足则递归结束。
为了理解流程，先来个3*3的数独。没有小框框
[[1. 2. 0.]
[2. 0. 1.]
[0. 0. 0.]]
流程图如下。
graph TB;
0--"1:depth+=1,state=[111,011,000,011,010,101]"-->A("[1,2,3],[2,0,1],[0,0,0]")
A--"2:depth+=1,state=[111,111,000,011,110,101]"-->B("[1,2,3],[2,3,1],[0,0,0]")
B--"3:depth+=1,state=[111,111,100,111,110,101]"-->C("[1,2,3],[2,3,1],[3,0,0]")
C--"4:depth+=1,state=[111,111,101,111,111,101]"-->D("[1,2,3],[2,3,1],[3,1,0]")
D--"5:depth+=1,state=[111,111,111,111,111,111]"-->e("[1,2,3],[2,3,1],[3,1,2]")
0("start,depth=4,state=[011,011,000,011,010,001]")
image.png
没时间了抄了份别人的哈希表解法，好清晰啊。以后有空再优化成位运算0.0
def solveSudoku(board):
nums = {"1", "2", "3", "4", "5", "6", "7", "8", "9"}
row = [set() for _ in range(9)]
col = [set() for _ in range(9)]
palace = [[set() for _ in range(3)] for _ in range(3)] # 3*3
blank = [] # 存储待填格的位置
# 初始化，按照行、列、宫 分别存入哈希表
for i in range(9):
for j in range(9):
ch = board[i][j]
if ch == '0':
#if ch == ".":
blank.append((i, j))
else:
row[i].add(ch)
col[j].add(ch)
palace[i // 3][j // 3].add(ch)
def dfs(n):
if n == len(blank):
return True
i, j = blank[n]
rst = nums - row[i] - col[j] - palace[i // 3][j // 3] # 剩余的数字
if not rst:
return False
for num in rst:
board[i][j] = num
row[i].add(num)
col[j].add(num)
palace[i // 3][j // 3].add(num)
if dfs(n + 1):
return True
row[i].remove(num)
col[j].remove(num)
palace[i // 3][j // 3].remove(num)
dfs(0)
board=[['0','0','5','3','0','0','0','0','0']
,['8','0','0','0','0','0','0','2','0']
,['0','7','0','0','1','0','5','0','0']
,['4','0','0','0','0','5','3','0','0']
,['0','1','0','0','7','0','0','0','6']
,['0','0','3','2','0','0','0','8','0']
,['0','6','0','5','0','0','0','0','9']
,['0','0','4','0','0','0','0','3','0']
,['0','0','0','0','0','9','7','0','0']]
solveSudoku(board)
from pprint import pprint
pprint(board)
2.3. 来到ctf数独题
其实已经出来了。。只要补一下生成
def solveSudoku(board):
nums = {"1", "2", "3", "4", "5", "6", "7", "8", "9"} #用set保证唯一
row = [set() for _ in range(9)]
col = [set() for _ in range(9)]
palace = [[set() for _ in range(3)] for _ in range(3)] # 3*3
blank = [] # 存储待填格的位置
# 初始化，按照行、列、宫 分别存入哈希表
for i in range(9):
for j in range(9):
ch = board[i][j]
if ch == '0':
blank.append((i, j))
else:
row[i].add(ch)
col[j].add(ch)
palace[i // 3][j // 3].add(ch)
def dfs(n):
if n == len(blank): # 填满
return True
i, j = blank[n]
rst = nums - row[i] - col[j] - palace[i // 3][j // 3] # 剩余的数字
if not rst: # 无解的情况
return False
for num in rst:
board[i][j] = num
row[i].add(num)
col[j].add(num)
palace[i // 3][j // 3].add(num)
if dfs(n + 1):
return True
row[i].remove(num)
col[j].remove(num)
palace[i // 3][j // 3].remove(num)
dfs(0)
import numpy as np
d = np.zeros(81).reshape(9, 9)
d[0][2] = '5'
d[0][3] = '3'
d[1][0] = '8'
d[1][7] = '2'
d[2][1] = '7'
d[2][4] = '1'
d[2][6] = '5'
d[3][0] = '4'
d[3][5] = '5'
d[3][6] = '3'
d[4][1] = '1'
d[4][4] = '7'
d[4][8] = '6'
d[5][2] = '3'
d[5][3] = '2'
d[5][7] = '8'
d[6][1] = '6'
d[6][3] = '5'
d[6][8] = '9'
d[7][2] = '4'
d[7][7] = '3'
d[8][5] = '9'
d[8][6] = '7'
board = d
board= np.asarray(board,dtype=np.int16)
board = np.asarray(board,dtype=np.unicode_)
solveSudoku(board)
for i in board:
print(''.join(i),end='')
flag{145327698839654127672918543496185372218473956753296481367542819984761235521839764}
3. 总结
- 机器学习赶紧接着学啊！
- 继续学A* 算法解迷宫题啊！手动解迷宫你也好意思？（）
- 现在安全竞赛是不是越来越往算法大赛转了。。。落后专业人才转型迫在眉睫。
