스도쿠가 독창적 인 솔루션을 가지고 있는지 확인하십시오.

Question

스도쿠가 고유 한 솔루션을 가지고 있는지 또는 여러 솔루션을 가지고 있는지 판단하기 위해 백 트랙킹 알고리즘에 어려움을 겪고 있습니다. (다른 솔루션이 존재하는 경우) 내가 다른 해결책을 찾아야한다 두 개의 서로 다른 해결-algorithmns를 얻을 내가

for (int val = 1; val <= 9; ++val) { 
for (int val = 9; val >= 1; val--) { 

을 변경하는 경우 :

static boolean solve(int i, int j, int[][] cells) { 
    if (i == 9) { 
     i = 0; 
     if (++j == 9) 
      return true; 
    } 
    if (cells[i][j] != 0) // skip filled cells 
     return solve(i+1,j,cells); 

    for (int val = 1; val <= 9; ++val) { 
     if (legal(i,j,val,cells)) { 
      cells[i][j] = val; 
      if (solve(i+1,j,cells)) 
       return true; 
     } 
    } 
    cells[i][j] = 0; // reset on backtrack 
    return false; 
} 

첫 번째 방법 : 여기 내가 사용하는 역 추적 코드입니다. 이 접근 방식의 문제점은 알고리즘이 약간 변경되었지만 그 이유를 모르더라도 알고리즘이 종료되지 않는다는 것입니다.

두 번째 접근 : 다시 추적하여 솔루션을 계속 검색하십시오. 내가 이것을 시도하면, 그것은 또한 작동하지 않는다.

Java 예제를 찾으려고했지만 "다시 추적하고 두 번째 솔루션을 계속 검색"과 같은 정보 만 찾을 수 있습니다.

사람이 여러 솔루션 왜 내 첫 번째 방법

또는

누군가가 나에게 설명해 주시겠습니까 (정확한 숫자가 필요하지 않은)이있는 경우는 저에게 말한다 있도록 알고리즘을 변경하는 방법을 예제를 제공시겠습니까 종료되지 않습니까?

감사합니다.

Answer 1

후 당신은 0, 1, 또는 1 개 이상이있는 경우를 구별 할 수, 부울 대신 숫자를 반환하는 경우 솔루션.

// returns 0, 1 or more than 1 depending on whether 0, 1 or more than 1 solutions are found 
static byte solve(int i, int j, int[][] cells, byte count /*initailly called with 0*/) { 
    if (i == 9) { 
     i = 0; 
     if (++j == 9) 
      return 1+count; 
    } 
    if (cells[i][j] != 0) // skip filled cells 
     return solve(i+1,j,cells, count); 
    // search for 2 solutions instead of 1 
    // break, if 2 solutions are found 
    for (int val = 1; val <= 9 && count < 2; ++val) { 
     if (legal(i,j,val,cells)) { 
      cells[i][j] = val; 
      // add additional solutions 
      count = solve(i+1,j,cells, count)); 
     } 
    } 
    cells[i][j] = 0; // reset on backtrack 
    return count; 
} 

Answer 2

리셋 루프의 내부에 있어야하며 if solve 조건

for (int val = 1; val <= 9; ++val) { 
     if (legal(i,j,val,cells)) { 
      cells[i][j] = val; 
      if (solve(i+1,j,cells)) 
       return true; 
      cells[i][j] = 0; // reset on backtrack 
     } 
    }