Hide

# 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.

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

1. Star Battle puzzle images and test suite provided by krazydad.com, used with permission from author.
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 2.7easy
Statistics Show