Logic Puzzle#11636
You recently bought a magazine full of logic puzzles at a kiosk during a trip. After solving a few, you begin to wonder if some can be solved algorithmically. One puzzle is called "Mosaic", and it resembles the classic Minesweeper video game:
You are given a two-dimensional grid consisting of rows and columns of initially white cells. Your task is to color some of these cells black. You are also given a grid of clue numbers, which extends one cell beyond each border of the puzzle grid. The number in a cell specifies exactly how many of the 3 \times 3 block of cells centered at this cell must be colored black. You may not color any cells outside the original grid.
The first line contains two integers and (1 \le h, w \le 100)—the height and width of the puzzle grid.
Each of the next h+2 lines contains w+2 integers c_1, \ldots, c_{w+2} (0 \le c_i \le 9), the clues.
If the clues are inconsistent, output impossible. Otherwise, output lines, each containing characters—a possible solution. Use X for black cells and . for white cells. If there are multiple solutions, output any of them.
Example 1
Example 2