Problem 161: Triominoes

Project Euler Problem 161 Solution

EulerSolve provides an optimized solution for Project Euler Problem 161, Triominoes, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The task is to count the number of tilings of a $9\times12$ rectangle by triominoes. The implementations allow all six orientations: the two straight trominoes and the four $L$-shaped trominoes. Because each piece covers exactly three cells, the obvious necessary condition is $3 \mid 9\cdot12$, so the challenge is not existence but exact enumeration. A direct search is still hopeless, since a local choice can affect cells one or two rows later. Mathematical Approach A moving three-row frontier with a two-row stored profile Process the board from top to bottom. At any stage, the dynamic program remembers which cells are already occupied in two consecutive frontier rows. A bit value of 1 means that the cell is already covered by pieces chosen earlier, and a bit value of 0 means that the cell must still be completed by pieces extending farther downward. The stored state therefore needs only $2W$ bits for width $W$. During one transition, a fresh third row is attached underneath those two rows, so the local search works on a temporary $3W$-bit mask. When that search finishes, the oldest row is dropped and the remaining two rows become the next stored profile. This is the key compression: the global tiling is huge, but all future decisions depend only on the occupancy pattern of the next two rows....

Detailed mathematical approach

Problem Summary

A triomino is a shape made of three unit squares joined along their edges. Its two basic forms are the straight triomino, three squares in a row, and the L-triomino, a $2\times2$ square with one square removed. With all orientations there are six pieces: the straight one horizontal or vertical, and the L with any one of the four squares of its $2\times2$ square missing. ^[2] A tiling covers every cell of a grid exactly once with such pieces, and tilings that are rotations or reflections of each other count as different. Every $n\times m$ grid with $3\mid nm$ can be tiled, since $3$ then divides $n$ or $m$ and straight pieces fill it, and a $2\times9$ grid has $41$ tilings. We must count the tilings of a $9\times12$ grid. ^[1]

The whole solution in one sentence: since a piece reaches at most two rows above its lowest row, we fill the grid row by row and count the partial fillings separately for each pattern of covered cells in the last two rows, updating all these counts once per row with a small search.

Mathematical Approach

We count tiny grids, show that two rows of information suffice, and turn each row into a search that produces every arrangement of new pieces exactly once.

1. Small grids

A grid of $2$ rows and $3$ columns has $3$ tilings: one straight piece in each row, or two L-pieces that interlock in two mirror-image ways. A $3\times3$ grid has $10$. Its three pieces cannot all be L-pieces, since each of those covers at most one of the four corners. A straight piece through the middle forces two more parallel ones, and one along a side leaves a $2\times3$ rectangle, tiled as above. Hence there are $2$ tilings by three parallel straight pieces and, for each of the four sides, $2$ with a straight piece there and two L-pieces: $2+4\cdot2=10$.

A computer can list tilings with one rule: always cover the first free cell in reading order, row by row from the top and from left to right. In a tiling, the piece covering that cell uses no earlier cell, since those are covered, so the free cell is its first cell; trying each of the six pieces with its first cell there, and continuing in the same way, finds every tiling exactly once. This search gives $11$ tilings for $2\times6$, the $41$ of $2\times9$ and $80092$ for $6\times6$. But it meets the tilings one at a time, and the $9\times9$ grid already has $928789262080$, so they must be counted in large groups.

2. Two rows are enough

We turn the grid so that it has $H=12$ rows of $W=9$ cells, which does not change the number of tilings. Rows are numbered $0,\dots,H-1$ from the top, columns $0,\dots,W-1$ from the left, and $(i,j)$ is the cell in row $i$ and column $j$. The lowest row of a piece is the bottom-most row it touches. A piece with lowest row $i$ lies in the rows $i-2$, $i-1$ and $i$, and only the vertical straight piece reaches row $i-2$.

Suppose that exactly those pieces of a tiling whose lowest row is smaller than $k$ are in place. All other pieces lie in row $k-2$ and below, so rows $0$ to $k-3$ are completely covered, rows $k-2$ and $k-1$ may have free cells, and the rows from $k$ on are empty. How the tiling can be completed depends only on which cells of rows $k-2$ and $k-1$ are covered; this pattern of $2W$ cells is the profile. We write it as two strings of $W$ digits, the older row $k-2$ first, with $1$ for a covered and $0$ for a free cell, and we treat the rows $-2$ and $-1$ above the grid as covered, so that no piece sticks out at the top.

