-
-
[原创]KCTF2021春季赛第四题 英雄救美
-
发表于: 2021-5-15 11:41
-
程序无壳，ida打开，流程很清晰
反推，先解数独，再转格式
0 4 0 7 0 0 0 0 0
9 2 0 0 0 0 6 0 7
8 3 0 0 0 5 4 0 0
0 1 0 0 0 3 0 0 0
0 0 0 2 0 1 0 0 0
0 0 0 5 0 0 0 4 0
0 0 4 9 0 0 0 7 1
3 0 5 0 0 0 0 9 4
0 0 0 0 0 8 0 6 0
5 4 6 7 1 9 2 3 8
9 2 1 8 3 4 6 5 7
8 3 7 6 2 5 4 1 9
7 1 8 4 6 3 9 2 5
4 5 3 2 9 1 7 8 6
6 9 2 5 8 7 1 4 3
2 8 4 9 5 6 3 7 1
3 6 5 1 7 2 8 9 4
1 7 9 3 4 8 5 6 2
use Time: 0.031022 s
#sudoku: [0, 4, 0, 7, 0, 0, 0, 0, 0, 9, 2, 0, 0, 0, 0, 6, 0, 7, 8, 3, 0, 0, 0, 5, 4, 0, 0, 0, 1, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 4, 0, 0, 0, 4, 9, 0, 0, 0, 7, 1, 3, 0, 5, 0, 0, 0, 0, 9, 4, 0, 0, 0, 0, 0, 8, 0, 6, 0]
#result: [5, 4, 6, 7, 1, 9, 2, 3, 8, 9, 2, 1, 8, 3, 4, 6, 5, 7, 8, 3, 7, 6, 2, 5, 4, 1, 9, 7, 1, 8, 4, 6, 3, 9, 2, 5, 4, 5, 3, 2, 9, 1, 7, 8, 6, 6, 9, 2, 5, 8, 7, 1, 4, 3, 2, 8, 4, 9, 5, 6, 3, 7, 1, 3, 6, 5, 1, 7, 2, 8, 9, 4, 1, 7, 9, 3, 4, 8, 5, 6, 2]
[5, 6, 1, 9, 2, 3, 8, 1, 8, 3, 4, 5, 7, 6, 2, 1, 9, 7, 8, 4, 6, 9, 2, 5, 4, 5, 3, 9, 7, 8, 6, 6, 9, 2, 8, 7, 1, 3, 2, 8, 5, 6, 3, 6, 1, 7, 2, 8, 1, 7, 9, 3, 4, 5, 2]
[5, 6, 1, 9, 2, 3, 8, 1, 8, 3, 4, 5, 7, 6, 2, 1, 9, 7, 8, 4, 6, 9, 2, 5, 4, 5, 3, 9, 7, 8, 6, 6, 9, 2, 8, 7, 1, 3, 2, 8, 5, 6, 3, 6, 1, 7, 2, 8, 1, 7, 9, 3, 4, 5, 2]
checkov flag:
:u$YBPf2pa]Dt4#QM^H4ic'j0`w2y{d-Zzo2%/n_s@+2<UW)e4AR;F.4=-qEkvC2
import time
t0 = time.time()
class point:
def __init__(self, x, y):
self.x = x
self.y = y
self.available = []
self.value = 0
def rowNum(p, sudoku):
row = set(sudoku[p.y * 9:(p.y + 1) * 9])
row.remove(0)
return row # set type
def colNum(p, sudoku):
col = []
length = len(sudoku)
for i in range(p.x, length, 9):
col.append(sudoku[i])
col = set(col)
col.remove(0)
return col # set type
def blockNum(p, sudoku):
block_x = p.x // 3
block_y = p.y // 3
block = []
start = block_y * 3 * 9 + block_x * 3
for i in range(start, start + 3):
block.append(sudoku[i])
for i in range(start + 9, start + 9 + 3):
block.append(sudoku[i])
for i in range(start + 9 + 9, start + 9 + 9 + 3):
block.append(sudoku[i])
block = set(block)
block.remove(0)
return block # set type
def initPoint(sudoku):
pointList = []
length = len(sudoku)
for i in range(length):
if sudoku[i] == 0:
p = point(i % 9, i // 9)
for j in range(1, 10):
if j not in rowNum(p, sudoku) and j not in colNum(p, sudoku) and j not in blockNum(p, sudoku):
p.available.append(j)
pointList.append(p)
return pointList
ret = None
def tryInsert(p, sudoku):
global ret
availNum = p.available
for v in availNum:
p.value = v
if check(p, sudoku):
sudoku[p.y * 9 + p.x] = p.value
if len(pointList) <= 0:
t1 = time.time()
useTime = t1 - t0
ret = showSudoku(sudoku)
print('\nuse Time: %f s' % (useTime))
# print(ret)
return
# exit()
p2 = pointList.pop()
tryInsert(p2, sudoku)
sudoku[p2.y * 9 + p2.x] = 0
sudoku[p.y * 9 + p.x] = 0
p2.value = 0
pointList.append(p2)
else:
pass
def check(p, sudoku):
if p.value == 0:
print('not assign value to point p!!')
return False
if p.value not in rowNum(p, sudoku) and p.value not in colNum(p, sudoku) and p.value not in blockNum(p, sudoku):
return True
else:
return False
def showSudoku(sudoku):
result = []
for j in range(9):
for i in range(9):
result.append(sudoku[j * 9 + i])
print('%d ' % (sudoku[j * 9 + i]), end='')
print('')
return result
v13 = r"$BPV:ubfYp}]DtN>aT^MGmJQ#*Hr`O'wjic0!hdy{oZz-@n+?&%s_/g<e[W)XUxRFSLRA;.l=CEkvK-(q"
# def checkformat(myinput=r":u$YBPf2pa]Dt4#QM^H4ic'j0`w2y{d-Zzo2%/n_s@+2<UW)e4AR;F.4=-qEkvC2"):def checkformat(myinput):
a3 = []
i = 0
j = 0
k = 0
strlens = len(myinput)
while 1:
tmpchr = myinput[j]
if ord(tmpchr) > ord('0') and ord(tmpchr) <= ord('9'):
# break
if i + ord(tmpchr) == ord('9'):
i = 0
k += 9
j += 1
if j >= strlens:
printf(a3)
return 1
continue
m = k
if (k >= 81):
return 0
while ord(tmpchr) != ord(v13[m]):
m += 1
if (m >= 81):
return 0
v9 = m % 9 + 1
a3.append(v9)
i += 1
j += 1
# if j >= strlens:
# print('##',a3)
# return 1
return -1
DEBUG = True
def printf(*args):
if DEBUG:
print(*args)
if __name__ == '__main__':
sudoku = [
0, 4, 0, 7, 0, 0, 0, 0, 0,
9, 2, 0, 0, 0, 0, 6, 0, 7,
8, 3, 0, 0, 0, 5, 4, 0, 0,
0, 1, 0, 0, 0, 3, 0, 0, 0,
0, 0, 0, 2, 0, 1, 0, 0, 0,
0, 0, 0, 5, 0, 0, 0, 4, 0,
0, 0, 4, 9, 0, 0, 0, 7, 1,
3, 0, 5, 0, 0, 0, 0, 9, 4,
0, 0, 0, 0, 0, 8, 0, 6, 0
]
pointList = initPoint(sudoku)
showSudoku(sudoku)
print('\n')
p = pointList.pop()
tryInsert(p, sudoku)
result = ret
# result="""5 4 6 7 1 9 2 3 8
# 9 2 1 8 3 4 6 5 7
# 8 3 7 6 2 5 4 1 9
# 7 1 8 4 6 3 9 2 5
# 4 5 3 2 9 1 7 8 6
# 6 9 2 5 8 7 1 4 3
# 2 8 4 9 5 6 3 7 1
# 3 6 5 1 7 2 8 9 4
# 1 7 9 3 4 8 5 6 2 """.split()
# result = list(map(int, result))
strdata = v13
printf('#sudoku:', sudoku)
printf('#result:', result)
n = 0
need = []
my = ''
currentsize = 0
for i in range(81):
if sudoku[i] != result[i]:
currentsize += 1
need.append(result[i])
my += strdata[n * 9 + result[i] - 1]
if (i + 1) % 9 == 0:
my += chr(ord('9') - currentsize)
currentsize = 0
n += 1
printf(need)
r = checkformat(my)
if r:
print('checkov flag:\n', my, sep='')
# from hashlib import md5
# x=md5(my.encode()).hexdigest()
# print(x)
# print('########################')
import time
t0 = time.time()
class point:
def __init__(self, x, y):
self.x = x
self.y = y
self.available = []
self.value = 0
def rowNum(p, sudoku):
row = set(sudoku[p.y * 9:(p.y + 1) * 9])
row.remove(0)
return row # set type
def colNum(p, sudoku):
col = []
length = len(sudoku)
for i in range(p.x, length, 9):
col.append(sudoku[i])
col = set(col)
col.remove(0)
return col # set type
def blockNum(p, sudoku):
block_x = p.x // 3
block_y = p.y // 3
block = []
start = block_y * 3 * 9 + block_x * 3
for i in range(start, start + 3):
block.append(sudoku[i])
for i in range(start + 9, start + 9 + 3):
block.append(sudoku[i])
for i in range(start + 9 + 9, start + 9 + 9 + 3):
block.append(sudoku[i])
block = set(block)
block.remove(0)
return block # set type
def initPoint(sudoku):
pointList = []
length = len(sudoku)
for i in range(length):
if sudoku[i] == 0:
p = point(i % 9, i // 9)
for j in range(1, 10):
if j not in rowNum(p, sudoku) and j not in colNum(p, sudoku) and j not in blockNum(p, sudoku):
p.available.append(j)
pointList.append(p)
return pointList
ret = None
def tryInsert(p, sudoku):
global ret
availNum = p.available
for v in availNum:
p.value = v
if check(p, sudoku):
sudoku[p.y * 9 + p.x] = p.value
if len(pointList) <= 0:
t1 = time.time()
useTime = t1 - t0
ret = showSudoku(sudoku)
print('\nuse Time: %f s' % (useTime))
# print(ret)
return
# exit()
p2 = pointList.pop()
tryInsert(p2, sudoku)
sudoku[p2.y * 9 + p2.x] = 0
sudoku[p.y * 9 + p.x] = 0
p2.value = 0
pointList.append(p2)
else:
pass
def check(p, sudoku):
if p.value == 0:
print('not assign value to point p!!')
return False
if p.value not in rowNum(p, sudoku) and p.value not in colNum(p, sudoku) and p.value not in blockNum(p, sudoku):
return True
else:
return False
def showSudoku(sudoku):
result = []
for j in range(9):
for i in range(9):
result.append(sudoku[j * 9 + i])
print('%d ' % (sudoku[j * 9 + i]), end='')
[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！
