我正在处理一个问题，我需要创建一个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。
我知道这是不正确的，因为它可能会陷入一个无限循环的某个地方，而且我没有使用回溯在这个
有人能指导我如何使用回溯法来解决给定的问题吗？
如果有人能提供一些代码就好了谢谢。
最佳答案
下面是生成随机拉丁方的伪代码（本质上是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，如果有一个，返回一个描述是否存在一个解决方案的布尔值。它可以返回任何可能的解决方案。
注意，在此过程中，空单元格的“选择”是一个不会立即导致问题的数字——也就是说，任何尚未出现在该行和列中的数字。
有各种优化方法可以使这个过程更快（一个简单的例子：传递一个额外的参数来计算还有多少空白单元格），但是https://en.wikipedia.org/wiki/Dancing_Links是Knuth的有效解决方案。
另一个廉价的解决方案是，不生成所有拉丁方，只需对另一个拉丁方进行置换：对一个拉丁方的行、列和数字进行置换就可以生成另一个拉丁方。所以你可以有10或20个不同的拉丁方块烘焙到你的程序中，随机挑选一个，然后通过排列来伪装它。
这里有一个相当有效的python解决方案。它在大约半秒钟内产生随机的30x30拉丁方。通过消除o（n^2）max操作，而不是保持优先级队列，仍然可以将速度提高一个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