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) 

체크 (격자) 어떤 요소가 두 번 모든 행/열을 반복되어 있지 않은 경우는 true를 돌려 다음과 같이

가 나는 알고리즘의 생각했다.

어딘가에 무한 루프에 갇히게 될지도 모르고 또한 이것으로 역 추적을 사용하지 않을 수도 있다는 것을 알고 있습니다. 주어진 문제에 대해 역 추적을 사용하는 방법에 대한 안내를받을 수 있습니까?

누군가 코드를 제공 할 수 있다면 좋을 것입니다. 감사. 존재하는 경우

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"이다) 의사의 솔루션의 존재 여부를 설명합니다. 가능한 모든 솔루션을 반환 할 수 있습니다.

이 절차에서 빈 셀에 대한 "선택 사항"은 즉시 문제를 일으키지 않는 번호입니다. 즉, 해당 행과 열에 아직 나타나지 않은 번호입니다.

이렇게 빨리 만들 수있는 다양한 최적화가 있습니다 (하나의 쉬운 예 : 빈 셀의 수를 계산하는 추가 매개 변수 전달). https://en.wikipedia.org/wiki/Dancing_Links은 Knuth의 효율적인 솔루션입니다.

라틴어 사각형을 모두 생성하지 않는 또 다른 저렴한 솔루션은 다른 라틴어 사각형을 바꾸는 것입니다. 즉, 라틴 사각형의 행, 열 및 숫자를 바꾸면 다른 라틴어 사각형이 생성됩니다. 따라서 프로그램에 구워진 10 개 또는 20 개의 서로 다른 라틴 사각형을 무작위로 선택한 다음이를 치환하여 위장 할 수 있습니다.

다음은 매우 효율적인 Python 솔루션입니다. 그것은 약 30 초에 무작위 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