創造 - 數獨像

我上的問題，在這裏我需要創建一個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)

校驗（網格）如果沒有元素被重複兩次任何行/列返回true。

我知道這是不正確的，因爲它可能會卡住在一個無限循環的地方，我也沒有在這個使用回溯有人可以指導我如何使用回溯我的問題？

這將是很好，如果有人可以提供一些代碼。謝謝。

來源

2017-04-27 J.Doe

這裏的僞代碼（其基本上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

來源

2017-04-27 13:16:08

創造 - 數獨像

回答

相關問題