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.

\includegraphics[width=0.8\textwidth ]{star_battle_sample.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

  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
Author
Sonny Chan
Source Calgary Collegiate Programming Contest 2021
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in