Note

This English version is a partial translation: it stops at the beginning of the part on bitwise operators. The whole problem, with its solution, is available in French: Dungeons and Diagrams.

To solve this problem, we will add code to the file d_and_d.c.

Description of the problem and solving method

D&D

Dungeons and Diagrams (D&D) is a Sudoku-like puzzle designed by Zach Barth that can be found on his website in a paper version or, more recently, as one of many small games in Zachtronics's Last Call BBS.

A D&D puzzle is made of a rectangular grid with monsters 👹 and treasures 💰 and numbered hints on columns and rows. To solve it, you need to fill some empty cells with walls in such a way that:

• The number of walls on a row is the given hint for this row. Same thing with columns.
• Every monster is in a dead end and every dead end contains a monster. A dead end is a cell with exactly one free neighbouring cell.
• Every treasure is in a treasure room which is a 3x3 wall-free square containing no monster and a single treasure, bordered with walls in all but one cell: its entrance.
• Outside treasure rooms, hallways are one cell wide: there is no 2x2 square of free cells.
• The induced graph on the non-wall cells is connected. Neighbourhood of a cell doesn't account for diagonals.

We suppose here that every grid admits a unique solution.

Here is an example 6x6 grid and its solution:

Une grille 6x6 : monstres, trésor et nombres de murs attendus par ligne et par colonne.

Son unique solution (murs en bleu).

Question 1. Try to solve the 9 problems given in the above PDF with pen and paper.

Question 2. What can be said about the graph of a solution for a treasure-less problem?

If we consider a solution satisfying the rows and columns constraints, we can fill a treasure room with walls and place a monster at its entrance to check that the graph is valid.

Son unique solution (murs en bleu).

\(\Rightarrow\)

La salle au trésor remplie de murs (en orange) et un monstre placé à son unique entrée (encadré).

We now have a way of validating solutions:

• check that every column and row contains the right amount of walls
• verify that every treasure is inside a proper treasure room
• fill the treasure rooms with walls and place a monster at their entrance
• check that the graph of the grid is connected, that its leaves are exactly the cells containing monsters and that it contains no 2x2 square of free cells.

Actually, we don't need to check the last property with a graph search. For all the known puzzles, it's sufficient to check that the graph is locally valid:

• every cell with a monster is of degree 1
• every free cell is of degree at least 2
• there's no square of free cells

Question 3. How could this be a wrong way to check for a solution?

Bonus: find a grid where a graph search is needed for checking connectedness.

Given that we already checked that treasure rooms have a unique entrance, we can reorder the tests to check for a solution:

• check that every column and row contains the right amount of walls
• check that every cell with a monster is of degree 1
• check that every free cell is of degree at least 2
• verify that every treasure is inside a proper treasure room
• fill the treasure rooms with walls
• check that the grid does not contain a 2x2 square of free cells

Encoding boards in 64 bits

We are going to solve the puzzle by backtracking in C. All grids being of size 8x8, we can store a boolean data for each cell in a 64-bit unsigned integer. Every bit is linked to a cell. We fix the following order here:

Numérotation des cases : la case $i$ correspond au bit $a_i$.

The binary word \(a_{63} \dots a_0\) on 64 bits has the \(a_i\) bit linked to the cell \(i\).

We are going to associate three integers to a given puzzle:

• the board itself where we place a bit at 1 to account for a wall in this cell
• the monsters where every cell with a monster has a bit at 1
• the treasures where every cell with a treasure has a bit at 1

As an example, consider the grid:

Grille dont les monstres occupent les cases 15, 18, 31, 47 et 63.

Monsters are in cells 15, 18, 31, 47 and 63. This means the integer can be written

\[ 1000000000000000100000000000000010000000000001001000000000000000 \]

in binary, which amounts to 9223512776490909696 in decimal and 0x8000800080048000 in hex.

We can then directly write in C:

// at start of file
#include <stdint.h>
typedef uint64_t board;