3. Counting by profile

For $0\le k\le H$, a partial tiling of height $k$ is a set of non-overlapping pieces inside the grid, all with lowest row smaller than $k$, that covers rows $0$ to $k-3$. Let $F_k(s)$ be the number of those with profile $s$, and let $\mathbf 1$ be the full profile. Only the empty set has height $0$, so $F_0(\mathbf 1)=1$ and $F_0(s)=0$ otherwise. The tilings are exactly the partial tilings of height $H$ with profile $\mathbf 1$, so the answer is $F_H(\mathbf 1)$.

A step from a profile $s$ is a set of non-overlapping new pieces inside the grid, all with lowest row $k$, that use only cells left free by $s$ and cells of the empty row $k$, and after which row $k-2$ is full; its result $t$ is the profile of rows $k-1$ and $k$. With $T(s,t)$ the number of steps from $s$ to $t$,

$$F_{k+1}(t)=\sum_{s}F_k(s)\,T(s,t).$$

Indeed, removing the pieces with lowest row $k$ from a partial tiling of height $k+1$ with profile $t$ leaves a partial tiling of height $k$, because the removed pieces lie in rows $k-2$ to $k$. With $s$ its profile, the removed pieces form a step from $s$ to $t$; conversely, such a pair combines into a partial tiling of height $k+1$ with profile $t$, and the two operations undo each other. Computing $F_0,F_1,\dots$ layer by layer is dynamic programming on profiles. ^[3] In matrix language $F_H=F_0T^H$, so the answer counts the walks of length $H$ from the full profile to itself in the graph with $T(s,t)$ arrows from $s$ to $t$; this is the transfer-matrix method. ^[4]

4. Six pieces and their anchors

The cells of a piece in its lowest row $k$ are one, two or three neighbouring cells, and the rightmost of them is its anchor. Relative to its anchor $(k,c)$, the six pieces are

$$\begin{aligned}&\{(k-2,c),\,(k-1,c),\,(k,c)\},\\&\{(k,c-2),\,(k,c-1),\,(k,c)\},\\&\{(k-1,c),\,(k,c-1),\,(k,c)\},\\&\{(k-1,c-1),\,(k,c-1),\,(k,c)\},\\&\{(k-1,c-1),\,(k-1,c),\,(k,c)\},\\&\{(k-1,c),\,(k-1,c+1),\,(k,c)\}.\end{aligned}$$

The first two lines are the vertical and the horizontal straight piece. The lowest row of an L-piece is the bottom row of its $2\times2$ square. If the missing square is in the top row, two cells lie in row $k$, and the top cell stands above the right one (third line) or the left one (fourth line). If it is in the bottom row, the anchor is the only cell in row $k$, and the two top cells reach to the left (fifth line) or to the right (sixth line).

5. One row by a search

A search finds the steps from a profile by running through row $k$ from right to left, starting at $c=W-1$. When it arrives at column $c$, the cell $(k,c)$ is free, because a piece anchored further right covers cells of row $k$ only at and to the left of its anchor, and the search jumps past them. The search either leaves $(k,c)$ free for a later row and goes on at $c-1$, or makes $(k,c)$ the anchor of one of the six pieces whose other cells are inside the grid and free. It then goes on at $c-3$ after the horizontal piece, at $c-2$ after the third and fourth lines, and at $c-1$ otherwise. When no column is left, it accepts the result if row $k-2$ is full.

Every step is produced exactly once. Read a step from right to left: at each column that the search reaches, the cell $(k,c)$ is either not covered by the step or the anchor of exactly one of its pieces, whose shape is then known, so exactly one choice agrees with the step. Apart from the edges of the grid, only cells of rows $k-2$ and $k-1$ need to be tested.

6. Worked example: two columns

The C++ program checks itself on the $2\times9$ grid turned to $W=2$ columns and $H=9$ rows, a case that can be followed by hand. The steps between the profiles that occur are:

