F — Kilenc huszár

A sakkban a huszár különleges figura az „L alakú” lépése miatt. Ahogy az 1. ábrán látható, egy huszár vagy két mezőt lép oldalra és egyet felfelé vagy lefelé, vagy egy mezőt lép oldalra és kettőt felfelé vagy lefelé.

1. ábra: A kiemelt mezők mutatják a huszár lehetséges lépéseit.

A kilenc huszár problémában pontosan kilenc huszárt kell elhelyezni egy 5 × 5-ös méretű táblán úgy, hogy egy huszár se tudjon egy lépésben támadni egy másikat. A 2. ábrán látható állás nem érvényes megoldás, mert két huszár meg tudja támadni egymást, míg a 3. ábrán látható állás érvényes megoldása a problémának.

2. ábra: Érvénytelen megoldás.

3. ábra: Érvényes megoldás.

A feladatod annak eldöntése, hogy egy adott játékállás érvényes megoldása-e a kilenc huszár problémának.

A bemenet specifikációja

A bemenet 5 sorból áll, amelyek mindegyikében 5 karakter szerepel. A karakterek mindegyike vagy egy 'k' betű, amely egy huszárt jelöl, vagy egy '.', amely a tábla egy üres mezőjét jelöli.

A kimenet specifikációja

A kimenetre egyetlen sort kell kiírni, amely a „valid” szót tartalmazza, ha a megadott sakktábla érvényes megoldása a kilenc huszár problémának. Egyébként pedig az “invalid” szót kell kiírni.