programmingChallenges/shikaku/README.md

Générateur de grilles de Shikaku

Introduction

Nous sommes en 2025. La directrice de la Clinique du Séquoia, Aimée Surprise, doit faire face à l’ennui de ses seniors. Les abonnements aux différentes revues de jeux d’esprit plombent le budget de la clinique et ne parviennent pas à satisfaire une demande sans cesse croissante.

Aimée Surprise a donc décidé de faire produire en masse des grilles de Shikaku.

Le Shikaku

Le Shikaku est un casse-tête logique venant du Japon. Il se joue sur une grille de W×H cases.

Le but est de réaliser un générateur de grilles de Shikaku.

Format du fichier produit

Le générateur produit un fichier dont la structure est la suivante :

• première ligne : définition de l’aire de jeu

  • 'T' : magic char
  • W : largeur de l’aire de jeu
  • H : hauteur de l’aire de jeu

• lignes suivantes : une ligne par aire

  • S : superficie du bloc ( 2 <= S < W×H )
  • X : abscisse du bloc ( 0 <= X < W )
  • Y : ordonnée du bloc ( 0 <= Y < H )

Notes :

• La grille est divisée en plusieurs rectangles
• la grille doit être entièrement recouverte par les rectangles et deux rectangles ne peuvent pas se chevaucher (Somme des S = W×H)
• des nombres apparaissent sur la grille : chaque rectangle doit en contenir un et un seul qui indique l’aire du rectangle qui le contient
• 2 < W < 200, 2 < H < 200
• 2 <= Nombre de blocs <= W×H/3

Voici un exemple de fichier :

T 8 4    -> une grille de 8×4
6 7 0    -> un bloc de 6 aux coordonnées (7,0)
6 5 3    -> un bloc de 6 aux coordonnées (5,3)
12 2 1   -> un bloc de 12 aux coordonnées (2,1)
4 4 1    -> un bloc de 4 aux coordonnées (4,1)
4 3 3    -> un bloc de 4 aux coordonnées (3,3)

Cet exemple décrit la grille suivante :

+---+---+---+---+---+---+---+---+
|                            6  |
+   +   +   +   +   +   +   +   +
|        12      4              |
+   +   +   +   +   +   +   +   +
|                               |
+   +   +   +   +   +   +   +   +
|            4       6          |
+---+---+---+---+---+---+---+---+

La solution de cette grille est la suivante :

+---+---+---+---+---+---+---+---+
|               |   |        6  |
+   +   +   +   +   +   +   +   +
|        12     |4  |           |
+   +   +   +   +   +---+---+---+ -.
|               |   |           |  |
+---+---+---+---+   +   +   +   +  |
|            4  |   |6          |  |
+---+---+---+---+---+---+---+---+  +-- bloc
                    .              |
                    `--------------+

Challenge

Écrire un programme générant des grilles de Shikaku en laissant l’utilisateur spécifier :

• la largeur de la grille voulue
• la hauteur de la grille voulue
• le nombre de blocs à créer sur la grille

Exemple d’appel du programme pour générer une grille de 8×4 contenant 5 blocs :

shikakugen 8 4 5

Bonus

Le premier challenge correspond au niveau 1.

Niveau 2

Écrire une version capable d’afficher une version humaine de la grille et du problème comme ci-dessous:

+---+---+---+---+---+
|           |       |
+---+---+---+---+---+
|   |       |       |
+   +   +   +---+---+
|   |       |       |
+---+---+---+---+---+
|       |       |   |
+   +   +   +   +   +
|       |       |   |
+---+---+---+---+---+

+---+---+---+---+---+
|    3           2  |
+   +   +   +   +   +
|2       4   2      |
+   +   +   +   +   +
|            2      |
+   +   +   +   +   +
|        4       2  |
+   +   +   +   +   +
|    4              |
+---+---+---+---+---+

Niveau 3

Écrire un solveur de grille de Shikaku dont l’entrée est le fichier

Niveau 4

Écrire un générateur de grilles qui ne soient pas uniquement des sous-divisions de rectangles.

Exemple d’une telle grille :

+---+---+---+---+
|           |   |
+---+---+---+   +
|   |       |   |
+   +   +   +   +
|   |       |   |
+   +---+---+---+
|   |           |
+---+---+---+---+

Note : cela n’est possible qu’à partir de 5 blocs !