Same row column

You are given an n x n matrix containing integers from 1 to n.

Write a script to find if every row and every column contain all the integers from 1 to n.

Examples

Example 1
Input: @matrix = ([1, 2, 3, 4],
                  [2, 3, 4, 1],
                  [3, 4, 1, 2],
                  [4, 1, 2, 3])
Output: true

Example 2
Input: @matrix = ([1])
Output: true

Example 3
Input: @matrix = ([1, 2, 5],
                  [5, 1, 2],
                  [2, 5, 1])
Output: false
Elements are out of range 1..3.

Example 4
Input: @matrix = ([1, 2, 3],
                  [1, 2, 3],
                  [1, 2, 3])
Output: false

Example 5
Input: @matrix = ([1, 2, 3],
                  [3, 1, 2],
                  [3, 2, 1])
Output: false

Analysis

A simple challenge for which someone will probably have a one-line solution.

But is it really so simple? No limit has been placed on the size of the matrix, and it could be - say - 1000 x 1000 with a million elements, so let's look for an efficient solution.

My solution inspects each element of the matrix no more than once, and does the following:

• Checks that the value of the element is in the range 1 .. $n: if not, returns false
• Checks that the value has not been seen already in the same row or column: if it has, returns false
• Records that it has been seen in the current row and column

It may not be immediately obvious that this is sufficient to meet the terms of the challenge, but in a n x n matrix containing only the digits 1 to n, no digit can appear more than once in any row or column. Consider for example example 5 above. It contains exactly three (ie n) ones, and can only meet the challenge criterion if all the ones occupy different rows and columns.

Hence, if my algorithm encounters a number which has already been seen in the same row or column there will be another row or column that lacks that digit, and the matrix therefore fails the challenge criterion.

Similarly, if a digit is found outside the range of 1 to n, the matrix fails because all n positions are required in that row and column to house the digits 1 to n.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge/381/1

use v5.26;    # The Weekly Challenge - 2026-07-06
use utf8;     # Week 381 - task 1 - Same row column
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

same_row_column([[1, 2, 3, 4],
                 [2, 3, 4, 1],
                 [3, 4, 1, 2],
                 [4, 1, 2, 3]]);
                 
same_row_column([[1]]);

same_row_column([[1, 2, 5],
                 [5, 1, 2],
                 [2, 5, 1]]);
                 
same_row_column([[1, 2, 3],
                 [1, 2, 3],
                 [1, 2, 3]]);
                 
same_row_column([[1, 2, 4],
                 [2, 3, 1],
                 [3, 1, 2]]);

sub same_row_column {
    
    my ($matrix, @good, $m, $row, $col, $in_row, $in_col, $value, $test);
    
    # initialise
    $matrix = shift;
    $m = scalar @$matrix - 1;  # $m == $n - 1
    print_matrix($matrix, $m, qq[Input: ]);

    # survey matrix
    for $row (0 .. $m) {
        for $col (0 .. $m) {
            $value = $matrix->[$row]->[$col];
            unless ($value >= 1 and $value <= $m + 1) {
                say qq[Output: false - out of range value: $value];
                return;
            }
            if ($in_row->[$row]->[$value] or 
                $in_col->[$col]->[$value]) {
                say qq[Output: false - duplicated value: $value];
                return;
            }   
            $in_row->[$row]->[$value] = $in_col->[$col]->[$value] = 1;
        }
    }
    
    # otherwise ...
    say qq[Output: true];
}

sub print_matrix {
    
    my ($matrix, $cols, $legend, $row, $rows);
    
    # print array as a matrix with $cols columns
    ($matrix, $cols, $legend) = @_;
    $rows = $cols;
    say '';
    for $row (0 .. $rows) {
        say qq{$legend [} . join(', ', @{$matrix->[$row]}) . ']'
                . ($row < $rows ? ',' : '');
        $legend = ' ' x length($legend);
    }
}

26 lines of code

Output from script

Input:  [1, 2, 3, 4],
        [2, 3, 4, 1],
        [3, 4, 1, 2],
        [4, 1, 2, 3]
Output: true

Input:  [1]
Output: true

Input:  [1, 2, 5],
        [5, 1, 2],
        [2, 5, 1]
Output: false - out of range value: 5

Input:  [1, 2, 3],
        [1, 2, 3],
        [1, 2, 3]
Output: false - duplicated value: 1

Input:  [1, 2, 4],
        [2, 3, 1],
        [3, 1, 2]
Output: false - out of range value: 4