IEEE SB Passau Advent Calendar 2025

Sudoku validation

Santa Claus is desperate: Last year a lot of Sudoku puzzle books were given away and this year a lot of children sent in a solution. Because the children were promised that when they attach a solved Sudoku to their new wish list next year, they will receive an additional gift. But Santa Claus and his helpers, don't have time to correct all the sent in Sudokus. Help Santa speed up the correction!
The kids submitted many different sizes of Sudokus, but only Sudokus with a dimension which has an integer square root are included. Only Sudokus of the form K×K with K=n² | n>2 and n∈N+ are checked, e.g. 9×9, 16×16, ...
But be careful, not all Sudokus sent in were completely solved. When a child was not certain, it entered a question mark instead of a number. For each puzzle you have to check if all Sudoku rules are followed:

• each number from 1 to n occurs exactly once per row
• each number from 1 to n occurs exactly once per column
• each number from 1 to n occurs exactly once in a box of size √ n 

Input

The input consists of a table in CSV format with commas as separators between the cells and a semicolon at the end of each row. The first row consists of only one value indicating the dimension (K) of the Sudoku. This is followed by n lines, each with n elements, resulting in a square matrix as is usual for a Sudoku. The individual fields can contain the positive integers 1-n or a question mark ?.

Output

Only a truth value True/False is expected as output.

Example

Input

9;
8,3,5,4,1,6,9,2,7;
2,9,6,8,5,7,4,3,1;
4,1,7,2,9,3,6,5,8;
5,6,9,1,3,4,7,8,2;
1,2,3,6,7,8,5,4,9;
7,4,8,5,2,9,1,6,3;
6,5,2,7,8,1,3,9,4;
9,8,1,3,4,5,2,7,6;
3,7,4,9,6,2,8,1,5;

Output

True

Questions and answers

Please log in to submit a question...

Submit a solution

Please log in to submit a solution...