Simple Algorithms for Programmers Looking for a Job: Part Two - Latin Square

Introduction

I have always been fascinated by the elegance of mathematical structures, and one of the most intriguing ones I have come across is the Latin Square. During a visit to the Bibliothèque Nationale de France, I stumbled upon a book by René Descombes titled Les carrés magiques, and I was completely fascinated by it. The Latin Square is an array filled with different symbols, each appearing exactly once in each row and column. This concept has been studied for centuries, and I love discovering its real-world applications in statistics, scheduling, and even cryptography.

One of the most fascinating applications of Latin squares is in experimental design. Researchers use them to control variations in two directions, making experiments more reliable in fields like agriculture, medicine, and industry. I also find their use in time planners particularly practical—Latin squares can help organize tasks and personnel schedules to prevent redundancy and conflicts.

Latin squares also pop up in error-correcting codes, Sudoku puzzles, and round-robin tournament schedules. Their structured beauty makes them a great tool for solving problems requiring balanced arrangements.

What truly excites me is the connection between Latin squares and art. At Gonville and Caius College in Cambridge, there's a stained glass window designed by Sir Roland Fischer, depicting a Latin square in seven distinct colors. I would love to visit Cambridge one day and see this masterpiece in person. The idea that something as abstract as a mathematical concept can be transformed into a visually stunning piece of art is inspiring.

Problem Statement

Given an integer ( n ), construct an ( n \times n ) Latin square where each row and each column contains the numbers from ( 1 ) to ( n ) exactly once.

Pseudocode

FUNCTION generate_latin_square(n)
    CREATE a matrix 'square' of size (n x n) filled with zeros

    FOR i from 0 to n - 1 DO
        FOR j from 0 to n - 1 DO
            COMPUTE the value for cell (i, j) using the formula:
                square[i][j] = (i + j) MOD n + 1
        END FOR
    END FOR

    RETURN the 'square' matrix
END FUNCTION

Implementations

Python

import numpy as np

def generate_latin_square(n):
    square = np.zeros((n, n), dtype=int)
    for i in range(n):
        for j in range(n):
            square[i][j] = (i + j) % n + 1
    return square

def print_latin_square(square):
    for row in square:
        print(" ".join(map(str, row)))

if __name__ == "__main__":
    while True:
        try:
            n = int(input("Your latin square have to be between 3 and 7 : "))
            if 3 <= n <= 7:
                break
            else:
                print("Give me a number between 3 and 7.")
        except ValueError:
            print("Wrong entry. Give me a number between 3 and 7.")

    latin_square = generate_latin_square(n)
    print("latin square generated:")
    print_latin_square(latin_square)

JavaScript

function generateLatinSquare(n) {
    let square = Array.from({ length: n }, () => Array(n).fill(0));
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            square[i][j] = (i + j) % n + 1;
        }
    }
    return square;
}

function printLatinSquare(square) {
    square.forEach(row => console.log(row.join(" ")));
}

(function main() {
    let n;
    while (true) {
        n = parseInt(prompt("Your Latin square must be between 3 and 7: "), 10);
        if (n >= 3 && n <= 7) break;
        alert("Give me a number between 3 and 7.");
    }

    let latinSquare = generateLatinSquare(n);
    console.log("Latin square generated:");
    printLatinSquare(latinSquare);
})();

Java

import java.util.Scanner;

public class LatinSquare {
    public static int[][] generateLatinSquare(int n) {
        int[][] square = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                square[i][j] = (i + j) % n + 1;
            }
        }
        return square;
    }

    public static void printLatinSquare(int[][] square) {
        for (int[] row : square) {
            for (int num : row) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n;
        while (true) {
            System.out.print("Your Latin square must be between 3 and 7: ");
            n = scanner.nextInt();
            if (n >= 3 && n <= 7) break;
            System.out.println("Give me a number between 3 and 7.");
        }

        int[][] latinSquare = generateLatinSquare(n);
        System.out.println("Latin square generated:");
        printLatinSquare(latinSquare);
        scanner.close();
    }
}

Further Exploration

• Implement Latin squares using different methods, such as backtracking for more complex constraints.
• Explore applications of orthogonal Latin squares in statistical experiments.
• Modify the algorithm to generate randomized Latin squares instead of deterministic ones.
• Study how Latin squares relate to other combinatorial structures like magic squares and Sudoku puzzles.

By mastering the construction of Latin squares, programmers can improve their problem-solving skills and prepare for algorithmic coding interviews where combinatorial logic is tested. Understanding these structures opens doors to practical applications in various domains, making them a valuable topic to explore.