// then later
board monsters = 0x8000800080048000;

We could also handle an expanded view of the monsters as an array of 64 bools. Using this representation, we would get the following value in C:

// at start of file
#include <stdbool.h>
typedef bool map[64];

// then later
map monsters = {
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 1,
    0, 0, 1, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 1,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 1,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 1,
};

Question 4. Write a function of the given prototype

board map_to_board(map m);

that returns the integer encoding of the map m.

Solution

board map_to_board(map m)
{
    board b = 0;
    // m[63] must be the most significant bit: iterate backwards
    for(int i = 63; i >= 0; i--)
    {
        b = b * 2;
        if (m[i])
            b = b + 1;
    }
    return b;
}

Question 5. Write a function of the given prototype

void board_to_map(board b, map m);

that takes as arguments an integer encoding b and a map m and places in m the expansion of b.

Solution

void board_to_map(board b, map m)
{
    for(int i = 0; i < 64; i++)
    {
        m[i] = b % 2 == 1;
        b = b / 2;
    }
}

Question 6. Test these two functions, especially the fact that they are reciprocals.

Encoding the problem

To encode a problem, we will use the following type in C:

typedef char constraint[8];

struct problem {
    board monsters;
    board treasures;
    constraint rows;
    constraint columns;
};

typedef struct problem problem;

To define a problem, we can do it directly like this:

problem p = {
    0x8000800080048000,
    0x20000000000,
    { 3,2,5,3,4,1,4,4 },
    { 1,4,2,7,0,4,4,4 }
};

But, to improve clarity, we can label the fields as in:

problem p = {
    .monsters = 0x8000800080048000,
    .treasures = 0x20000000000,
    .rows = { 3,2,5,3,4,1,4,4 },
    .columns = { 1,4,2,7,0,4,4,4 }
};

Moreover, this syntax allows us to omit any field, which is then set to 0. We can then use the just-defined functions like this:

problem p = {
    .rows = { 3,2,5,3,4,1,4,4 },
    .columns = { 1,4,2,7,0,4,4,4 }
};

map monsters = {
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 1,
    0, 0, 1, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 1,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 1,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 1,
};

map treasures = {
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 1, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0,
};
// or faster
map treasure = { [41] = 1 }; // set the 41st bool to 1

p.monsters = map_to_board(monsters);
p.treasures = map_to_board(treasures);

Planning the backtracking

We are going to make partial fills of the grid to solve the problem. We reuse the board and moves analogy to go from a grid to another along the backtracking tree.

Most of the rules to check for a solution apply on a complete board so we could choose only to check for solutions on the leaves of the backtracking tree. But doing so would mean exploring way too many boards.

Taking the fact to place or not a wall on a given cell as a move, we would get a tree with \(2^{64}\) leaves!

We will instead consider moves filling a whole row knowing it should hold \(k\) walls.

Question 7. If rows hints are given by the numbers \(l_1, \dots, l_8\), show that we will get a backtracking tree with

\[ \prod_{k=1}^8 \binom{8}{l_k} \]

leaves.

When \(l_1 = \dots = l_8 = 4\), compare this number with \(2^{64}\).

Even if this new number is way less than the other one, it's still impossible to do an exhaustive search in this way. Thus, we are going to search for nodes in the backtracking tree leading for sure to no solutions.

First, we will restrict to row fillings that don't clash with monsters or treasures. Then, if we are on a node having filled the first \(k\) rows, we check:

• that no column has strictly more walls than the hint (column overload)
• that no monster is trapped, that is, every monster has a free cell in its neighbourhood (trapped monsters)
• that no free cell on the first \(k\) rows is of degree \(\le 1\) (no deadend upto row)

We have given the short names of these tests that will be used in the later questions.

Bitwise operators in C

For the sake of clarity, we are going to write 0b10101 for a binary value in C although it's not valid in standard C (before C23). In formulas, we will write \({10101}_2\).

We will now study bitwise operators acting directly on the bits of an integer.