作成 -

Question

私は、（N、ここでは入力として与えられる）NxNの行列を作成するようにする必要がある問題に取り組んでい様数独は、すべてのエントリは範囲[1、N]とに記載されていませんエントリは特定の行または列で2回繰り返されます。対角線には制約はありません。

また、すべての実行でグリッドの出力が確実に出力されるように、乱数ジェネレータを使用する必要があります。

また、私はこれを解決するためにバックトラッキングを使用するヒントを与えられました。どの要素が任意の行/列回繰り返されていない場合

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) 

チェック（グリッド）を次のように私はアルゴリズムを考えた

は真を返します。

どこかで無限ループに詰まっている可能性があり、これでバックトラッキングを使用していない可能性があるので、間違っていることがわかります 問題のバックトラックを使用する方法について教えてもらえますか？

誰かが何らかのコードを提供できるといいですね。ありがとう。ある場合

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を完了：

Answer 1

はここで、ランダムなラテン方陣を生成する（この問題に特化し、本質的にKnuth's "Algorithm X"である、）擬似コードです解が存在するかどうかを記述する。可能な解決策を返すことができます。

（注）この手順で空のセルのための「選択」は、すぐに問題にならない数であること - つまり、すでにその行と列に表示されていない任意の数。

これを高速化するためのさまざまな最適化があります（1つの簡単な例：余分なパラメータを渡して何個の空白セルを残すか）。https://en.wikipedia.org/wiki/Dancing_LinksはKnuthの効率的なソリューションです。他のラテンラテン方陣平方利回りの行、列、数字を並べ替え：

すべてのラテンの正方形を生成しないもう一つの安価な解決策は、他のラテン方陣を置換するために、単純です。だからあなたはプログラムに焼き付けられた10個または20個の異なるラテンの四角形をランダムに選んで並べ替えることでそれを隠すことができます。

これは、合理的に効率的なPythonソリューションです。それは約30秒でランダムな30x30ラテン方陣を生成します。まだO（N^2）の最大操作を排除し、代わりにプライオリティキューを維持することによってLOGN N倍/によって速度を向上させることが可能でなければなりませんが、それはおそらくすでに十分に高速です。

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