algorithm - 创建 nxn 矩阵 - 数独类

Question

我正在研究一个问题，我需要创建一个 NxN 矩阵(N 在这里作为输入给出)，这样，所有条目都在 [1,N] 范围内，并且没有条目在特定的范围内重复两次行或列。对角线没有限制。

此外，我需要使用随机数生成器来确保网格的输出随每次执行而变化。

另外，我得到了使用回溯来解决这个问题的提示。

我想到了如下算法

func(i,j):
    grid[i][j] = 1 + rand()%N
    if(check(grid)==true)
        j++
        if j == N
            j = 0
            i++
            if i == N
                return
    else
       //resetting the grid entry
        grid[i][j] = -1;
    //make a recursive call to func(i,j) again
    func(i,j)

如果没有任何元素在任何行/列中重复两次，则 check(grid) 返回 true。

我知道这是不正确的，因为它可能会在某个地方陷入无限循环，而且我也没有在其中使用回溯 有人可以指导我如何对给定的问题使用回溯吗？

如果有人能提供一些代码就好了。谢谢。

Answer 1

这是生成随机拉丁方的伪代码(本质上是 Knuth's "Algorithm X"，专门用于此问题):

complete(S):
    If S is completely filled in, return true
    find the index [i,j] where there's the fewest immediate choices.
    for c in each choice for S[i,j] {  // iterated over in a random order
        S[i][j] = c
        if complete(S) {
            return true
        }
    }
    S[i][j] = blank
    return false
}

如果存在一个随机有效解，此过程将用一个随机有效解来完成数组 S，并返回一个描述解是否存在的 bool 值。它可以返回任何可能的解决方案。

请注意，在此过程中，空单元格的“选择”是不会立即导致问题的数字——也就是说，任何尚未出现在该行和列中的数字。

您可以进行各种优化来加快速度(一个简单的示例:传递一个额外参数来计算剩余空白单元格的数量)，但是 https://en.wikipedia.org/wiki/Dancing_Links是 Knuth 的高效解决方案。

另一个不生成所有拉丁方的廉价解决方案是简单地置换另一个拉丁方:置换一个拉丁方的行、列和数字会产生另一个拉丁方。因此，您可以将 10 或 20 个不同的拉丁方 block 嵌入到您的程序中，随机选择一个，然后通过排列来伪装它。

这是一个相当高效的 Python 解决方案。它会在大约半秒内生成一个随机的 30x30 拉丁方 block 。通过消除 O(N^2) 最大操作并维护优先级队列，仍然可以将速度提高 N/logN 倍，但它可能已经足够快了。

import random

def bitcount(n):
    i = 0
    while n:
        i += 1
        n &= n-1
    return i

def complete(S, rowset, colset, entries):
    N = len(S)
    if entries == N * N:
        return True
    i, j = max(
        ((i, j) for i in xrange(N) for j in xrange(N) if S[i][j] == 0),
        key=(lambda (i, j): bitcount(rowset[i]|colset[j])))
    bits = rowset[i]|colset[j]
    p = [n for n in xrange(1, N+1) if not (bits >> (n-1)) & 1]
    random.shuffle(p)
    for n in p:
        S[i][j] = n
        rowset[i] |= 1 << (n-1)
        colset[j] |= 1 << (n-1)
        if complete(S, rowset, colset, entries+1): return True
        rowset[i] &= ~(1 << (n-1))
        colset[j] &= ~(1 << (n-1))
    S[i][j] = 0
    return False

N = 30
ns = len(str(N))
for _ in xrange(5):
    S = [[0] * N for _ in xrange(N)]
    assert complete(S, [0]*N, [0]*N, 0)
    for row in S:
        print ''.join('%*d ' % (ns, x) for x in row)
    print