Creating a Latin Square program in Python

Question

order = input("Input the order of a Latin Square: ")
top_left = input("Input the top-left number: ")
int_order = int(order)
int_top_left = int(top_left)
for order in range(int_order):
    for top_left in range(int_order):
        print(int_top_left, end=" ")
    print()

I am trying to input an order then a top left amount and have it create a latin square from there. The problem is, I don't know how to make it count up in the rows and columns. This program only arranges the top left number in a square grid with the size order x order.

Solution 1

The key idea is that you can create a valid row and rotate the row to generate a valid square:

def create_latin_square(n: int):
    row = [i for i in range(1, n+1)]
    return [row[i:] + row[:i] for i in range(n)]

A square of size 4 looks like this:

[1, 2, 3, 4]  # row
[2, 3, 4, 1]  # row, rotated by 1 to the left
[3, 4, 1, 2]  # row, rotated by 2 to the left
[4, 1, 2, 3]  # row, rotated by 3 to the left

Then just rotate the first row:

def create_latin_square(n: int, start_el: int=1):
    row = [i for i in range(1, n+1)]
    row = row[start_el-1:] + row[:start_el-1]
    return [row[i:] + row[:i] for i in range(n)]

Solution 2

The Latin Square is an NP-complete problem (see http://en.wikipedia.org/wiki/Latin_square#Mathematical_puzzles), like Sudoku, only with some constraints dropped.

You need to (somehow) search the space of Latin Squares of the given order. You have several possibilites:

1. Manual state-space search

You can write the Latin Square solver yourself using some state-space search techniques. Your initial state will be the Latin Square with all but the top-left field blank. Than you can look at one field at a time and try to set it to a number satisfying the constraints. If there is such, proceed to the next field, else backtrack to the parent state.

You can find a huge amount of resources on state-space search online. Search for keywords like: backtracking, DFS, BFS, branch and bound, A*

2. Convert to another combinatorial problem and use an existing solver

You can convert this problem to another, well explored combinatorial optimization problem and use a solver for that one.

This problem can be expressed as Graph coloring - you can convert it to graph coloring problem in the following way:

1. Each field in the square is one node in the graph, each number in the square is one color.
2. There is an edge between two nodes if they are in the same row or column.
3. After the coloring is solved, you replace colors by numbers.

In fact, the Latin Square (more or less) is graph coloring, only using different terminology :).

Graph coloring can be solved by CSP (Constraint Satisfaction Programming) solvers, or you can plug your problem into CSP directly.

You can solve it using ILP (Integer Linear Programming). There are tuned solvers for that. GLPK is an open source one and there are python bindings for it (e.g. PyGLPK)

3. Use a metaheuristic approach

If you figure out a way how to express an error for some square filled by some numbers (e.g. the number of constraint violations, i.e. number of pairs of the same numbers in the same row or column), you can use some stochastic metaheuristics like Simmulated Annealing or Evolutionary Algorithms to use that error function to drive the solutions to a valid one.

Solution 3

what about this?

def latin_square(n, mod='ballanced'):
  import numpy as np

  mat = np.empty((n,n,))*np.nan

  mat[:,0] = range(1,n+1)

  if mod=='ballanced':
    shift = (.5-np.mod(np.array(range(1,n)),2))/.5*np.ceil(np.array(range(1,n))/2)
    shift = shift.astype(int)
  elif mod=='normal':
    shift = np.array(range(n-1, -1, -1))

  for col in range(1, n):
    mat[:, col] = np.roll(mat[:,0], shift[col-1])
    
  return(mat)


latin_square(6)

array([[1., 2., 6., 3., 5., 4.],
   [2., 3., 1., 4., 6., 5.],
   [3., 4., 2., 5., 1., 6.],
   [4., 5., 3., 6., 2., 1.],
   [5., 6., 4., 1., 3., 2.],
   [6., 1., 5., 2., 4., 3.]])

Solution 4

You can use the Jacobson and P. Matthews approach.

M. T. Jacobson and P. Matthews, Generating uniformly distributed random Latin squares, J. Combinatorial Design 4 (1996), 405-437

Take a look.

View more solutions

Comments

[Tristan Wiley]

This should include an explanation of code, all code answers are not valuable.

[Nathan Tuggy]

@TristanWiley: I was about to ask "but what about the comments?" when I realized they weren't all that much of an addition. Still, the code does have an explanation built in, it's just not focusing on the most interesting parts.

[Floam]

The comments were meant to help him/her follow the program from start to finish. The student could easily Google Latin Squares to gain a deeper understanding of the concept.

[Martin Thoma]

"The Latin Square is an NP-complete problem" - not always. Especially not if only one cell is filled as my solution shows.

[Martin Broadhurst]

The problem here is Latin square construction, not Latin square completion, so it isn't NP-complete. All of these methods are overkill except for backtracking.