스도쿠 9 박스 (3x3) 재귀 C 모든 조합의 역 추적

Question

3x3 (9 박스)에 스도쿠를 썼습니다. 재귀 적으로 만들고 모든 조합을 생성하고 싶지만 어디서 잘못되었는지 모르겠습니다 ... 여기에 내 코드 : 코드와 난, 난 단지 내가하지 유효을 역 추적 함수를 호출해야한다고 생각 모든 조합을 생성하는 방법을 모르는 말했듯이

#include <iostream> 
#include <stdio.h> 
#include <stdlib.h> 
#define dbg 0 
using namespace std; 
int n,st[100][100]; 

void afisare() 
{ 
    for(int i=1;i<=3;i++) { 
     for(int j=1;j<=3;j++) 
      printf("%2d",st[i][j]); 

     printf("\n"); 
    } 

    printf("\n"); 
} 

int valid(int k,int ii,int jj) 
{ 
    int i,j; 
// if(k==1){ 
//  if(dbg)printf("\nReturnez 1 deoarece k-ul este egal cu 1"); 
// return 1; 
// } 

    for(i=1;i<=3;i++) 
     for(j=1;j<=3;j++) 
      if((i==ii) && (j==jj)) 
      { 
       if(dbg) 
        printf("\nValorile nu indeplinesc criteriul, se incrementeaza j."); 
      } 
      else 
      { 
       if(dbg) 
        printf("\n i= %d j= %d",i,j); 

       if(dbg) 
        printf("\nSe verifica daca %d este egal cu casuta %d %d",k,i,j); 

       if(k==st[i][j]) { 
        if(dbg)printf("\nValorile sunt egale, returnez 0"); 
        return 0; 
       } 
      } 

    if(dbg) 
     printf("\nValorile nu sunt egale, deci returnez 1"); 

    return 1; 
} 

void back(int k) 
{ 
    int i,j; 

    if(dbg) printf("\nk=",k); 

    for(i=1;i<=3;i++) { 
     for(j=1;j<=3;j++) 
     { 
      if(dbg) 
       printf("\nVerifica daca casuta %d %d este egal cu 0",i,j); 

      if(st[i][j]==0) { 
       if(dbg) printf("\n Este egal cu 0"); 
       if(dbg) printf("\n%d ia valoarea %d.",st[i][j],k); 

       st[i][j]=k; 

       if(dbg) 
        printf("\nSe verifica valabilitatea numarului %d",st[i][j]); 

       // while(valid(k,i,j)!=0) 
       if(valid(k,i,j)!=0) { 
        valid(++k,i,j); 
        //back(k+1); 
       } 
       else 
        do { 
         st[i][j]=k+1; 
         if(dbg) 
          printf("\nCasuta %d %d are noua valoare %d, veche valoare fiind %d.",i,j,k+1,k);  
         if(dbg) 
          ("\nValoarea returnata este 0, merg cu urmatoarea valoare %d si verific valabilitatea.",k+1); 

         //back(k+1); 
        } 
        while(valid(++k,i,j)==0); 
      } 
      else 
       if(dbg) 
        printf("\nNu este egala cu 0 ci are valoarea %d",st[i][j]); 
     } 
    } 

    if(k>9 || st[3][3]!=0) 
     afisare(); 

    //afisare(); 
} 

int main() 
{ 
    int i,j; 
    freopen("sudoku.in","r",stdin); 

    for(i=1;i<=3;i++) 
     for(j=1;j<=3;j++) 
      scanf("%d",&st[i][j]); 

/* for(i=1;i<=3;i++){ 
     for(j=1;j<=3;j++){ 
      printf("%2d",st[i][j]); 
     } 

     printf("\n"); 
    }*/ 

    back(1); 
    system("pause"); 

    return 0; 
} 

...

Answer 1

문제를 주로 서식을 지정하고 이름을 지정하는 것입니다. 당신은 아마 재귀 함수 back 이름을 지정하여 자신을 혼란스럽게 관리하고 여기에 이유 :

주어진 시작 조건에 대한 모든 해결책을 찾기 위해 당신을 필요로하는 문제, 기본적으로 깊이 우선 검색을하고 있습니다에

재귀 솔루션 솔루션 공간. 즉, 각 재귀 호출은 전달 이동입니다. 당신은 메서드를 호출하여 역 추적하지 않는

, 당신은 경로까지 그것을보고 있었다 다시 이동 (재귀 중 하나 개 길을 통과 됨) DFS 트리를 할 수 있도록, 더 이상 앞으로 메소드를 호출 하지에 의해 역 추적 in

귀하의 경우에는 스도쿠 격자를 저장하기 위해 전역 데이터 구조 (st)를 사용하고 있습니다. 다시 말하자면, 메소드를 호출하기 전의 상태로 그리드의 상태를 반환해야합니다. 귀하의 경우, 이는 체크인 한 위치를 다시 0으로 설정하는 것을 의미합니다.

여기 글로벌 데이터 구조를 사용하는 경우 솔루션을 안내하고 해결할 수있는 방법이 있습니다. (아주 좋은 프로그래밍 방법은 아닙니다. 클래스를 사용하여 데이터를 저장하는 것이 좋습니다. 그리드).

• void afisare()는
• int valid(int, int, int)이 bool isValid(int, int, int) 될 것입니다 (구현이 동일합니다) 내 솔루션에 void printGrid() 것, 그것은 간단하게 할 수 있습니다

  첫째, 어떤 이름이 변경됩니다.

• void back(int)

는 void fillEmpty()

이 기능은 모든 가능한 숫자 다음 빈 공간을 채우는 시도하며, 모든 유효한 숫자, 그것은 아래로 재귀 다시 fillEmpty()를 호출 할 것이다. 빈 번호가 남아 있지 않으면 해결책을 찾았 기 때문에 격자가 인쇄됩니다.

그래서 내가 아는 한 당신의 문제에 대한 해결책이 있습니다.

#include <stdio.h> 
#include <stdbool.h> 
#include <stdlib.h> 

int grid[3][3]; 

void 
printGrid() 
{ 
    for(int i = 0; i < 3; ++i) { 

     for(int j = 0; j < 3; ++j) 
      printf("%d ", grid[i][j]); 

     printf("\n"); 
    } 

    printf("\n"); 
} 

bool 
isValid(int k, int ii, int jj) 
{ 
    for(int i = 0; i < 3; ++i) 
     for(int j = 0; j < 3; ++j) { 
      if((i != ii || j != jj) && grid[i][j] == k) 
       return false; 
     } 

    return true; 
} 

void 
fillEmpty() 
{ 
    // Find the next empty position. 
    int i, j; bool foundEmpty = false; 
    for(i = 0; i < 3; ++i) { 
     for(j = 0; j < 3; ++j) 
      if(grid[i][j] == 0) { 
       foundEmpty = true; 
       break; 
      } 

     if(foundEmpty) break; 
    } 

    // If there are no empty positions left 
    // we have reached a solution, so we 
    // print it and do nothing else. 
    if(!foundEmpty) 
    { 
     printGrid(); 
     return; 
    } 

    // Try every number 
    for(int k = 1; k <= 9; ++k) 
     if(isValid(k, i, j)) 
     { 
      grid[i][j] = k; 
      fillEmpty(); 
     } 

    // Reset the grid position before backtracking. 
    grid[i][j] = 0; 
} 

int 
main(void) 
{ 
    for(int i = 0; i < 3; ++i) 
     for(int j = 0; j < 3; ++j) 
      scanf("%d", &grid[i][j]); 

    printGrid(); 
    fillEmpty(); 

    return 0; 
}