11|11 → 11|00 by adding nothing, since the horizontal piece needs three columns and every other piece a free cell in a stored row;
11|00 → 00|00 by adding nothing, or → 11|10, 11|01, 10|11, 01|11 by one of the four L-pieces in the $2\times2$ square of rows $k-1$ and $k$;
00|00 → 11|11 by two vertical pieces;
11|10 → 10|00 by adding nothing, or → 11|11 by the L-piece on $(k-1,1)$, $(k,0)$ and $(k,1)$; in mirror image, 11|01 → 01|00 or 11|11;
10|00 → 01|01 → 11|10 and 01|00 → 10|10 → 11|01, each time by one vertical piece;
10|11 and 01|11 have no step: their free older cell could only be covered by a vertical piece, which would need the covered cell below it.

After $3n$ rows nonzero counts can occur only on three of these eleven profiles: $f_n$ for 11|11, and $g_n$ each for the mirror images 10|00 and 01|00. One row later these counts sit on 11|00, 01|01 and 10|10. After the next row 11|00 has passed $f_n$ to each of its five results, and with the $g_n$ from 01|01 and 10|10 the profiles 11|10 and 11|01 hold $f_n+g_n$ each. In the third row 00|00 returns $f_n$ to 11|11, while 11|10 and 11|01 pass $f_n+g_n$ both to 11|11 and to 10|00 or 01|00. So

$$f_{n+1}=3f_n+2g_n,\qquad g_{n+1}=f_n+g_n,$$

with $f_0=1$ and $g_0=0$, which gives $f_1=3$, $f_2=11$ and $f_3=41$, the count of the statement. The first rule for $n+1$, with the second rule and $2g_n=f_{n+1}-3f_n$ inserted, becomes $f_{n+2}=4f_{n+1}-f_n$. This is the recurrence of the OEIS sequence $a(n)$ that begins $1,1,3,11,41,153$ at $n=0$, so $f_n=a(n+1)$; this number also counts the domino tilings of a $3\times2n$ rectangle. ^[5]

7. Which profiles occur

For $W=9$ there are $4^9=262144$ conceivable profiles, against $4^{12}=16777216$ if the long side were the width, and far fewer occur. In the first row only horizontal pieces fit; $j$ of them leave $9-3j$ free cells, and pieces and free cells can be put in order in $\binom{9-2j}{j}$ ways, so $1+7+10+1=19$ profiles follow the first row. Then come $8359$, $26922$, $33699$ and $33731$. The set after the sixth row equals the set after the fifth, and as each set determines the next, it never changes again.

Most of them are dead ends. If a free cell of the older row lies above a covered cell, only a vertical piece of the next step could cover it, and that piece needs the covered cell, so there is no step; this holds for $27170$ profiles. The number of covered cells of a profile is always a multiple of $3$, since pieces cover three cells and finished rows nine. The other $6561$ profiles are exactly those with this property in which every column is covered in both rows, only in the older row or in neither; there are $3^8$ of them, because for any first eight columns exactly one of the three column types for the last one gives a multiple of $3$. Each of them has a step, for instance a vertical piece in every column whose older cell is free.

How the Code Works

The C++ program ^[7] starts in main. parse_arguments reads --width=, --height= and --skip-checkpoints, with the defaults $9$ and $12$; an unknown argument, a malformed value or a size of $0$ gives exit code $1$, but neither the parser nor the area test of solve guards against the overflow of an int for huge values. Unless skipped, run_checkpoints requires solve(2, 9) to return the $41$ of Section 6, or the program exits with code $2$. Then main prints solve(width, height).

solve returns $0$ when the area is not a multiple of $3$, correctly, and also when the width is not between $1$ and $10$, the range in which the $3W$-bit masks of the search fit into a 32-bit int. That $0$ is not a count: --width=12 --height=9 prints $0$ for a grid with as many tilings as the $9\times12$ one. Otherwise solve sets up two vectors g_cur and g_next of $4^W$ counts of type long long, one per profile, gives the full profile $2^{2W}-1$ the count $1$, and runs $H$ rounds. Each round calls dfs_transition(width - 1, s, s) for every profile $s$ with a nonzero count, then swaps the vectors and clears g_next; the result is the final count of the full profile. For the $9\times12$ grid these 64-bit counts cannot overflow: every $F_k(s)$ that occurs is below $2^{55}$, and all terms of the sums are nonnegative. The additions are unchecked, however: with $9$ columns the counts exceed the range of long long from $14$ rows on.

