Cowboy Checkers
Time limit1sMemory limit1024 MB
Given a Nine Men's Morris board, decide whether White has a single move that creates a double mill.
- Level
Medium4 of 10
- Topics
- Simulation, Brute force, Implementation
- Solved
- No attempts yet
Problem
Figure 1: Left: the board at the start of the game. Right: a position that is a win for White. Source: Wikimedia Commons
Theta plays Cowboy Checkers, also known as "Nine Men's Morris." This strategy board game dates back at least to the Roman Empire. Two players play on a grid with 24 intersections, or points. The left side of Figure 1 shows the starting layout. Each player has nine pieces, either white or black. In the first phase, the players take turns placing pieces on unoccupied intersections. After all pieces are placed, the players take turns moving pieces. A piece can move along the lines of the board from its intersection (or corner) to any connected open intersection (or corner).
The goal is to take the opponent's pieces. You do this by forming a "mill," which is three pieces lined up horizontally or vertically. Figure 1 shows two mills. White has a mill on e3, e4, and e5, and black has a mill on f2, f4, and f6.
Each time a player forms a mill, that player can take one piece from the opponent. A "double mill" is a position where the player to move can shift one piece out of one mill so that it closes another mill. On the next move, the player moves the piece back, which closes the first mill again and reopens the second. Such a position almost always wins. In Figure 1, White has a double mill. Moving e3 to d3 closes a mill on d1, d2, and d3, and at the same time opens the mill on e4 and e5.
Theta is fairly good at spotting double mills. Can you write a program that does the same?
Input
The input is a single test case of 7 lines with 7 characters each. B and W are black and white pieces. A . is an open intersection or corner, except at the center of the board, where it has no meaning. The characters | and - are connector lines, and no piece can be on them. Every input is a valid position in terms of which points may hold pieces, as shown on the left side of Figure 1. The board may hold up to nine black pieces and up to nine white pieces.
Output
If White has at least one double mill, print double mill. Otherwise, print no double mill.