在 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()

我正在尝试输入一个订单，然后输入左上角的金额，并让它从那里创建一个拉丁方块。问题是，我不知道如何让它在行和列中计数。该程序仅将左上角的数字排列在大小顺序x顺序的方形网格中。

Answer 1

关键思想是您可以创建一个有效的行并旋转该行以生成一个有效的正方形：

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)]

大小为 4 的正方形如下所示：

[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

然后只需旋转第一行：

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)]

Answer 2

拉丁方块是一个NP完全问题(见 http://en.wikipedia.org/wiki/Latin_square#Mathematical_puzzles(，就像数独一样，只是删除了一些约束。

您需要(以某种方式(搜索给定顺序的拉丁方块的空间。您有几种可能性：

1. 手动状态空间搜索

您可以使用一些状态空间搜索技术自己编写拉丁方块求解器。您的初始状态将是拉丁方块，除左上角字段外，其他所有字段均为空白。您可以一次查看一个字段并尝试将其设置为满足约束的数字。如果有，请继续下一个字段，否则回溯到父状态。

您可以在线找到有关状态空间搜索的大量资源。搜索关键字，例如：回溯，DFS，BFS，分支和绑定，A*

2. 转换为另一个组合问题并使用现有的求解器

您可以将此问题转换为另一个经过充分探索的组合优化问题，并为该问题使用求解器。

此问题可以表示为图形着色 - 您可以通过以下方式将其转换为图形着色问题：

正方形
1. 中的每个字段是图形中的一个节点，正方形中的每个数字都是一种颜色。
2. 如果两个节点位于同一行或同一列中，则它们之间存在一条边。
3. 求解着色后，用数字替换颜色。

事实上，拉丁方块(或多或少(是图形着色，只是使用不同的术语:)。

图形着色可以通过 CSP(约束满足规划(求解器求解，也可以直接将问题插入 CSP。

您可以使用ILP(整数线性规划(来解决它。有针对此的调整求解器。GLPK是一个开源的，它有python绑定(例如PyGLPK(

3. 使用元启发式方法

如果你想出一种方法来表达由某些数字填充的某个平方的误差(例如，约束违规的数量，即同一行或同一列中相同数字的对数(，你可以使用一些随机元启发式方法，如简化退火或进化算法来使用该误差函数将解驱动到有效的解。

Answer 3

这个呢？

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.]])

Answer 4

您可以使用 Jacobson 和 P. Matthews 方法。

M. T. Jacobson 和 P. Matthews， 生成均匀分布 随机拉丁方块， J. 组合设计 4 (1996(， 405-437

看

一看。

Answer 5

# Highest number in square
order_of_sq = int(input("Enter order of sq: "))
# Number you want to start the square with
top_left = int(input("Enter top left number: "))
# Sets a placeholder for a variable called top_left_init
top_left_init = 0
# Sets the initial value of top_left to a new variable because the code will
# change the value of top left later on
top_left_init += top_left
# Initialize the value of count
count = 0
# Add 1 to the highest value in latin square to account for the range function
# (the ending number is always one less than the number you enter into the
# range function)
for values in range(1, order_of_sq + 1):
    # Prevents the program from adding too many characters to the line
    while count != order_of_sq:
        # Prints numbers with spaces after them in a horizontal manner
        print(top_left, sep=" ", end=" ")
        # Adds 1 to the top_left
        top_left += 1
        # Count is used to keep track of how many characters are in your line
        count += 1
        # Restarts the numbers in your line when you reach the highest number
        if top_left == order_of_sq + 1:
            top_left = 1
    # Creates a new row
    print()
    count = 0
    # Calls the initial value of top_left and adds 1 to it before beginning the
    # next row
    top_left_init += 1
    # Resets top_left_init to 1 if it reaches the highest number in the square
    if top_left_init == order_of_sq + 1:
        top_left_init = 1
        top_left = top_left_init
    else:
        top_left = top_left_init