Problem H
Star Battles II
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/starbattles2/file/statement/en/img-0001.png)
Your task for this problem is to write a program to solve a given Star Battle puzzle. The input to your program is guaranteed to be a valid Star Battle puzzle with a unique solution.
Input
The input is a description of the Star Battle puzzle as $10$ lines of text. 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.
Output
Output your solution to the Star Battle puzzle as exactly $10$ lines of text. Every line should contain exactly $10$ characters, each a ‘.’ to indicate an empty cell or a ‘*’ to indicate placement of a star.
| Sample Input 1 | Sample Output 1 |
|---|---|
0001111223 0001221223 0001222223 0000224433 5544444433 5555466663 5575566663 8877666663 8997777663 8999976666 |
......*.*. .*.*...... .....*...* ...*...*.. .*...*.... .......*.* ..*.*..... *.......*. ..*...*... *...*..... |
| Sample Input 2 | Sample Output 2 |
|---|---|
0000001111 0022221111 3322222111 3322222141 3355511144 3555516664 3771116664 7788811644 7888919944 7999999444 |
...*.*.... .......*.* .*.*...... ......*.*. *.*....... ....*...*. .*....*... ....*....* ..*....*.. *....*.... |
Footnotes
- Star Battle puzzle images and test suite provided by krazydad.com, used with permission from author.
