Problem G
Star Battles I
A Star Battle (of the $2$-star variety), also known as “Two Not Touch” as published by The New York Times, is a solitary star-placement puzzle played on a $10\times 10$ grid. The grid is divided into exactly ten $4$-connected regions, and the objective is to place exactly $20$ stars in the grid, each in its own cell, such that following conditions are satisfied:
-
Every row, column, and region of the grid contains exactly two stars.
-
No two stars are in adjacent cells, i.e. cells next to each other horizontally, vertically, or diagonally.
Below is an example of a Star Battle puzzle,1 where regions are delimited by bold lines. The unique solution to this puzzle is shown on the right.
![\includegraphics[width=0.8\textwidth ]{star_battle_sample.png}](/problems/starbattles1/file/statement/en/img-0001.png)
Given a description of a Star Battle puzzle and a candidate solution, your task for this problem is to write a program that will determine whether or not the candidate is indeed a valid solution to the puzzle. The input to your program is guaranteed to be a valid Star Battle puzzle with a unique solution.
Input
The first $10$ lines of input contain a description of the Star Battle puzzle. Every line contains exactly $10$ digits, where the digit names the region to which its cell belongs. There will be exactly $10$ contiguous, $4$-connected (i.e. left, right, top, bottom, but not diagonal) regions in the puzzle.
The next $10$ lines of input contain a description of the candidate solution. Every line contains exactly $10$ characters, each a ‘.’ to indicate an empty cell or a ‘*’ to indicate placement of a star.
Output
If the candidate solution is consistent with all the Star Battle rules for the provided puzzle, output the word “valid” on a single line. Otherwise, output “invalid”.
| Sample Input 1 | Sample Output 1 |
|---|---|
0001111223 0001221223 0001222223 0000224433 5544444433 5555466663 5575566663 8877666663 8997777663 8999976666 ......*.*. .*.*...... .....*...* ...*...*.. .*...*.... .......*.* ..*.*..... *.......*. ..*...*... *...*..... |
valid |
| Sample Input 2 | Sample Output 2 |
|---|---|
0000001111 0022221111 3322222111 3322222141 3355511144 3555516664 3771116664 7788811644 7888919944 7999999444 ......*.*. .*.*...... .....*...* ...*...*.. .*...*.... .......*.* ..*.*..... *.......*. ..*...*... *...*..... |
invalid |
Footnotes
- Star Battle puzzle images and test suite provided by krazydad.com, used with permission from author.
