Pavage de Jardin¶
Le problème¶
Dans un jardin, si on fait trop d’allées, on perd de la surface de culture. Si on n’en fait pas suffisamment, il y a des points non accessibles depuis les allées, ce qui oblige à marcher dans le jardin et à compacter le sol. Comment tracer les allées intelligemment ?
La modélisation¶
On coupe un jardin de 10mx10m en carrés de 1/3m et on affecte a chaque carré le statut d’allée ou de surface cultivable. Chaque point du jardin doit être a au plus 50 cm du bord d’une allée. L’allée doit former un ensemble connexe et être accessible depuis le bord du jardin ( deux carrés en diagonale ou à côté l’un de l’autre forment un ensemble connexe).
Ce que vous devez faire¶
Essayer de trouver une solution à la main en faisant quelques exemples
Ecrire une fonction qui vérifie si une proposition d’allées vérifie les contraintes ci-dessus.
Chercher des solutions informatiques si possibles meilleures que celles obtenues par tatonnement à la main.
Faire une representation graphique des solutions.