F — Nine Knights

In the game of chess, knights are unique due to their “L-shaped” movement. A knight can move, as shown in Figure 1, by either moving two squares sideways and one square up or down, or moving one square sideways and two squares up or down.

Figure 1: The highlighted squares show all possible moves for a knight.

In the Nine Knights puzzle, exactly nine knights must be positioned on a 5 × 5 board so that no knight can attack another knight with a single move. The configuration shown in Figure 2 is an invalid solution, because two of the knights can attack each other, while the configuration shown in Figure 3 is a valid solution.

Figure 2: Invalid solution.

Figure 3: Valid solution.

Given the description of a game configuration, your job is to determine whether or not it represents a valid solution of the Nine Knights puzzle.

Input Specification

The input will consist of 5 lines, each having 5 characters. All characters will be either 'k', indicating a knight, or '.', indicating an empty square on the board.