A kerekasztal lovagjai

A kerekasztal lovagjai jól ismert lovagok Artúr király udvarában. Ahhoz, hogy egy lovag bekerülhessen a kerekasztal lovagjai közé, arra érdemesnek kellett bizonyulnia, és fel kellett esküdnie a lovagság törvényeire. A lovagság törvényei az alábbiak:

• Ne bántalmazz vagy ölj meg senkit.
• Ne áruld el az országodat vagy királyodat.
• Ne légy kegyetlen: irgalmazz annak, ki kegyelemért könyörög.
• Mindig segítsd az úrihölgyeket, nemesasszonyokat és az özvegyeket.
• Sose bántalmazz úrihölgyet, nemesasszonyt vagy özvegyet.
• Ne bocsátkozz igazságtalan vitákba a szerelemért vagy világi javakért.

Amikor a kerekasztal lovagjai gyűlést tartanak, egy kör alakú asztalhoz ülnek. Minden lovag kap egy sorszámot aszerint, hogy hányadikként került be a társaságba. Bármely alkalommal legfeljebb 16 lovag lehet jelen. A hagyomány szerint amikor összeülnek, legalább két lovagnak kell megjelennie, és páros számú lovagnak kell eljönnie, hogy megkezdhessék az ülést. Továbbá abban is hisznek, hogy bármely két szomszédos lovag sorszámai összegének prímszámnak kell lennie. Írj egy programot, amely megkeresi az összes lehetséges üléssorrendet, amely eleget tesz a hagyománynak!

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. Minden teszteset egyetlen sorból áll, amely n-et, az ülésre érkező lovagok számát tartalmazza (0 < n ≤ 16). n mindig páros szám.

A kimenet specifikációja

Minden tesztesetre a kimenetre kell írni az összes lehetséges üléssorrendet, amely eleget tesz a fent ismertetett szabálynak. A kimenet formátumát lásd a példa kimenetben! Minden sor az asztal körül ülő lovagok sorszámainak egy sorozatát tartalmazza, az 1-es számú lovaggal kezdve, az óramutató járásával megegyező és azzal ellentétes irányban is haladva. Az üléssorrendeket lexikografikus sorrendben kell megadni. Két egymást követő tesztesethez tartozó kimenetet egy-egy üres sorral kell elválasztani egymástól.

Példa bemenet

1. 6
2. 8

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. Case 1:
2. 1 4 3 2 5 6
3. 1 6 5 2 3 4
5. Case 2:
6. 1 2 3 8 5 6 7 4
7. 1 2 5 8 3 4 7 6
8. 1 4 7 6 5 8 3 2
9. 1 6 7 4 3 8 5 2

letöltés szöveges állományként