[Defenit CTF 2020] Misc - Puzzle write-up

Intro

대회가 진행중일때는 솔버수가 너무 낮아서 문제를 확인하지도 않았는데, 대회가 끝나고 나서 한번 풀어봤습니다.

I didn't even checked this problem during the contest due to too lower number of solvers.

After CTF finished, I just tried and solve this challenge.

 

15 puzzle은 일반적인 탐색 문제입니다. CTF와 같은 해킹 대회에서는 생소할 수 있지만, PS나 CP를 하는 사람들에게는 어느정도 풀어 볼 수 있는 기회가 있는 문제입니다. 학부때 인공지능 수업에서 일반적인 15 puzzle을 A* 알고리즘으로 풀어본적이 있었습니다. 그래서 이번 문제도 약간 변형되어 있긴 하지만, A* 알고리즘으로 풀 수 있을거라고 생각했습니다. 여기 나오는 15 puzzle은 인접한 칸과 바꾸는 것이 아닌, 체스의 나이트가 움직이는 범위의 칸과 바꿀 수 있다는 차이점이 있습니다.

15 puzzle is basic searching algorithm problem. It seems unfamiliar in security challenge like CTFs, for the people who are engaged in Problem solving or Competitive Programming area it could be familiar problem. I've seen this problem in artificial intelligence course in my university bachelor degree period. This problem can be solved with A* search algorithm. This is a little transformed version of 15 puzzle, but it is still solvable with A-star search algorithm.

The 15 puzzle have difference in movable range while classical 15 puzzle moves with adjacent 4 direction, this 15 puzzle moves like chess's knight.

 

Modeled to Graph Search Problem(그래프 탐색 문제로 모델링)

이 15 퍼즐문제는 그래프 탐색 문제로 모델링 될 수 있습니다. 모든 그래프 정점은 퍼즐의 상태를 타나내며, 처음 루트 노드는 15퍼즐의 입력 값에 따른 상태를 나타냅니다. 모든 노드들은 다른 노드로 간선이 연결되어 있으며, 만약 두개의 노드가 연결되어 있다면 한번의 움직임으로 해당 상태로 전환될 수 있다는 것을 뜻합니다.

아래 예시 그림에서는 루트 노드는 goal 상태를 나타냅니다. 루트 노드의 상태는 2개의 퍼즐 움직임이 가능한데, 이는 엣지로 연결된 자식 노드를 나타냅니다.

 

This 15 puzzle problem is a kind of graph search problem. This problem can be modeled to graph search.

Every graph node indicates the state of puzzle. Initial root node indicates input state of 15 puzzle. Every node has edge to other node. If two node is connected, it indicates that two node is both transformable with single move.

In this example diagram, the root node indicates the goal state. The root state 2 possible move, it is indicates as child node with edge.

이 탐색 문제를 풀기 위해서 우리는, BFS나 DFS같은 전통적인 탐색 알고리즘을 사용할 수 있습니다.

하지만 DFS는 최적화를 보장하지 않고, 따라서 시간이 너무 많이 걸릴 수 있습니다.

BFS 알고리즘은 최적회를 보장하지만 문제를 풀기에는 조금 느릴 수 있습니다.

To solve this search problem, we can use traditional search algorithm like BFS or DFS.

But DFS algorithm doesn't guarantee the optimal solution, so it could consume too much time.

BFS algorithm guarantee the optimal solution but it can be little bit slow to solve the problem.

A-star search algorithm

A* search algorithm can enhance search speed by prioritizing the node have more probability to reach the solution.

A* search algorithm seems very difficult, but there is nothring special than BFS(Breadth-First Search) graph searching algorithm.

In implementation level, there is one difference, while BFS uses simple queue, but A* uses priority queue.

 

Priority of node can be determined by heuristic function which is the core concept of A* algorithm.

You can use many kind of heuristic function to make this algorithm works, just not over estimating the node than real value.

 

Simple and naive heuristic function is the number of matched puzzle. I used this h-function, and I implemented this heuristic function as name hfunc.

 

Deciding unsolvable case

I refer the geeksforgeeks document to deciding the unsolvable case. In normal 15 puzzle case, unsolvable case can be detected with number of inversions. When puzzle moves, the number of inversion state alters.

Applying this rules to this type of problem, every puzzle moves, the number of inversion changes with odd number.

In goal state, number of inversions is 0(even number). From the goal state with one move, number of inversion is odd number. When number of inversion is odd number, with one move it alters to even number. The number of inversion's 2 modulo value is negated with every move.

 

 

 

