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.