---
# System prepended metadata

title: Dominoues solution

---

Dominoues solution
===
## Description
The challenge is about combining three-letter dominoes into a full sentence. Each of the dominoes has to be used exactly once. 

For example, from DOM, OMI, MIN, INO, NOE, OES you create:

```
DOM
 OMI
  MIN
   INO
    NOE
     OES
```

After overlapping, you see that the word is `DOMINOES`

This challenge is inspired by another challenge prepared by me, that is about leaking all three-letters words and then use them to recover the whole CSRF token with only one page reload. 

## Solution

I used the `backtracking` algorithm to find all the possible solutions where the correctness function is the existence of each word in the `english top 10000` dictionary.

After running the algorithm, it produced `7296` correct solutions. 

From reading the first lines of the produced file we can notice that each sentence consists of the same words but in the permutated order. 

```
there_the_player_like_you_shall_solve_doubt_great_in_my_mind_that_puzzle_was_no_single
there_the_player_like_you_shall_solve_doubt_in_my_mind_that_great_puzzle_was_no_single
there_the_player_like_you_shall_solve_was_no_single_doubt_great_in_my_mind_that_puzzle
there_the_player_like_you_shall_solve_was_no_single_doubt_in_my_mind_that_great_puzzle
there_the_player_like_you_shall_single_was_no_solve_doubt_great_in_my_mind_that_puzzle
there_the_player_like_you_shall_single_was_no_solve_doubt_in_my_mind_that_great_puzzle
there_the_player_like_you_solve_doubt_great_in_my_mind_that_puzzle_was_no_shall_single
```

The idea of the challenge is to find the correct flag from these `7296` lines. From the challenge description, it was clear that the flag is in the unusual format, and that it consists of lower_case english words that when combined produce a  grammatically correct meaningful sentence.

The approach for reducing the number of lines is to filter out all "strange" sentences.

```
Start: 7296
^.*(the_was).*$\n - 1632
^.*(the_you).*$\n - 1632
^.*(the_that).*$\n - 528
^.*(was_no_shall).*$\n - 1752
^.*(was_no_solve).*$\n - 875
^.*(solve_doubt_great).*$\n - 90
^the_there.*$\n - 40 
^that_in_my_mind.*$\n - 86
^.*there_doubt_great.*$\n - 36
^.*that_great_in_my_mind.*$\n - 192
^.*player_like_there.*$\n - 28
^.*puzzle_the_doubt.*$\n - 12
^.*great_puzzle_player.*$\n - 13
^.*player_like_the_doubt.*$\n - 19
^.*player_like_doubt.*$\n - 65
^.*shall_solve_doubt.*$\n - 39
^.*player_like_the_puzzle.*$\n - 5
^.*there_doubt_in_my_mind.*$\n - 21
^.*was_no_single$\n - 116
^.*the_doubt_great.*$\n - 48

Left: 67
```

For example, the above approach can reduce the number of solutions to 67, from where it's relatively easy to find the best candidates for the flag, which is **justCTF{there_was_no_single_doubt_in_my_mind_that_great_player_like_you_shall_solve_the_puzzle}**

## PoC

I created PoC, that solves the challenge.

```sh
node --max-old-space-size=10000 dominoes-solver.js
```