Diagonals

Time limit8sMemory limit1024 MB

Summary

Fill an n by n grid with diagonals so that given intersection counts match and no cycle of diagonals forms.

Level: Medium6 of 10
Topics: Backtracking, Graph, Union-find, Brute force
Solved: No attempts yet

Problem

Diagonals is a pencil puzzle played on a square grid. The player must draw one diagonal line in every cell of the grid, corner to corner, either from top left to bottom right or from bottom left to top right. Two constraints apply:

Some intersections of gridlines have an integer from $0$ to $4$ inclusive written on them, which is the exact number of diagonals that must touch that point.
No set of diagonals may form a loop of any size or shape.

The following is a $5\!\times\!5$ example together with its unique solution:

Given the numbers at the intersections of a grid, solve the puzzle.

Input

The first line of input contains an integer $n$ ( $1 \le n \le 8$ ), the size of the grid.

Each of the next $n+1$ lines contains a string $s$ ( $|s|=n+1$ , $s \in \{\texttt{0},\texttt{1},\texttt{2},\texttt{3},\texttt{4},\texttt{+}\}^\ast$ ). These are the intersections of the grid, and '+' means there is no number at that intersection.

The input data is such that the puzzle has exactly one solution.

Output

Output exactly $n$ lines, each with exactly $n$ characters, representing the solution to the puzzle. Each character must be either '/' or '\'.

Sample 1 corresponds to the example in the problem description.

Examples3

Example 1

Input

5
+1+2++
1++11+
+3+2++
02+++1
++3+1+
+1+++1

Expected output

\\/\\
\/\\/
\\\\\
////\
//\\\

Example 2
Input
```
3
++++
+1+1
+31+
+0+0
```
Expected output
```
/\/
///
/\/
```

Example 3

Input

4
+++++
+3++2
++3++
+3+3+
++2+0

Expected output

\//\
\\//
\\\/
/\//