스도쿠 해결/알고리즘 생성 문제

Question

vb.net에서 스도쿠 퍼즐을 생성하는 프로그램을 만들고 있는데,이 방법으로 보드 위치를 해결할 필요가 있습니다 (특정, 임의의 순서)를 역순으로 다시 풀 수 있습니다. 이 재귀 솔버를 사용하고 있습니다.

이

제가 함께 일하고 코드이다 check_conflicts 특정 셀 할당이 직접적으로 기판과 충돌하는지 여부를 판정하는 기능 (따라서 판 전달되고 세포 order(i)의 인덱스이다

Public Function solve(ByRef board() As Integer) As Boolean 
    For i = 0 To 80 
     If board(order(i)) = 0 Then 
      For j = 1 To 9 
       board(order(i)) = j 
       If check_conflicts(board, order(i)) = False Then 
        If solve(board) = True Then 
         Return True 
        End If 

       End If 
      Next 
      board(order(i)) = 0 
      Return False 
     End If 
    Next 

    Return True 
End Function 

또한 통과된다). 이 함수는 order이 0에서 80까지의 목록 일 때 예상대로 작동하지만 order이 무작위로 셔플 된 목록 인 경우 함수는 매우 길거나 (때로는 1 분 이상) 대개 정답을 얻습니다. order가 80에서 0까지의 숫자 목록 일 때 함수는 아무 것도 해결하지 않고 항상 false를 반환합니다.

나는 코드를 단계별로 시도했지만 재귀 함수로는 어렵다. 아무도 내가 논리적 오류를 볼 수 있는지 궁금해, 고마워!

Answer 1

이 기능은 순서는 무작위로 단행 목록 인 경우, 그러나 다음 함수가 매우 긴 (때로는 위쪽 분) 소요되는 순서는 0 ~ 80의 목록이 예상대로 작동하지만 일반적으로 얻는다 정답.

이유는 재귀 트리 재귀 수준으로 기하 급수적으로 증가하면서 (오히려 임의의 순서로보다) 행으로 수 행을 처리 할 때, 잘못된 계약의 대부분이 초기 절단되어있을 수 있습니다. 첫 번째 행이 일관성이없는 상태에서 두 번째 행을 처리 할 필요가 없습니다. 순서는 80에서 0으로 번호의 목록 인 경우

, 함수는 아무것도 해결하고 항상 false를 반환하지 않습니다.

몇 가지 제안 :

1) 문제가 order() 기능에 있지 않은지 확인하기 위해 80-i으로 order(i)을 교체하십시오;

2) check_conflicts(board, order(i))으로 전화 할 때마다 check_conflicts(inverse(board), 80-order(i))으로 전화를 걸어 결과가 동일하지 않은 경우 예외를 throw하십시오.