SECCON 2013 CTF Online Quals に参加しました
参加しました
SECCON 2013 CTF オンライン予選にチームで参加しました。
私は結局のところ、『数「毒」ちゃれんじ★』のみの解答でした。 もはや CTF をやっているか怪しいレベルなので、精進したいと思います。 そのうち。
『数「毒」ちゃれんじ★』の Writeup
各ステージで数独の問題が与えられます。 X の部分だけ可変でその値が問題ごとに与えられますが、特にひねりもないので、やるだけです。方針としては、数独のルールに則って確実に埋めていったあと、まだ埋まっていないマスがあればバックトラック法で無理やり埋める方法でいきました。
コード (Python 3)
変に長いので、ご注意ください。
#!/usr/bin/env python3
import copy
import re
import telnetlib
import time
def generate_xy():
return ((i%9, i//9) for i in range(81))
class Square(object):
def __init__(self):
self.boolcube = [[[True for n in range(9)]
for y in range(9)]
for x in range(9)]
self.numbers = [[None for y in range(9)] for x in range(9)]
def copy(self):
copied = self.__class__()
copied.boolcube = copy.deepcopy(self.boolcube)
copied.numbers = copy.deepcopy(self.numbers)
return copied
def pickup_candidates(self, x, y):
return [n for n in range(9) if self.boolcube[x][y][n]]
def fill(self, x, y, n):
for i in range(9):
px = x//3*3+i%3
py = y//3*3+i//3
self.boolcube[i][y][n] = False
self.boolcube[x][i][n] = False
self.boolcube[x][y][i] = False
self.boolcube[px][py][n] = False
self.boolcube[x][y][n] = True
self.numbers[x][y] = n
def ban(self, x, y, n):
self.boolcube[x][y][n] = False
def is_completed(self):
for x, y in generate_xy():
if self.numbers[x][y] is None:
return False
return True
def is_valid(self):
for x, y in generate_xy():
if len(self.pickup_candidates(x, y)) == 0:
return False
return True
def compute_impact_score(self, x, y, n):
count = 0
for i in range(9):
px = x//3*3+i%3
py = y//3*3+i//3
count += 1 if self.boolcube[i][y][n] else 0
count += 1 if self.boolcube[x][i][n] else 0
count += 1 if self.boolcube[x][y][i] else 0
count += 1 if self.boolcube[px][py][n] else 0
if self.boolcube[x][y][n]:
count -= 4
return count
def count_solution(problem):
has_changed = True
while has_changed:
has_changed = False
for x, y in generate_xy():
if problem.numbers[x][y] is not None:
continue
candidates = problem.pickup_candidates(x, y)
if len(candidates) == 1:
problem.fill(x, y, candidates[0])
has_changed = True
if not problem.is_valid():
return 0
if problem.is_completed():
return 1
solutions = 0
candidates = list()
for x, y in generate_xy():
if problem.numbers[x][y] is not None:
continue
for n in range(9):
score = problem.compute_impact_score(x, y, n)
candidates.append((score, x, y, n))
candidates.sort(reverse=True)
for score, x, y, n in candidates:
copied = problem.copy()
copied.fill(x, y, n)
problem.ban(x, y, n)
solutions += count_solution(copied)
return solutions
def decode_numbers(square_string):
pattern = re.compile('\\w ' + '\\|(.)'*9)
lines = square_string.replace('\r', '').split('\n')
index = 0
numbers = [[None for y in range(9)] for x in range(9)]
for y in range(9):
while True:
matched = pattern.search(lines[index])
index += 1
if matched is None:
continue
for x in range(9):
s = matched.group(x+1)
if s == '.':
s = None
elif s != 'X':
s = int(s)-1
numbers[x][y] = s
break
return numbers
def decode_xinfo(xinfo):
matched = re.search('if \'X\' is (\\d+), how many solutions', xinfo)
if matched is None:
raise Exception
return int(matched.group(1))-1
def generate_answer(numbers, xvalue):
problem = Square()
for x, y in generate_xy():
if numbers[x][y] is None:
continue
if numbers[x][y] == 'X':
problem.fill(x, y, xvalue)
else:
problem.fill(x, y, numbers[x][y])
solutions = count_solution(problem)
return str(solutions)
def main():
tn = telnetlib.Telnet('133.242.48.175', 65434)
while True:
time.sleep(0.5)
problem_string = tn.read_very_eager().decode()
if 'Stage' in problem_string:
numbers = decode_numbers(problem_string)
print(problem_string, end='')
x = decode_xinfo(problem_string)
answer = generate_answer(numbers, x)
print(answer)
tn.write(answer.encode()+b'\n')
if __name__ == '__main__':
main()
途中経過
'suDOKU(su-poison)' challenge for SECCON 2013.
by KeigoYAMAZAKI, 2013.11.22-
* Stage 1
1 2 3 4 5 6 7 8 9
$-+-+-$-+-+-$-+-+-$
A |6|4|2|.|X|5|.|8|9|
B |.|.|.|.|.|7|1|3|.|
C |1|.|.|.|9|.|.|2|.|
$-+-+-$-+-+-$-+-+-$
D |3|.|.|.|2|6|.|.|.|
E |7|.|.|8|.|9|.|.|2|
F |2|8|.|.|7|4|6|1|.|
$-+-+-$-+-+-$-+-+-$
G |.|7|1|.|.|3|.|6|.|
H |.|6|3|7|.|.|.|.|1|
I |5|.|8|.|6|.|.|7|.|
$-+-+-$-+-+-$-+-+-$
if 'X' is 1, how many solutions does this sudoku have? => 1
if 'X' is 3, how many solutions does this sudoku have? => 2
*** Good job!
* Stage 2
1 2 3 4 5 6 7 8 9
$-+-+-$-+-+-$-+-+-$
A |X|5|.|.|.|.|.|.|.|
B |.|.|6|5|7|3|2|.|.|
C |.|.|2|8|4|.|.|.|5|
$-+-+-$-+-+-$-+-+-$
D |.|.|8|.|3|7|9|.|1|
E |.|6|1|.|9|.|.|.|.|
F |5|.|7|4|.|.|.|.|.|
$-+-+-$-+-+-$-+-+-$
G |7|.|.|9|.|.|.|3|2|
H |.|.|.|.|.|.|.|4|.|
I |6|.|.|.|.|.|7|.|8|
$-+-+-$-+-+-$-+-+-$
if 'X' is 1, how many solutions does this sudoku have? => 0
if 'X' is 3, how many solutions does this sudoku have? => 0
if 'X' is 4, how many solutions does this sudoku have? => 1
if 'X' is 8, how many solutions does this sudoku have? => 3
if 'X' is 9, how many solutions does this sudoku have? => 12
*** Good job!
* Stage 3
1 2 3 4 5 6 7 8 9
$-+-+-$-+-+-$-+-+-$
A |.|3|5|1|6|4|.|.|9|
B |7|9|.|.|5|3|.|.|4|
C |.|.|1|.|.|.|5|2|3|
$-+-+-$-+-+-$-+-+-$
D |3|5|4|6|7|.|.|.|.|
E |.|.|6|9|.|.|3|.|.|
F |.|2|7|3|.|5|.|4|1|
$-+-+-$-+-+-$-+-+-$
G |4|6|.|5|.|7|2|.|8|
H |.|1|.|.|.|.|4|7|6|
I |8|.|X|4|.|.|9|.|.|
$-+-+-$-+-+-$-+-+-$
if 'X' is 2, how many solutions does this sudoku have? => 2
if 'X' is 3, how many solutions does this sudoku have? => 1
*** Good job!
* Stage 4
1 2 3 4 5 6 7 8 9
$-+-+-$-+-+-$-+-+-$
A |.|.|2|1|.|.|6|.|.|
B |1|.|5|.|8|.|.|.|.|
C |8|X|.|.|.|9|.|.|.|
$-+-+-$-+-+-$-+-+-$
D |.|.|7|.|.|.|5|.|.|
E |.|.|.|6|.|.|3|.|8|
F |.|3|.|5|2|4|.|.|1|
$-+-+-$-+-+-$-+-+-$
G |2|8|.|4|.|.|.|.|6|
H |6|.|.|9|.|3|8|2|.|
I |.|5|9|.|.|.|.|.|3|
$-+-+-$-+-+-$-+-+-$
if 'X' is 4, how many solutions does this sudoku have? => 2
if 'X' is 6, how many solutions does this sudoku have? => 0
if 'X' is 7, how many solutions does this sudoku have? => 1
*** Good job!
* Stage 5
1 2 3 4 5 6 7 8 9
$-+-+-$-+-+-$-+-+-$
A |.|.|.|2|3|5|8|4|9|
B |2|5|.|.|4|.|.|.|.|
C |3|4|.|X|8|.|.|5|.|
$-+-+-$-+-+-$-+-+-$
D |.|8|2|9|5|.|.|6|.|
E |1|.|.|6|.|8|5|.|4|
F |6|.|.|3|.|.|1|9|8|
$-+-+-$-+-+-$-+-+-$
G |.|6|.|8|.|2|.|7|.|
H |.|3|1|.|.|.|.|.|.|
I |.|.|.|5|9|.|.|1|.|
$-+-+-$-+-+-$-+-+-$
if 'X' is 1, how many solutions does this sudoku have? => 2
if 'X' is 7, how many solutions does this sudoku have? => 1
*** Good job!
* Stage 6
1 2 3 4 5 6 7 8 9
$-+-+-$-+-+-$-+-+-$
A |8|1|.|2|.|5|4|6|7|
B |.|.|.|.|7|6|1|8|9|
C |.|6|.|.|8|.|3|5|2|
$-+-+-$-+-+-$-+-+-$
D |1|.|.|9|2|4|.|3|X|
E |.|9|3|8|6|.|.|1|4|
F |7|4|.|3|5|1|.|2|.|
$-+-+-$-+-+-$-+-+-$
G |.|.|.|6|1|8|2|7|5|
H |.|.|.|7|4|3|.|.|1|
I |6|.|.|5|.|.|8|4|3|
$-+-+-$-+-+-$-+-+-$
if 'X' is 6, how many solutions does this sudoku have? => 2
if 'X' is 8, how many solutions does this sudoku have? => 1
*** Good job!
*************************************************************************
*** Congratulations! Flag is 'iitai-koto mo ienai konna yononaka-ja!' ***
*************************************************************************
フラグが得られました。ぱちぱち。