dfs_transition(d, state, mask) is the search of Section 5 at column $d$. Bits $0$ to $W-1$ of mask hold row $k-2$, bits $W$ to $2W-1$ row $k-1$, and bits $2W$ to $3W-1$ the new row $k$. The branches are: leave the cell free, then the six pieces in the order of Section 4, each guarded by tests with get_bit; two of these tests examine the cell $(k,d-1)$, which is always free. When $d$ drops below $0$, the test ((mask + 1) & ((1 << g_width) - 1)) == 0 checks that row $k-2$ is full, because adding $1$ to $W$ ones carries through all of them; then g_cur[state] is added to g_next[mask >> g_width]. $T(s,t)$ is never stored: a profile reached by two steps receives the count twice.

The Python version fixes $W=9$ and $H=12$ and has no checkpoint. Its transitions(state) runs the same search and returns the pairs $(t,T(s,t))$, and lru_cache(maxsize=None) keeps every result, so each profile is searched only once. ^[6] Its solve keeps the counts in dictionaries of the profiles that occur, and its integers are unbounded. The Java version copies the C++ search and rounds with two long arrays, fixed to $9$ and $12$, without options, checkpoint or the tests at the start of solve.

Complexity and Verification

Apart from scanning and clearing the $4^W$ counts once per round, the cost is the number of calls of the search. Once all $33731$ profiles occur, a round makes $55455134$ calls in C++ and Java; the twelve rounds make $494202238$, of which $263655051$ reach the end of the row and $2702707$ pass the final test. Each of the two programs needs about one second (Apple M4 Max, GCC 16 with -O2, OpenJDK 17), and the two arrays of $2^{18}$ counts of $8$ bytes take $4$ MiB. Python searches every profile once, $55455134$ calls, keeps the $272825$ pairs $(s,t)$ with $T(s,t)\gt0$ in its cache, and then makes at most one update per pair and round; Python 3.11 needs about $13$ seconds.

The work could be cut. Almost half of a round, $25639149$ calls, goes to the $27170$ dead profiles of Section 7, which the programs keep, and the search could drop a branch before its call when it would move left of a column whose cell in row $k-2$ is still free; this finds the same steps with $1149062$ calls per round. A cell-by-cell version, which covers the first free cell in reading order and remembers the next $2W+1$ cells, never holds more than $7290$ states here.

The C++ program checks the $41$ tilings of the $2\times9$ grid before the main run. These further checks were made for this article and are not part of the published solutions:

the first-free-cell search of Section 1 agrees with the row method, in both positions of the grid, on every grid with at most $6$ rows, $9$ columns and $36$ cells;
a separately written cell-by-cell program agrees on these grids, gives $928789262080$ for $9\times9$, and gives for $9\times12$ the same count as all three published programs;
a search over all profiles reachable from the full one confirms the counts of Section 7, exact arithmetic confirms the bound $2^{55}$, and a copy of the C++ program with a counter confirms the numbers of calls above.

Footnotes and References

The references below supply the background facts used above; the reduction to profiles, the row search, the two-column recurrence and the profile counts are derived in this article.

Project Euler 161 — Triominoes. The official statement shows the six orientations of a triomino, gives 41 tilings of a 2 by 9 grid when reflected or rotated tilings count as different, and asks for the number of tilings of a 9 by 12 grid.
Wikipedia — Tromino. A tromino or triomino is a polyomino of size 3. There are two free trominoes, I and L, and six fixed trominoes, two I and four L shapes, when rotations are considered distinct.
cp-algorithms — Dynamic Programming on Broken Profile. Domino tilings of a grid are counted row by row, with dp[i, mask] for the first i rows and a recursive function that fills one row; Sections 3 and 5 use the same scheme with a mask of two rows.
Wikipedia — Adjacency matrix. The element (i, j) of Aⁿ counts the walks of length n from vertex i to vertex j, and for multigraphs the entries count edges. Section 4.7 of R. P. Stanley, Enumerative Combinatorics, Volume 1, second edition treats the transfer-matrix method; its Theorem 4.7.1 shows that the total weight of the walks of length n between two vertices of a weighted digraph is an entry of the n-th power of the weighted adjacency matrix.
OEIS A001835. The sequence a(n) = 4a(n − 1) − a(n − 2), a(0) = a(1) = 1, begins 1, 1, 3, 11, 41, 153, …, and a(n) counts the domino packings of a 3 × 2(n − 1) rectangle; Section 6 has fₙ = a(n + 1).
Python — functools.lru_cache. The decorator wraps a function with a memoizing callable; with maxsize=None the cache can grow without bound.
C++ — Euler161.cpp. The linked immutable revision, with dfs_transition, solve and run_checkpoints, is the implementation record for this article.

