2 
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 顺序的方形网格中。

4

5 回答 5

3

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

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)]
于 2020-04-10T21:01:09.877 回答
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. 使用元启发式方法

如果您想出一种方法来表达由某些数字填充的某个正方形的错误（例如，违反约束的数量，即同一行或列中相同数字对的数量），您可以使用一些随机元启发式算法，例如Simmulated退火或进化算法使用该误差函数将解决方案驱动为有效的解决方案。

于 2014-09-23T09:59:17.547 回答
1

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

MT Jacobson 和 P. Matthews，生成均匀分布的随机拉丁方格，J. Combinatorial Design 4 (1996)，405-437

看一看。_

于 2014-09-25T03:04:54.420 回答
1

那这个呢？

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.]])
于 2020-09-13T02:42:59.917 回答
0 
# 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
于 2015-05-18T00:58:40.453 回答