solver.cpp

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, vector<int> > State;
const int correct[4][4] = {
	{0, 1, 2, 3},
	{4, 5, 6, 7},
	{8, 9, 10, 11},
	{12, 13, 14, 15}
};
int puz[4][4];
int hfunc(int puz[][4]) {
	int ret = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			ret += (correct[i][j] == puz[i][j] ? 1 : 0);
		}
	}
	return ret;
}
vector<pii> movable;
void dump(vector<int>& arr) {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			printf("%3d ", arr[i * 4 + j]);
		}
		puts("");
	}
	puts("======================================");
}
void vec2arr(vector<int>& vec, int puz[][4]) {
	for (int i = 0; i < 16; i++) {
		int& v = vec[i];
		puz[i / 4][i % 4] = v;
	}
}
void arr2vec(int puz[][4], vector<int>& vec) {
	vec.resize(16, 0);
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			vec[i * 4 + j] = puz[i][j];
		}
	}
}
void input() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			scanf("%d", &puz[i][j]);
		}
	}
}
pii findzero(int puz[][4]) {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (puz[i][j] == 0) return make_pair(i, j);
		}
	}
	assert(false);
	return make_pair(-1, -1);
}
bool isin(int x, int y) {
	return x >= 0 && y >= 0 && x < 4 && y < 4;
}
char dir[8][3] = {
	{-1, -2, 'q'},
	{-2, -1, 'w'},
	{-2, +1, 'e'},
	{-1, +2, 'r'},
	{+1, -2, 'a'},
	{+2, -1, 's'},
	{+2, +1, 'd'},
	{+1, +2, 'f'}
};
void unsolvable() {
	puts("unsolvable");
	exit(EXIT_SUCCESS);
}
int main() {
	input();
	State state;
	state.first = hfunc(puz);
	arr2vec(puz, state.second);
	pii zero = findzero(puz);
	int inv = 0;
	for (int i = 0; i < 16; i++) {
		for (int j = i + 1; j < 16; j++) {
			int a = state.second[i];
			int b = state.second[j];
			if (a > b) inv++;
		}
	}
	

	int id = ((zero.first + zero.second) & 1);
	if ((inv & 1) != id) {
		unsolvable();
	}
	
	map<vector<int>, State> visited;
	priority_queue<State> pq;
	visited[state.second] = make_pair(-1, vector<int>()); //initial state!
	pq.push(state);
	while (pq.size()) {
		State cur = pq.top(); pq.pop();
		if (cur.first == 16) {
			// puts("GOTCHA!");
			State p = cur;
			vector<char> move;
			while (p.second.size()) {
				if (visited[p.second].first != -1) {
					move.push_back(dir[visited[p.second].first][2]);
				}
				//To dump intermediate puzzle state
				//dump(p.second);
				p = visited[p.second];
			}
			while (move.size()) {
				putchar(move.back());
				puts("");
				move.pop_back();
			}
			return 0;
		}
		vec2arr(cur.second, puz); //puz <- 기존
		pii zero = findzero(puz);
		for (int k = 0; k < 8; k++) {
			int nx = dir[k][0] + zero.first;
			int ny = dir[k][1] + zero.second;
			if (isin(nx, ny)) {
				swap(puz[zero.first][zero.second], puz[nx][ny]); //위치 바꿈
				State next;
				next.first = hfunc(puz);
				arr2vec(puz, next.second);
				if (visited.find(next.second) == visited.end()) { //중복이 아닌 경우
					visited[next.second] = make_pair(k, cur.second); //마지막 움직임 형태와, 기존 형태를 저장함
					pq.push(next);
				}
				swap(puz[zero.first][zero.second], puz[nx][ny]); //원복 시킴
			}
		}
	}
	return 0;
}

do.py

#!/usr/bin/env python3

from pwn import *
import os

p = remote('puzzle.ctf.defenit.kr', 1515)

p.recvuntil("y/n)\n")
p.sendline("y")

def solve():
    global p
    
    with open("in.txt", "w") as f:
        for i in range(0, 4):
            f.write(p.recvuntil("\n").decode('utf-8'))
    os.system("./solver < in.txt > out.txt")
    with open("out.txt", "r") as f:
        p.send(f.read())
    resp = p.recvuntil("\n")[:-1].decode('utf-8')
    if "Solved" not in resp:
        return False
    else:
        return True
for i in range(0, 100):
    solve()
p.interactive()
p.close()

Got the flag!

 

Reference

https://www.geeksforgeeks.org/check-instance-15-puzzle-solvable/

https://gist.github.com/Einstrasse/d9b2503d068ae2a8937d15e985f02c3f