Problem 161 source code

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using i64 = long long;

struct Options {
    int width = 9;
    int height = 12;
    bool run_checkpoints = true;
};

int g_width = 0;
int g_state_count = 0;
std::vector<i64> g_cur;
std::vector<i64> g_next;

inline bool get_bit(const int mask, const int pos) {
    return ((mask >> pos) & 1) != 0;
}

inline int bit(const int pos) {
    return 1 << pos;
}

void dfs_transition(const int d, const int state, const int mask) {
    if (d < 0) {
        if (((mask + 1) & ((1 << g_width) - 1)) == 0) {
            g_next[static_cast<std::size_t>(mask >> g_width)] += g_cur[static_cast<std::size_t>(state)];
        }
        return;
    }

    dfs_transition(d - 1, state, mask);

    if (!get_bit(mask, d) && !get_bit(mask, d + g_width)) {
        dfs_transition(d - 1, state, mask | bit(d) | bit(d + g_width) | bit(d + 2 * g_width));
    }

    if (d >= 2) {
        dfs_transition(d - 3, state, mask | bit(d + 2 * g_width) | bit(d - 1 + 2 * g_width) | bit(d - 2 + 2 * g_width));
    }

    if (d >= 1 && !get_bit(mask, d + g_width) && !get_bit(mask, d + 2 * g_width - 1)) {
        dfs_transition(d - 2, state, mask | bit(d + g_width) | bit(d + 2 * g_width - 1) | bit(d + 2 * g_width));
    }

    if (d >= 1 && !get_bit(mask, d + g_width - 1) && !get_bit(mask, d + 2 * g_width - 1)) {
        dfs_transition(d - 2, state, mask | bit(d + g_width - 1) | bit(d + 2 * g_width - 1) | bit(d + 2 * g_width));
    }

    if (d >= 1 && !get_bit(mask, d + g_width - 1) && !get_bit(mask, d + g_width)) {
        dfs_transition(d - 1, state, mask | bit(d + g_width - 1) | bit(d + g_width) | bit(d + 2 * g_width));
    }

    if (d < g_width - 1 && !get_bit(mask, d + g_width) && !get_bit(mask, d + g_width + 1)) {
        dfs_transition(d - 1, state, mask | bit(d + g_width + 1) | bit(d + g_width) | bit(d + 2 * g_width));
    }
}

i64 solve(const int width, const int height) {
    if ((width * height) % 3 != 0) {
        return 0;
    }
    if (width <= 0 || width >= 11) {
        return 0;
    }

    g_width = width;
    g_state_count = 1 << (2 * width);
    g_cur.assign(static_cast<std::size_t>(g_state_count), 0);
    g_next.assign(static_cast<std::size_t>(g_state_count), 0);

    g_cur[static_cast<std::size_t>(g_state_count - 1)] = 1;

    for (int row = 0; row < height; ++row) {
        for (int s = 0; s < g_state_count; ++s) {
            if (g_cur[static_cast<std::size_t>(s)] == 0) {
                continue;
            }
            dfs_transition(width - 1, s, s);
        }
        g_cur.swap(g_next);
        std::fill(g_next.begin(), g_next.end(), 0);
    }

    return g_cur[static_cast<std::size_t>(g_state_count - 1)];
}

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--width=", options.width) ||
            parse_int_after_prefix(arg, "--height=", options.height)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.width >= 1 && options.height >= 1;
}

bool run_checkpoints() {
    if (solve(2, 9) != 41LL) {
        std::cerr << "Checkpoint failed for 2x9" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.width, options.height) << '\n';
    return 0;
}

Python

from __future__ import annotations

from collections import defaultdict
from functools import lru_cache


W = 9
H = 12
FULL = (1 << (2 * W)) - 1


def bit(mask: int, pos: int) -> bool:
    return ((mask >> pos) & 1) != 0


