Hide

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}

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

  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