Pour résoudre ce problème, on partira du fichier d_and_d.c.
Présentation du problème et de la résolution¶
D&D¶
Dungeons and Diagrams (D&D) est un casse-tête type Sudoku inventé par Zach Barth et présenté initialement sur son site en version papier et, plus récemment, au sein du jeu Last Call BBS de Zachtronics.
Une grille de D&D est la donnée d'une grille rectangulaire sur laquelle figurent des monstres 👹 et des trésors 💰, ainsi que des indications chiffrées sur les colonnes et les lignes. Le but est de remplir certaines cases vides par des murs en respectant les règles suivantes :
- Le nombre de murs sur une ligne (resp. une colonne) correspond au nombre associé à cette ligne (resp. cette colonne).
- Tous les monstres sont dans des impasses et toutes les impasses contiennent des monstres. Une impasse est une case ayant exactement une case voisine libre.
- Chaque trésor est dans une salle au trésor qui est un carré sans mur de taille 3x3 ne contenant aucun monstre et un seul trésor et qui, de plus, est bordé de murs sauf en exactement une case qui doit être libre.
- En dehors des salles au trésor, les couloirs ont une largeur d'une case : il n'y a pas de carré 2x2 de cases libres.
- Le graphe induit par la grille avec des connexions directes, mais pas en diagonale, est connexe.
On suppose que les grilles admettent une unique solution.
Ainsi, par exemple, une grille 6x6 et son unique solution :
Question 1. Résoudre manuellement les 9 problèmes du PDF donné en lien au-dessus.
Corrigé
On peut vérifier ses solutions avec le programme écrit dans la suite de ce problème. Les solutions des 9 grilles de la section Exemples sont données à la fin de cette section.
Question 2. Que peut-on dire du graphe d'une solution pour un problème sans trésor ?
Corrigé
C'est un graphe connexe dont les sommets de degré 1 (les feuilles) sont exactement les cases contenant des monstres, tous les autres sommets étant de degré au moins 2, et qui ne contient aucun carré 2x2 de cases libres.
Ce n'est pas forcément un arbre : un couloir peut faire le tour d'un bloc de murs et former un cycle. C'est le cas pour la grille 3 de la liste des 64 grilles, dont la solution contient un couloir circulaire.
Si on considère une grille satisfaisant les contraintes de lignes et de colonnes, une fois une salle au trésor identifiée, il est possible de la remplir et de placer un monstre à son unique entrée.
\(\Rightarrow\)
On en déduit ainsi une méthode de vérification des solutions :
- tester qu'il y a le bon nombre de murs dans chaque ligne et chaque colonne
- vérifier que chaque trésor est dans une salle au trésor conforme
- remplir les salles au trésor et placer un monstre à leur entrée
- vérifier que le graphe est connexe, que ses feuilles sont exactement les cases contenant des monstres et qu'il ne contient pas de carré 2x2 de cases libres.
En pratique, il n'est pas nécessaire de vérifier la dernière condition avec un parcours de graphe, on peut se contenter de vérifier que le graphe est localement conforme :
- chaque case avec un monstre est de degré 1
- chaque case libre est de degré au moins 2
- il n'existe pas de carré de cases libres
Question 3. Pourquoi cette vérification n'est pas suffisante a priori ?
Bonus : trouver une grille pour laquelle cette approximation ne permet pas d'obtenir la solution.
Corrigé
Ces conditions sont locales : elles ne garantissent pas que le graphe est connexe. Plusieurs composantes connexes vérifiant chacune les conditions locales seraient acceptées.
Bonus : avec les indications de lignes \(0, 8, 0, 8, 0, 8, 0, 8\), des 4 sur toutes les colonnes et des monstres aux deux extrémités des lignes paires, les lignes sont entièrement forcées et on obtient :
M......M
########
M......M
########
M......M
########
M......M
########
Cette grille vérifie toutes les conditions locales (et le programme final l'affiche comme solution) alors que le graphe a quatre composantes connexes : la grille n'a en fait aucune solution.
Sur les 64 grilles de Last Call BBS, l'approximation donne cependant à chaque fois l'unique solution.
Compte tenu de la vérification de la présence d'une unique entrée dans une salle au trésor, on peut réordonner les vérifications :
- tester qu'il y a le bon nombre de murs dans chaque ligne et chaque colonne
- vérifier que les cases contenant des monstres sont de degré 1
- vérifier que les cases libres sont de degré au moins 2
- vérifier que chaque trésor est dans une salle au trésor conforme
- remplir les salles au trésor
- vérifier que la grille résultante ne contient pas de carré de cases libres
Représentation des plateaux en 64 bits¶
On va résoudre ce casse-tête par backtracking en C. Les grilles étant de taille 8x8, on peut ainsi représenter une information booléenne sur chaque case à l'aide d'entiers non signés sur 64 bits : chaque bit est associé à une case.
On choisit ici l'ordre suivant :
qui correspond au mot binaire \(a_{63} \dots a_0\) sur 64 bits avec \(a_i\) représentant l'information sur la case \(i\).
On va associer trois entiers à une grille :
- le plateau (board) où un booléen vrai indique la présence d'un mur
- les monstres où un booléen vrai indique la présence d'un monstre
- les trésors où un booléen vrai indique la présence d'un trésor
Par exemple, pour la grille :
on a les monstres dans les positions 15, 18, 31, 47 et 63. Cela correspond alors à l'entier s'écrivant en binaire
et qui vaut 9223512776490909696 en décimal ainsi que 0x8000800080048000
en hexadécimal.
On pourra écrire en C :
// au début du fichier
#include <stdint.h>
typedef uint64_t board;
// puis
board monsters = 0x8000800080048000;
On pourrait considérer une représentation développée sous la forme d'un tableau de 64 booléens. Dans ce cas-là, on obtiendrait la valeur suivante en C :
// au début du fichier
#include <stdbool.h>
typedef bool map[64];
// puis
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. Écrire une fonction de signature
board map_to_board(map m);
qui renvoie la représentation entière associée à un tableau.
Corrigé
On construit l'entier en partant du bit de poids fort m[63] (schéma de
Horner) :
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. Écrire une fonction de signature
void board_to_map(board b, map m);
qui prend en entrée une représentation entière b,
un tableau m de 64 cases et place dans m le tableau de booléens déduit de
b.
Corrigé
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. Faire des tests pour vérifier que ces deux fonctions sont correctes. Notamment, qu'elles sont réciproques l'une de l'autre.
Corrigé
#include <assert.h>
void test_map_board(void)
{
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,
};
assert(map_to_board(monsters) == 0x8000800080048000);
map m;
board b = 0x123456789abcdef1;
for (int k = 0; k < 1000; k++)
{
board_to_map(b, m);
assert(map_to_board(m) == b);
// nombres pseudo-aléatoires (générateur congruentiel)
b = b * 6364136223846793005 + 1442695040888963407;
}
}
Comme board_to_map est injective sur les tableaux de booléens et que
map_to_board(board_to_map(b)) = b pour tout b, les deux fonctions sont
bien réciproques.
Représentation du problème¶
Pour représenter le problème, on utilise le type suivant en C :
typedef char constraint[8];
struct problem {
board monsters;
board treasures;
constraint rows;
constraint columns;
};
typedef struct problem problem;
Pour définir un problème, on peut le faire directement comme ici :
problem p = {
0x8000800080048000,
0x20000000000,
{ 3,2,5,3,4,1,4,4 },
{ 1,4,2,7,0,4,4,4 }
};
Mais par lisibilité, on peut préciser les noms des champs comme ici :
problem p = {
.monsters = 0x8000800080048000,
.treasures = 0x20000000000,
.rows = { 3,2,5,3,4,1,4,4 },
.columns = { 1,4,2,7,0,4,4,4 }
};
Cette dernière syntaxe a l'avantage de permettre d'omettre n'importe quel champ, qui est alors initialisé à 0. On peut ainsi utiliser les fonctions précédemment définies pour présenter le problème de manière plus lisible dans le code source :
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,
};
// ou plus rapidement
map treasure = { [41] = 1 }; // met 1 à l'indice 41 et 0 ailleurs
p.monsters = map_to_board(monsters);
p.treasures = map_to_board(treasures);
Choix pour le backtracking¶
On va effectuer des remplissages incrémentaux de la grille pour résoudre ce problème par backtracking. On reprend donc la terminologie de plateau et de coups permettant de passer d'un plateau à un autre.
Une majeure partie des conditions de résolution portant sur des grilles complètes, on pourrait se contenter de vérifier uniquement les grilles remplies. En faisant cela, on obtient un arbre déraisonnablement grand.
Par exemple, avec comme coup le fait, pour une position donnée, de choisir ou pas de placer un mur, on obtient un arbre binaire ayant \(2^{64}\) feuilles.
On va plutôt considérer les coups consistant à placer directement \(k\) murs sur une ligne dont on sait qu'elle doit en contenir \(k\).
Question 7. Justifier que si les indications de contraintes sur les lignes sont données par les nombres \(l_1, \dots, l_8\) alors on obtient ainsi un arbre de backtracking ayant
feuilles.
Dans le cas où \(l_1 = \dots = l_8 = 4\), comparer ce nombre avec le nombre obtenu en effectuant des mouvements case par case.
Corrigé
L'arbre a 8 niveaux : au niveau \(k\), on choisit la ligne \(k\). Un nœud de profondeur \(k - 1\) a exactement \(\binom{8}{l_k}\) fils, un par choix des \(l_k\) cases de murs parmi les 8 cases de la ligne, indépendamment des lignes précédentes. Par récurrence sur \(k\), il y a donc \(\prod_{j=1}^{k} \binom{8}{l_j}\) nœuds de profondeur \(k\), et les feuilles sont les nœuds de profondeur 8.
Pour \(l_k = 4\), on obtient \(\binom{8}{4}^8 = 70^8 \approx 5{,}8 \cdot 10^{14}\) feuilles contre \(2^{64} \approx 1{,}8 \cdot 10^{19}\), soit environ \(32\,000\) fois moins.
Même si ce nombre est beaucoup plus petit que le précédent, cela reste prohibitif pour faire une recherche exhaustive.
On va donc adopter une détection des nœuds pour lesquels on est certain de ne pas pouvoir résoudre le problème.
Tout d'abord, on restreint les lignes à celles qui ne placent pas un mur sur la même case qu'un monstre ou un trésor.
Ensuite, si on a un nœud correspondant à avoir rempli les \(k\) premières lignes, on vérifie :
- que le nombre de murs dans une colonne n'est pas strictement supérieur à la contrainte (column overload)
- qu'aucun monstre n'est sur une case de degré 0 (trapped monsters)
- qu'aucune case libre sur les \(k\) premières lignes n'est de degré \(\le 1\) (no deadend upto row)
On a indiqué entre parenthèses les noms des fonctions qu'on programmera dans la suite pour réaliser ces tests.
Opérations bit à bit en C¶
Dans ce paragraphe, on notera 0b10101 une valeur en binaire en C. Cette
notation, calquée sur la notation hexadécimale, n'est pas valide en C standard
(avant C23), mais rendra les exemples plus lisibles. De même, dans les
formules, on notera \({10101}_2\) un nombre écrit en binaire.
On va étudier ici des opérateurs opérant directement sur l'écriture binaire des entiers. Aucun de ces opérateurs n'est explicitement au programme, cependant, leur usage permet, selon les contextes, d'avoir un code plus efficace et plus lisible.
Opérateurs de décalage¶
On utilise l'opération x >> k pour décaler l'écriture de x de \(k\) bits vers
la droite, cela revient donc à réaliser une division entière par \(2^k\)
(pour un entier non signé).
De même, on utilise l'opération x << k pour décaler son écriture de \(k\) bits
vers la gauche en rajoutant des 0.
Exemple :
123 >> 3vaut 15 car123 = 0b1111011donc123 >> 3 = 0b1111 = 15123 << 2vaut 492 car123 << 2 = 0b111101100 = 492
Pour calculer \(2^k\) on peut ainsi écrire 1 << k mais cela pose un problème
dès que \(k \ge 31\) parce que 1 est un int (sur 32 bits en général) : le
calcul provoque un dépassement de capacité, ce qui est un comportement indéfini
en C (en pratique, on obtient un résultat faux). Pour \(k \le 63\), on peut
régler ce problème en utilisant 1ULL << k car 1ULL est la constante 1 en
unsigned long long, type d'au moins 64 bits (1UL convient sous Linux et
macOS, où unsigned long fait 64 bits, mais pas sous Windows).
Cependant, comme ce problème n'est pas propre aux constantes, on préfèrera
utiliser une coercition comme ici : (uint64_t)x << k qui fonctionne quand x
est un int.
On donne dans le code fourni une fonction
uint64_t bit(int pos)
{
return (uint64_t) 1 << pos;
}
afin de pouvoir écrire directement bit(n)
pour calculer \(2^n\) avec \(n \in \range{0}{63}\).
Opérateurs logiques¶
Il est possible de réaliser les opérations logiques connues sur les booléens en les appliquant bit à bit. Pour cela, on utilise :
a & bpour réaliser un et logique entre chaque bit. Ainsi, en écrivant abusivement en binaire, on a0b10110 & 0b11010qui vaut0b10010.a | bpour réaliser un ou logique entre chaque bit. Ainsi, on a0b10110 | 0b11010qui vaut0b11110.a ^ bpour réaliser un ou exclusif logique entre chaque bit. Ainsi, on a0b10110 ^ 0b11010qui vaut0b01100.~apour réaliser la négation logique de chaque bit. Ainsi, sur 5 bits, on a~0b10101qui vaut0b01010.
Une manière classique d'utiliser & est de réaliser
des masquages : on stocke dans une variable mask les bits que l'on veut
étudier et on écrit x & mask pour ne conserver que ceux-ci.
L'opération | permet de réaliser efficacement une addition d'entiers dont les
bits sont disjoints. En effet, comme il n'y a pas de retenue dans ce cas-là, il
suffit de superposer les écritures avec un ou.
Remarque
Ces opérations utilisent de simples portes logiques et sont très rapides à exécuter sur un processeur.
Notons que le compilateur les privilégie souvent. Par exemple, pour tester
la parité, x % 2 == 0 sera traduit par un test de nullité de x & 1
et les divisions/multiplications par \(2^k\) sont remplacées par des décalages.
Popcount¶
On va avoir besoin de compter les murs ou les cases libres, pour cela
on utilise une opération appelée popcount (pour population count)
qui permet, étant donné un entier non signé x sur 64 bits de renvoyer
le nombre \(p(x) \in \range{0}{64}\) de 1 dans son écriture binaire.
Dans la suite, on utilisera cette fonction sur un plateau pour compter les murs ou sur sa négation pour compter les cases libres.
Calcul naïf¶
Pour réaliser un calcul naïf, on va juste itérer sur les bits en faisant des tests de parité et des divisions par 2.
Question 8. Écrire une fonction de signature
int popcount_slow(uint64_t x);
qui effectue ce calcul.
Corrigé
int popcount_slow(uint64_t v)
{
int s = 0;
while(v != 0)
{
if (v % 2 == 1)
s = s+1;
v = v/2;
}
return s;
}
On pourrait penser que ce code est long en raison de la boucle, mais en fait, celle-ci sera sûrement déroulée par le compilateur et le problème vient des branchements induits par les tests de parité.
Calcul par masquage et additions¶
Soit \(p > 0\) et \(x,y\) deux entiers tels que \(x, y \le p < 2^p\). On a alors \(x + y \le 2p < 2^{p+1}\) ainsi, si \(z = x 2^p + y\), en considérant le masque \(m = 2^p - 1\), on peut calculer \(x+y\) ainsi :
(z & m) + ((z & (m << p)) >> p)
Cette remarque a priori anodine permet de réaliser un calcul efficace de
popcount. En effet, on souhaite effectuer en place la somme de tous les bits
d'un entier.
Si x est un entier sur 8 bits, on peut se servir du procédé de masquage pour
réaliser plusieurs additions d'un coup à l'aide des masques
Par exemple, si \(x = 173 = {10101101}_2\), on va avoir :
Ici, les couleurs servent à identifier les sous-mots sur lesquels portent les additions.
Le dernier résultat est alors le nombre de 1 présents dans \(x\) : \({00000101}_2 = 5\).
On en déduit le programme C suivant :
unsigned char popcount_byte(unsigned char x)
{
unsigned char m1 = 0x55; // 0b01010101
unsigned char m2 = 0x33; // 0b00110011
unsigned char m3 = 0x0f; // 0b00001111
x = (x&m1) + ((x&(m1<<1))>>1);
x = (x&m2) + ((x&(m2<<2))>>2);
x = (x&m3) + ((x&(m3<<4))>>4);
return x;
}
Question 9. En déduire une fonction de signature
int popcount(uint64_t x);
qui calcule le popcount d'un entier sur 64 bits en utilisant cette méthode. On
peut se contenter de renvoyer un int car on sait que la valeur renvoyée est
dans \(\range{0}{64}\).
Corrigé
Il faut \(\log_2 64 = 6\) étapes, avec des blocs de taille 1, 2, 4, 8, 16 puis 32 bits :
int popcount(uint64_t v)
{
uint64_t mask_1 = 0x5555555555555555;
uint64_t mask_2 = 0x3333333333333333;
uint64_t mask_3 = 0x0f0f0f0f0f0f0f0f;
uint64_t mask_4 = 0x00ff00ff00ff00ff;
uint64_t mask_5 = 0x0000ffff0000ffff;
uint64_t mask_6 = 0x00000000ffffffff;
v = (v & mask_1) + ((v & (mask_1 << 1)) >> 1);
v = (v & mask_2) + ((v & (mask_2 << 2)) >> 2);
v = (v & mask_3) + ((v & (mask_3 << 4)) >> 4);
v = (v & mask_4) + ((v & (mask_4 << 8)) >> 8);
v = (v & mask_5) + ((v & (mask_5 << 16)) >> 16);
v = (v & mask_6) + ((v & (mask_6 << 32)) >> 32);
return v;
}
Question 10. Combien cette fonction fait-elle d'opérations élémentaires ?
Corrigé
Les masques décalés mask_i << k sont des constantes calculées à la
compilation. Chaque étape fait donc deux &, un décalage >> et une
addition, soit 4 opérations, et la fonction fait \(6 \times 4 = 24\)
opérations élémentaires, sans aucun branchement, quel que soit x.
La version naïve fait jusqu'à 64 tours de boucle, chacun avec un test.
Instruction assembleur¶
Il existe une fonction __builtin_popcountll (extension de gcc et clang)
permettant de réaliser un popcount grâce à une instruction assembleur quand
elle est disponible sur l'architecture visée, ou avec le code qu'on vient de
voir quand ce n'est pas le cas.
Si votre processeur dispose de cette instruction (processeur x86-64), vous
pouvez compiler avec le flag -mpopcnt pour l'utiliser. Cela permettra
d'améliorer les performances.
Squelette du backtracking¶
La fonction récursive solve réalisant le
backtracking a la structure suivante :
void solve(problem *p, int row, board b)
{
// teste si b est une impasse et sort
// b est une feuille de l'arbre
if(row == 8)
{
// teste et sort si ce n'est pas une solution
printf("Solution %lx\n", b);
print_board(p, b);
return;
}
// pour chaque mouvement move valide dans
// la rangée row
solve(p, row+1, b+move);
}
Question 11. Écrire une fonction de signature
void print_board(problem *p, board b);
qui permet d'afficher le plateau avec un affichage comme celui-ci :
###...##
#...#...
M.#.#...
#...#T..
###.####
.....#.M
M#M#.#.#
####...#
où # est un mur, M est un monstre,
T un trésor et . est une case libre.
Corrigé
void print_board(problem *p, board b)
{
for (int i = 0; i < 64; i++)
{
if (((b >> i) & 1) != 0)
putchar('#');
else if (((p->monsters >> i) & 1) != 0)
putchar('M');
else if (((p->treasures >> i) & 1) != 0)
putchar('T');
else putchar('.');
if (i % 8 == 7) printf("\n");
}
}
Afin de réaliser la boucle sur les mouvements, on peut itérer sur les 256 placements possibles de murs, ne garder que ceux qui ont le bon nombre de murs et qui ne se superposent pas aux monstres et aux trésors.
Question 12. Écrire le test permettant de s'assurer que
move n'est pas en conflit avec les monstres
et les trésors du problème p.
Corrigé
move est le placement de murs déjà décalé sur la ligne row :
// ensure there's no overlap with walls/monsters/treasures
if ((move & (p->monsters | p->treasures)) != 0)
continue;
Question 13. Écrire la boucle en utilisant popcount
pour tester qu'il y a le bon nombre de murs.
Corrigé
for(int i = 0; i < 256; i++)
{
if (popcount(i) == p->rows[row])
{
uint64_t move = (uint64_t)i << (8*row);
// ensure there's no overlap with walls/monsters/treasures
if ((move & (p->monsters | p->treasures)) != 0)
continue;
solve(p, row+1, b + move);
}
}
La fonction précédente va refaire continuellement
les mêmes calculs de popcount.
Question 14. Dans le programme donné, il y a une variable globale
int enum_popcount_byte[256];
Rajouter les instructions dans main pour que
enum_popcount_byte[i] contienne la valeur popcount(i) et en déduire une
version plus efficace de la boucle précédente.
Corrigé
Dans main, avant les appels à solve :
for(int i = 0; i < 256; i++)
enum_popcount_byte[i] = popcount(i);
puis, dans solve, on remplace le test popcount(i) == p->rows[row] par
enum_popcount_byte[i] == p->rows[row].
Remarque
On peut réduire les branchements en précalculant
les tableaux de placements pour chaque nombre
de murs (c'est ce que font les tableaux enum_byte et enum_byte_idx du
corrigé complet).
Implémentation des différentes vérifications¶
Toutes les fonctions test_... ci-dessous renvoient true lorsqu'elles
détectent un problème, c'est-à-dire lorsque le plateau doit être rejeté :
c'est la convention utilisée par la fonction solve du fichier fourni
(if (test_...(p, b)) return;).
Tests pour les colonnes¶
Il n'est pas nécessaire de tester si les lignes ont le bon nombre de murs, car on a restreint le backtracking pour l'assurer.
Question 15. Déterminer un masque correspondant à la première colonne.
En déduire, à l'aide de décalages, une fonction de signature
uint64_t mask_column(int i)
renvoyant un masque correspondant à la colonne i.
Corrigé
La première colonne est formée des cases \(0, 8, 16, \dots, 56\), soit un
bit à 1 dans chaque octet : 0x0101010101010101.
uint64_t mask_column(int i)
{
return (uint64_t)0x0101010101010101 << i;
}
Question 16. En déduire des fonctions de signature
bool test_columns_overload(problem *p, board b);
bool test_columns_underload(problem *p, board b);
testant respectivement si une colonne a trop ou pas assez de murs dans le plateau.
Corrigé
bool test_columns_overload(problem *p, board b)
{
for(int col = 0; col < 8; col++)
if (popcount(b & mask_column(col)) > p->columns[col])
return true;
return false;
}
bool test_columns_underload(problem *p, board b)
{
for(int col = 0; col < 8; col++)
if (popcount(b & mask_column(col)) < p->columns[col])
return true;
return false;
}
Impasses¶
Question 17. Écrire une fonction de signature
bool empty(problem *p, board b, int pos);
indiquant s'il y a une case libre dans le plateau
b à la position pos.
Attention, une case contenant un monstre ou un trésor n'est pas libre.
Corrigé
bool empty(problem *p, board b, int pos)
{
board fb = b | p->monsters | p->treasures;
return (fb & bit(pos)) == 0;
}
Question 18. Écrire des fonctions de signature
bool treasure(problem *p, int pos);
bool monster(problem *p, int pos);
déterminant respectivement s'il y a un trésor
ou un monstre à la position pos.
Corrigé
bool treasure(problem *p, int pos)
{
return p->treasures & bit(pos);
}
bool monster(problem *p, int pos)
{
return p->monsters & bit(pos);
}
Question 19. Écrire une fonction de signature
uint64_t neighbours(int pos);
qui renvoie le masque correspondant aux cases voisines
de la position pos. Ce masque contiendra ainsi de 2
à 4 bits à 1 selon les positions (2 aux coins,
3 sur les bords stricts et 4 à l'intérieur du plateau).
Corrigé
uint64_t neighbours(int pos)
{
uint64_t mask = 0;
if (pos % 8 != 0)
mask |= bit(pos - 1);
if (pos % 8 != 7)
mask |= bit(pos + 1);
if (pos > 7)
mask |= bit(pos - 8);
if (pos < 56)
mask |= bit(pos + 8);
return mask;
}
Question 20. En déduire une fonction de signature
int count_non_wall(problem *p, board b, int pos);
qui compte le nombre de cases qui ne sont
pas des murs dans le voisinage
de pos.
On pensera bien à prendre en compte la négation du plateau pour ne pas avoir besoin de faire de cas selon qu'on soit à l'intérieur ou sur un bord.
Corrigé
int count_non_wall(problem *p, board b, int pos)
{
uint64_t mask = neighbours(pos);
return popcount(~b & mask);
}
Maintenant qu'on peut compter le degré d'une position dans le graphe, on peut réaliser les tests présentés plus haut.
Question 21. Écrire une fonction de signature
bool test_deadends(problem *p, board b);
qui renvoie true si, dans le plateau b, un monstre n'est pas dans une
impasse ou une case libre est une impasse.
Corrigé
bool test_deadends(problem *p, board b)
{
for(int i = 0; i < 64; i++)
{
// Empty cell must not be a dead-end
if (empty(p,b,i) && count_non_wall(p, b, i) <= 1)
return true;
// Monsters must be a dead-end
if (monster(p,i) && count_non_wall(p, b, i) != 1)
return true;
}
return false;
}
Question 22. Écrire une fonction de signature
bool test_no_deadend_upto_row(problem *p, board b, int row);
qui renvoie true si une case libre est dans une impasse
dans les rangées d'indice < row.
Corrigé
Les cases de la rangée row ne sont pas encore remplies et comptent comme
libres : une case libre des rangées précédentes qui est déjà une impasse le
restera.
bool test_no_deadend_upto_row(problem *p, board b, int row)
{
for(int i = 0; i < 8*row; i++)
{
if (empty(p,b,i) && count_non_wall(p, b, i) <= 1)
return true;
}
return false;
}
Question 23. Écrire une fonction de signature
bool test_trapped_monster(problem *p, board b);
qui renvoie true si un monstre est piégé par des murs.
Corrigé
bool test_trapped_monster(problem *p, board b)
{
for(int i = 0; i < 64; i++)
if (monster(p,i) && count_non_wall(p, b, i) == 0)
return true;
return false;
}
Carrés libres¶
Question 24. Déterminer un masque correspondant à un carré de quatre cases commençant à la position 0.
Corrigé
Les cases 0, 1, 8 et 9, soit 0x0303.
Question 25. En déduire une fonction de signature
bool test_empty_squares(problem *p, board b);
qui renvoie true s'il y a un carré de quatre cases libres
dans le plateau b.
Corrigé
On décale le masque sur les 7 premières colonnes de chacune des 7
premières lignes ; en fin de ligne, on décale une fois de plus pour passer
de la colonne 6 à la colonne 0 de la ligne suivante. Le plateau b reçu
contient aussi les monstres et les salles au trésor remplies.
bool test_empty_squares(problem *p, board b)
{
uint64_t mask_square = 0x0303;
for(int i = 0; i < 7; i++)
{
for(int j = 0; j < 7; j++)
{
if((b & mask_square) == 0)
return true;
mask_square *= 2;
}
mask_square *= 2;
}
return false;
}
Remarque
À partir d'ici, vous pouvez résoudre tous les problèmes ne comportant pas de trésors.
Salles au trésor¶
Pour chaque trésor, on va appliquer la méthode suivante :
- à l'aide d'un masque correspondant à un carré 3x3, identifier une possible salle au trésor autour du trésor (pas la peine de toutes les chercher, il ne peut y en avoir qu'une)
- à l'aide d'un masque correspondant à la bordure de la salle, en prenant garde au fait qu'elle n'est pas nécessairement à l'intérieur du plateau, déterminer l'unique ouverture de la salle
- remplir la salle au trésor de murs
Si jamais on n'arrive pas à trouver une salle valide, on sait que le plateau est insoluble.
Question 26. Écrire une fonction de signature
bool test_treasure_rooms(problem *p, board *b);
qui renvoie true si un trésor n'est pas dans une salle valide, et sinon
remplit toutes les salles par des murs à l'aide du pointeur b.
Corrigé
Le plateau *b contient les murs et les monstres, ce qui exclut les salles
contenant un monstre. Le carré 3x3 de coin supérieur gauche \((s_x, s_y)\)
correspond au masque 0x070707 décalé de \(s_x + 8 s_y\), à condition que
\(s_x, s_y \le 5\).
bool test_treasure_rooms(problem *p, board *b)
{
for(int i = 0; i < 64; i++)
{
if(treasure(p,i))
{
int x = i % 8;
int y = i / 8;
int minx = x - 2;
if (minx < 0) minx = 0;
int miny = y - 2;
if (miny < 0) miny = 0;
// the room must fit in the board: top-left corner (sx, sy)
// with sx, sy <= 5, otherwise the shift wraps to the next row
int maxx = x < 5 ? x : 5;
int maxy = y < 5 ? y : 5;
// starting point of the treasure room
// xxx
// xTx
// xxx
bool found = false;
uint64_t room = 0;
int sx, sy;
for(sy = miny; sy <= maxy; sy++)
{
for(sx = minx; sx <= maxx; sx++)
{
room = (uint64_t)0x070707 << (sx + 8*sy);
if (popcount(~(*b) & room) == 9)
{
found = true;
break;
}
}
if(found) break;
}
if (!found) return true;
uint64_t border = 0;
if (sy > 0)
border |= (uint64_t)0x07 << (sx+8*(sy-1));
if (sy+2 < 7)
border |= (uint64_t)0x07 << (sx+8*(sy+3));
if (sx > 0)
border |= (uint64_t)0x010101 << (sx-1+8*sy);
if (sx+2 < 7)
border |= (uint64_t)0x010101 << (sx+3+8*sy);
int exit = popcount(~(*b) & border);
if (exit != 1)
return true;
*b = *b | room;
}
}
return false;
}
Remarque
Vous pouvez maintenant résoudre tous les problèmes.
En tenant compte de toutes les optimisations dans les remarques et en compilant
en -O3, il est possible de résoudre les
64 problèmes de Last Call BBS en moins de 500 ms !
Exemples¶
Les exemples de problèmes présents dans le fichier fourni sont reproduits ici dans le même ordre.
Solutions des 9 exemples
Solutions obtenues avec le programme ci-dessous (# : mur, M : monstre,
T : trésor), dans le même ordre :
Ex 1 Ex 2 Ex 3 Ex 4 Ex 5
#####M## #####... M######M ...#...# M.......
...#..## #..T#T.. ........ M#.#.T.# #######.
.T.#.### #...#... .#.##.#. ##.#...# #M#T..#.
.......# #.....## M#...... .....### #.#...#.
######.# #####.#M ##.##.#M .####### #.#...#.
M......# ........ #...#..# .......M #.#.###.
##.#.### .######. #.T.##.. .#.#.#.# #...#...
##M#...M .M#M.... #...###M .......M ###...##
Ex 6 Ex 7 Ex 8 Ex 9
#####M.# ...M#... #M#...M# #...###M
#...##.M .#.##.#. #.#.#### ..#.....
#.T.#M.# M#....#. .......M .#M#.#.#
#...##.M ##.####M .#.###.# .....#.#
##.##M.# ......## .#.#M#.# ##.###.#
...###.M .##.#... .......M #...#...
.###...# .##.#..T #.#.#### #...#.#.
.....### ....#... #M#...M# #T..#...
Solution¶
Corrigé complet
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <inttypes.h>
typedef uint64_t board;
typedef bool map[64];
typedef char constraint[8];
struct problem {
board monsters;
board treasures;
constraint rows;
constraint columns;
};
typedef struct problem problem;
problem p1 = {
.monsters = 0x8400010000000020,
.treasures = 0x20000,
.rows = { 7,3,4,1,7,1,6,3 },
.columns = { 4,4,2,6,2,3,4,7 }
};
problem p2 = {
.monsters = 0xa00008000000000,
.treasures = 0x2800,
.rows = { 5,2,2,3,6,0,6,1 },
.columns = { 5,3,4,3,5,1,3,1 }
};
problem p3 = {
.monsters = 0x8000008001000081,
.treasures = 0x4000000000000,
.rows = { 6,0,4,1,5,3,3,4 },
.columns = { 4,4,1,3,6,3,4,1 }
};
problem p4 = {
.monsters = 0x8000800000000100,
.treasures = 0x2000,
.rows = { 2,3,4,3,7,0,4,0 },
.columns = { 1,4,1,5,1,3,2,6 }
};
problem p5 = {
.monsters = 0x20001,
.treasures = 0x80000,
.rows = { 0,7,3,3,3,5,2,5 },
.columns = { 7,2,6,1,3,2,6,1 }
};
problem p6 = {
.monsters = 0x802080208020,
.treasures = 0x40000,
.rows = { 6,3,3,3,5,3,4,3 },
.columns = { 5,3,2,4,6,4,1,5 }
};
problem p7 = {
.monsters = 0x80010008,
.treasures = 0x80000000000000,
.rows = { 1,4,2,6,2,3,3,1 },
.columns = { 1,5,2,2,6,1,4,1 }
};
problem p8 = {
.monsters = 0x4200801000800042,
.treasures = 0x0,
.rows = { 3,6,0,5,4,0,6,3 },
.columns = { 4,2,4,2,3,4,2,6 }
};
problem p9 = {
.monsters = 0x40080,
.treasures = 0x200000000000000,
.rows = { 4,1,4,2,6,2,3,2 },
.columns = { 5,2,1,2,5,4,2,3 }
};
uint64_t mask_column(int i)
{
return (uint64_t)0x0101010101010101 << i;
}
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;
}
void board_to_map(board b, map m)
{
for(int i = 0; i < 64; i++)
{
m[i] = b % 2 == 1;
b = b / 2;
}
}
int popcount_slow(uint64_t v)
{
int s = 0;
while(v != 0)
{
if (v % 2 == 1)
s = s+1;
v = v/2;
}
return s;
}
int popcount(uint64_t v)
{
uint64_t mask_1 = 0x5555555555555555;
uint64_t mask_2 = 0x3333333333333333;
uint64_t mask_3 = 0x0f0f0f0f0f0f0f0f;
uint64_t mask_4 = 0x00ff00ff00ff00ff;
uint64_t mask_5 = 0x0000ffff0000ffff;
uint64_t mask_6 = 0x00000000ffffffff;
v = (v & mask_1) + ((v & (mask_1 << 1)) >> 1);
v = (v & mask_2) + ((v & (mask_2 << 2)) >> 2);
v = (v & mask_3) + ((v & (mask_3 << 4)) >> 4);
v = (v & mask_4) + ((v & (mask_4 << 8)) >> 8);
v = (v & mask_5) + ((v & (mask_5 << 16)) >> 16);
v = (v & mask_6) + ((v & (mask_6 << 32)) >> 32);
return v;
}
#define popcount __builtin_popcountll
int enum_popcount_byte[256];
void print_board(problem *p, board b)
{
for (int i = 0; i < 64; i++)
{
if (((b >> i) & 1) != 0)
putchar('#');
else if (((p->monsters >> i) & 1) != 0)
putchar('M');
else if (((p->treasures >> i) & 1) != 0)
putchar('T');
else putchar('.');
if (i % 8 == 7) printf("\n");
}
}
uint64_t bit(int pos)
{
return (uint64_t) 1 << pos;
}
uint64_t neighbours(int pos)
{
uint64_t mask = 0;
if (pos % 8 != 0)
mask |= bit(pos - 1);
if (pos % 8 != 7)
mask |= bit(pos + 1);
if (pos > 7)
mask |= bit(pos - 8);
if (pos < 56)
mask |= bit(pos + 8);
return mask;
}
int count_non_wall(problem *p, board b, int pos)
{
uint64_t mask = neighbours(pos);
return popcount(~b & mask);
}
bool empty(problem *p, board b, int pos)
{
board fb = b | p->monsters | p->treasures;
return (fb & bit(pos)) == 0;
}
bool treasure(problem *p, int pos)
{
return p->treasures & bit(pos);
}
bool monster(problem *p, int pos)
{
return p->monsters & bit(pos);
}
// Optional: precompute wall test
int enum_byte[] = { 0, 1, 2, 4, 8, 16, 32, 64, 128, 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36,
40, 48, 65, 66, 68, 72, 80, 96, 129, 130, 132, 136, 144, 160,
192, 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42,
44, 49, 50, 52, 56, 67, 69, 70, 73, 74, 76, 81, 82, 84, 88, 97,
98, 100, 104, 112, 131, 133, 134, 137, 138, 140, 145, 146, 148,
152, 161, 162, 164, 168, 176, 193, 194, 196, 200, 208, 224, 15,
23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 71, 75,
77, 78, 83, 85, 86, 89, 90, 92, 99, 101, 102, 105, 106, 108, 113,
114, 116, 120, 135, 139, 141, 142, 147, 149, 150, 153, 154, 156,
163, 165, 166, 169, 170, 172, 177, 178, 180, 184, 195, 197, 198,
201, 202, 204, 209, 210, 212, 216, 225, 226, 228, 232, 240, 31,
47, 55, 59, 61, 62, 79, 87, 91, 93, 94, 103, 107, 109, 110, 115,
117, 118, 121, 122, 124, 143, 151, 155, 157, 158, 167, 171, 173,
174, 179, 181, 182, 185, 186, 188, 199, 203, 205, 206, 211, 213,
214, 217, 218, 220, 227, 229, 230, 233, 234, 236, 241, 242, 244,
248, 63, 95, 111, 119, 123, 125, 126, 159, 175, 183, 187, 189,
190, 207, 215, 219, 221, 222, 231, 235, 237, 238, 243, 245, 246,
249, 250, 252, 127, 191, 223, 239, 247, 251, 253, 254, 255 };
int enum_byte_idx[] = { 0, 1, 9, 37, 93, 163, 219, 247, 255, 256 };
bool test_columns_overload(problem *p, board b)
{
for(int col = 0; col < 8; col++)
if (popcount(b & mask_column(col)) > p->columns[col])
return true;
return false;
}
bool test_columns_underload(problem *p, board b)
{
for(int col = 0; col < 8; col++)
if (popcount(b & mask_column(col)) < p->columns[col])
return true;
return false;
}
bool test_no_deadend_upto_row(problem *p, board b, int row)
{
for(int i = 0; i < 8*row; i++)
{
if (empty(p,b,i) && count_non_wall(p, b, i) <= 1)
return true;
}
return false;
}
bool test_trapped_monster(problem *p, board b)
{
for(int i = 0; i < 64; i++)
if (monster(p,i) && count_non_wall(p, b, i) == 0)
return true;
return false;
}
bool test_deadends(problem *p, board b)
{
for(int i = 0; i < 64; i++)
{
// Empty cell must not be a dead-end
if (empty(p,b,i) && count_non_wall(p, b, i) <= 1)
return true;
// Monsters must be a dead-end
if (monster(p,i) && count_non_wall(p, b, i) != 1)
return true;
}
return false;
}
bool test_treasure_rooms(problem *p, board *b)
{
for(int i = 0; i < 64; i++)
{
if(treasure(p,i))
{
int x = i % 8;
int y = i / 8;
int minx = x - 2;
if (minx < 0) minx = 0;
int miny = y - 2;
if (miny < 0) miny = 0;
// the room must fit in the board: top-left corner (sx, sy)
// with sx, sy <= 5, otherwise the shift wraps to the next row
int maxx = x < 5 ? x : 5;
int maxy = y < 5 ? y : 5;
// starting point of the treasure room
// xxx
// xTx
// xxx
bool found = false;
uint64_t room = 0;
int sx, sy;
for(sy = miny; sy <= maxy; sy++)
{
for(sx = minx; sx <= maxx; sx++)
{
room = (uint64_t)0x070707 << (sx + 8*sy);
if (popcount(~(*b) & room) == 9)
{
found = true;
break;
}
}
if(found) break;
}
if (!found) return true;
uint64_t border = 0;
if (sy > 0)
border |= (uint64_t)0x07 << (sx+8*(sy-1));
if (sy+2 < 7)
border |= (uint64_t)0x07 << (sx+8*(sy+3));
if (sx > 0)
border |= (uint64_t)0x010101 << (sx-1+8*sy);
if (sx+2 < 7)
border |= (uint64_t)0x010101 << (sx+3+8*sy);
int exit = popcount(~(*b) & border);
if (exit != 1)
return true;
*b = *b | room;
}
}
return false;
}
bool test_empty_squares(problem *p, board b)
{
uint64_t mask_square = 0x0303;
for(int i = 0; i < 7; i++)
{
for(int j = 0; j < 7; j++)
{
if((b & mask_square) == 0)
return true;
mask_square *= 2;
}
mask_square *= 2;
}
return false;
}
void solve(problem *p, int row, board b)
{
// Unsolvable from this board
if (test_columns_overload(p, b))
return;
if (test_no_deadend_upto_row(p, b, row))
return;
if (test_trapped_monster(p, b))
return;
// Board is filled
if(row == 8)
{
// Validate columns count
if (test_columns_underload(p, b))
return;
// Monsters are exactly the dead-ends
if (test_deadends(p, b))
return;
// Full board with monsters
board fb = b | p->monsters;
if (test_treasure_rooms(p, &fb))
return;
// Every treasure room is now filled in fb
if (test_empty_squares(p, fb))
return;
printf("Solution %" PRIx64 "\n", b);
print_board(p, b);
return;
}
/*
// Slower because of branching
for(int i = 0; i < 256; i++)
if (enum_popcount_byte[i] == p->rows[row])
{
uint64_t move = (uint64_t)i << (8*row);
// ensure there's no overlap with walls/monsters/treasures
if ((move & (p->monsters | p->treasures)) != 0)
continue;
solve(p, row+1, b + move);
}
*/
int tgt = p->rows[row];
for(int v = enum_byte_idx[tgt]; v < enum_byte_idx[tgt+1]; v++)
{
uint64_t move = (uint64_t)enum_byte[v] << (8*row);
// ensure there's no overlap with walls/monsters/treasures
if ((move & (p->monsters | p->treasures)) != 0)
continue;
solve(p, row+1, b + move);
}
}
int main(void)
{
/*
map monsters = {
0, 0, 1, 0, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 1, 0, 0,
};
*/
map monsters = { [5] = 1 };
problem test = {
.rows = { 6, 2, 5, 3, 2, 5, 2, 6 },
.columns = { 6, 2, 4, 3, 4, 4, 2, 6 }
};
test.monsters = map_to_board(monsters);
for(int i = 0; i < 256; i++)
enum_popcount_byte[i] = popcount(i);
problem *problems[] = {
&p1, &p2, &p3,
&p4, &p5, &p6,
&p7, &p8, &p9
};
for (int i = 0; i < 9; i++)
{
printf("Solving problem %d\n", i);
print_board(problems[i], 0);
solve(problems[i], 0, 0);
}
}