1. intro：巔峰極客的一道逆向
刷巔峰極客2020里的rev題fu!kpy正蛙，復(fù)雜得不行但是看到if d[1][0] != '8' or d[1][7] != '2'和if check(h1) != 45 or check(h2) != 45 or check(h9) != 45這種內(nèi)容，結(jié)合flag相關(guān)的部分可以確認(rèn)是flag{9*9}的數(shù)獨(dú)贩猎。
# 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畫(huà)出格子苞尝，然后發(fā)現(xiàn)這道題太難了我不會(huì)做。這個(gè)時(shí)候需要搜一下……
[[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. 知識(shí)點(diǎn)引入：backtracking
回溯算法（backtracking）是暴力搜索算法的一種。正是由于回溯算法具有“強(qiáng)大的”暴力搜索的能力共螺，它被應(yīng)用于一些游戲問(wèn)題，例如：N 皇后情竹、解數(shù)獨(dú)藐不、祖瑪游戲、24 點(diǎn)游戲秦效、走迷宮雏蛮、生成迷宮。許多復(fù)雜的阱州、規(guī)模較大的問(wèn)題都可以使用回溯搜索算法得到所有可行解挑秉，進(jìn)而得到最優(yōu)解，因此回溯算法有“通用解題方法”的美稱苔货，回溯算法也是經(jīng)典的人工智能的基礎(chǔ)算法衷模。
由于回溯算法的時(shí)間復(fù)雜度很高，因此蒲赂，在遍歷的時(shí)候阱冶，如果能夠提前知道這一條分支不能搜索到滿意的結(jié)果，這一分支就可以跳過(guò)滥嘴，這一步操作就是在一棵樹(shù)上剪去一個(gè)枝葉木蹬，被人們很形象地稱之為剪枝。
結(jié)論，backtracking可以較好地解數(shù)獨(dú)題镊叁。(喂）
2.1. 算法入門(mén)-全排列
「力扣」上第 46 號(hào)問(wèn)題：“全排列”尘颓。
題目描述：給定一個(gè)沒(méi)有重復(fù)數(shù)字的序列，返回其所有可能的全排列晦譬。
在一個(gè)樹(shù)形問(wèn)題上做一次深度優(yōu)先遍歷疤苹。為了理解回溯的過(guò)程畫(huà)個(gè)流程圖如下。
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滿足時(shí)遞歸終止
if depth == size:
res.append(path)
return
for i in range(size):
#print(i,bin(state),path,res)
#state判斷第i位的元素是否已經(jīng)使用過(guò)卧土，位運(yùn)算優(yōu)化
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. 解數(shù)獨(dú)
樂(lè)扣37題，解數(shù)獨(dú)像樊∮容海空白格用 '.' 表示。
數(shù)獨(dú)的規(guī)則：
- 數(shù)字 1-9 在每一行只能出現(xiàn)一次生棍。
- 數(shù)字 1-9 在每一列只能出現(xiàn)一次颤霎。
- 數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。
和原py題一樣按照「行優(yōu)先」的順序依次枚舉每一個(gè)空白格中填的數(shù)字涂滴，通過(guò)遞歸 + 回溯的方法枚舉所有可能的填法友酱。
- 初始化state[row,line,palace]，表明哪些數(shù)字已經(jīng)被使用過(guò)了柔纵。
- 嘗試去填充數(shù)組缔杉。如果行、列首量、 或 3*3 的方格內(nèi)出現(xiàn)已經(jīng)被使用過(guò)的數(shù)字則不填充壮吩，否則嘗試填充进苍。
- 填充失敗則回溯加缘。
- 深度滿足則遞歸結(jié)束。
為了理解流程觉啊，先來(lái)個(gè)3*3的數(shù)獨(dú)拣宏。沒(méi)有小框框
[[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
沒(méi)時(shí)間了抄了份別人的哈希表解法杠人，好清晰啊勋乾。以后有空再優(yōu)化成位運(yùn)算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 = [] # 存儲(chǔ)待填格的位置
# 初始化，按照行嗡善、列辑莫、宮 分別存入哈希表
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] # 剩余的數(shù)字
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. 來(lái)到ctf數(shù)獨(dú)題
其實(shí)已經(jīng)出來(lái)了。罩引。只要補(bǔ)一下生成
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 = [] # 存儲(chǔ)待填格的位置
# 初始化各吨，按照行、列袁铐、宮 分別存入哈希表
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] # 剩余的數(shù)字
if not rst: # 無(wú)解的情況
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. 總結(jié)
- 機(jī)器學(xué)習(xí)趕緊接著學(xué)敖已选横浑！
- 繼續(xù)學(xué)A* 算法解迷宮題啊屉更！手動(dòng)解迷宮你也好意思徙融？（）
- 現(xiàn)在安全競(jìng)賽是不是越來(lái)越往算法大賽轉(zhuǎn)了。瑰谜。欺冀。落后專業(yè)人才轉(zhuǎn)型迫在眉睫。
