## Introduction

Sudoku is one of the popular combinatorial and logic-based number-placement puzzles. We are mostly familiar with 9Ă—9 grid-based puzzles where each row and column and each 3Ă—3 subgrids should contain all of the numbers from 1 to 9. Here, we will see a special type of sudoku with irregular sub-regions inside the grid and the grid can be of any given nĂ—n size. Here we need to fill each column and row as well as subregions so that it contains contain all of the numbers from 1 to n.

Recommended topic about, __kth largest element in an array__, and __Euclid GCD Algorithm__

## Problem statement

You are given nĂ—n sudoku puzzle grid and region[ ][ ] matrix denoting irregular sub-regions inside the puzzle grid with characters. The same characters denote a specific sub-region.

Your task is to fill empty cells of the puzzle grid with numbers from 1 to n so that the below conditions are satisfied.

- Each row and column should contain all of the numbers from 1 to n.
- Each subregion also should contain all of the numbers from 1 to n.

Note: empty cells will be denoted by 0.

Input

```
int n= 7
sudoku[ ][ ]
= {
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 2, 0, 4, 0, 0},
{3, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 5, 0, 2},
{5, 0, 0, 0, 0, 0, 3},
{0, 0, 1, 0, 0, 0, 5},
{2, 0, 0, 0, 0, 0, 1}
}
region[ ][ ]
={
{'r', 'r', 'r', 'b', 'b', 'b', 'b'},
{'g', 'r', 'r', 'r', 'r', 'b', 'o'},
{'g', 'g', 'g', 'g', 'b', 'b', 'o'},
{'p', 'p', 'g', 'o', 'o', 'o', 'o'},
{'p', 'p', 'g', 'd', 'o', 'l', 'l'},
{'p', 'p', 'p', 'd', 'l', 'l', 'l'},
{'d', 'd', 'd', 'd', 'd', 'l', 'l'}
}
```

0 |
0 |
0 |
0 |
0 |
0 |
0 |

0 |
0 |
2 |
0 |
4 |
0 |
0 |

3 |
0 |
0 |
0 |
0 |
0 |
0 |

0 |
0 |
0 |
0 |
5 |
0 |
2 |

5 |
0 |
0 |
0 |
0 |
0 |
3 |

0 |
0 |
1 |
0 |
0 |
0 |
5 |

2 |
0 |
0 |
0 |
0 |
0 |
1 |

Output

6 |
1 |
3 |
4 |
2 |
5 |
7 |

1 |
7 |
2 |
5 |
4 |
3 |
6 |

3 |
5 |
7 |
2 |
1 |
6 |
4 |

7 |
6 |
4 |
3 |
5 |
1 |
2 |

5 |
2 |
6 |
1 |
7 |
4 |
3 |

4 |
3 |
1 |
7 |
6 |
2 |
5 |

2 |
4 |
5 |
6 |
3 |
7 |
1 |

Explanation

Letâ€™s consider an unfilled cell of the grid, say (0,0). We will try to fill it with every possible number from 1 to 7. If any number is present neither in its current row, column nor in the current subregion, we will fill the cell with that number and will go to the next cell (0,1) and repeat the same process. In this way, if at any cell the conditions are mismatched, we will backtrack and try to fill the cells with other possibilities. If all cells are filled, then the puzzle is solved.

But If all cells are not filled after considering all possibilities, then the sudoku canâ€™t be solved.

Note: Please try to solve the problem first and then see the below solution approach.