@lru_cache(maxsize=None)
def transitions(state: int) -> tuple[tuple[int, int], ...]:
    out: dict[int, int] = defaultdict(int)

    def dfs(d: int, mask: int) -> None:
        if d < 0:
            if ((mask + 1) & ((1 << W) - 1)) == 0:
                out[mask >> W] += 1
            return

        dfs(d - 1, mask)

        if not bit(mask, d) and not bit(mask, d + W):
            dfs(d - 1, mask | (1 << d) | (1 << (d + W)) | (1 << (d + 2 * W)))

        if d >= 2:
            dfs(d - 3, mask | (1 << (d + 2 * W)) | (1 << (d - 1 + 2 * W)) | (1 << (d - 2 + 2 * W)))

        if d >= 1 and not bit(mask, d + W) and not bit(mask, d + 2 * W - 1):
            dfs(d - 2, mask | (1 << (d + W)) | (1 << (d + 2 * W - 1)) | (1 << (d + 2 * W)))

        if d >= 1 and not bit(mask, d + W - 1) and not bit(mask, d + 2 * W - 1):
            dfs(d - 2, mask | (1 << (d + W - 1)) | (1 << (d + 2 * W - 1)) | (1 << (d + 2 * W)))

        if d >= 1 and not bit(mask, d + W - 1) and not bit(mask, d + W):
            dfs(d - 1, mask | (1 << (d + W - 1)) | (1 << (d + W)) | (1 << (d + 2 * W)))

        if d < W - 1 and not bit(mask, d + W) and not bit(mask, d + W + 1):
            dfs(d - 1, mask | (1 << (d + W + 1)) | (1 << (d + W)) | (1 << (d + 2 * W)))

    dfs(W - 1, state)
    return tuple(out.items())


def solve() -> int:
    if (W * H) % 3 != 0:
        return 0

    cur: dict[int, int] = {FULL: 1}
    for _ in range(H):
        nxt: dict[int, int] = defaultdict(int)
        for state, ways in cur.items():
            for dst, multiplicity in transitions(state):
                nxt[dst] += ways * multiplicity
        cur = nxt
    return cur.get(FULL, 0)


if __name__ == "__main__":
    print(solve())

Java

public class Euler161 {
    static int W;
    static long[] cur, nxt;

    static boolean bit(int mask, int pos) {
        return ((mask >> pos) & 1) != 0;
    }

    static void dfs(int d, int state, int mask) {
        if (d < 0) {
            if (((mask + 1) & ((1 << W) - 1)) == 0)
                nxt[mask >> W] += cur[state];
            return;
        }
        dfs(d - 1, state, mask);
        if (!bit(mask, d) && !bit(mask, d + W))
            dfs(d - 1, state, mask | (1 << d) | (1 << (d + W)) | (1 << (d + 2 * W)));
        if (d >= 2)
            dfs(d - 3, state, mask | (1 << (d + 2 * W)) | (1 << (d - 1 + 2 * W)) | (1 << (d - 2 + 2 * W)));
        if (d >= 1 && !bit(mask, d + W) && !bit(mask, d + 2 * W - 1))
            dfs(d - 2, state, mask | (1 << (d + W)) | (1 << (d + 2 * W - 1)) | (1 << (d + 2 * W)));
        if (d >= 1 && !bit(mask, d + W - 1) && !bit(mask, d + 2 * W - 1))
            dfs(d - 2, state, mask | (1 << (d + W - 1)) | (1 << (d + 2 * W - 1)) | (1 << (d + 2 * W)));
        if (d >= 1 && !bit(mask, d + W - 1) && !bit(mask, d + W))
            dfs(d - 1, state, mask | (1 << (d + W - 1)) | (1 << (d + W)) | (1 << (d + 2 * W)));
        if (d < W - 1 && !bit(mask, d + W) && !bit(mask, d + W + 1))
            dfs(d - 1, state, mask | (1 << (d + W + 1)) | (1 << (d + W)) | (1 << (d + 2 * W)));
    }

    public static void main(String[] args) {
        W = 9;
        int H = 12;
        int sc = 1 << (2 * W);
        cur = new long[sc];
        nxt = new long[sc];
        cur[sc - 1] = 1;
        for (int r = 0; r < H; r++) {
            for (int s = 0; s < sc; s++) {
                if (cur[s] == 0)
                    continue;
                dfs(W - 1, s, s);
            }
            long[] t = cur;
            cur = nxt;
            nxt = t;
            java.util.Arrays.fill(nxt, 0);
        }
        System.out.println(cur[sc - 1]);
    }
}