The problem of checking if every row and column of a matrix contains all numbers from 1 to n can be approached by iterating through the matrix and ensuring that each row and column contains all required numbers without repetition.
Problem Statement
Given an ( n \times n ) matrix, verify if every row and every column contains all integers from 1 to n exactly once.
C# Implementation
Here’s how you can implement this in C#:
using System;
using System.Collections.Generic;
public class MatrixChecker
{
public static bool CheckMatrix(int[][] matrix)
{
int n = matrix.Length;
// Check each row
for (int i = 0; i < n; i++)
{
HashSet<int> rowSet = new HashSet<int>();
for (int j = 0; j < n; j++)
{
if (matrix[i][j] < 1 || matrix[i][j] > n || !rowSet.Add(matrix[i][j]))
{
return false; // Value out of range or duplicate found
}
}
}
// Check each column
for (int j = 0; j < n; j++)
{
HashSet<int> colSet = new HashSet<int>();
for (int i = 0; i < n; i++)
{
if (matrix[i][j] < 1 || matrix[i][j] > n || !colSet.Add(matrix[i][j]))
{
return false; // Value out of range or duplicate found
}
}
}
return true; // All checks passed
}
public static void Main(string[] args)
{
int[][] matrix = new int[][]
{
new int[] { 1, 2, 3 },
new int[] { 2, 3, 1 },
new int[] { 3, 1, 2 }
};
bool isValid = CheckMatrix(matrix);
Console.WriteLine($"The matrix is valid: {isValid}");
}
}
Explanation
-
Matrix Structure:
- The matrix is represented as a 2D array (
int[][]
), where each inner array corresponds to a row in the matrix.
- The matrix is represented as a 2D array (
-
CheckMatrix Method:
- This method checks whether every row and column contains all numbers from 1 to n.
n
is determined by the length of the matrix.
-
Row Checking:
- A loop iterates over each row. A
HashSet<int>
is used to track the unique numbers in the current row. - For each number in the row, the method checks:
- If the number is outside the valid range (1 to n).
- If the number has already been added to the
HashSet
(which indicates a duplicate).
- If any of these checks fail, the method returns
false
.
- A loop iterates over each row. A
-
Column Checking:
- Similar to row checking, a loop iterates over each column.
- A new
HashSet<int>
is used for each column to track unique numbers. - The same validation checks are performed for each number in the column.
-
Final Result:
- If all rows and columns pass the checks without duplicates or out-of-range numbers, the method returns
true
.
- If all rows and columns pass the checks without duplicates or out-of-range numbers, the method returns
-
Main Method:
- This method creates a sample matrix and calls the
CheckMatrix
method, printing whether the matrix is valid.
- This method creates a sample matrix and calls the
Usage
You can modify the matrix
variable in the Main
method to test different configurations. This implementation ensures that each row and column contains the numbers from 1 to n exactly once, effectively validating the matrix.