스도쿠 역 추적 알고리즘 실패

스도쿠 보드를 생성하려고하는데 솔루션을 생성 할 수 있지만 이제 사용자가 채울 수있는 사각형을 제거해야합니다. 이렇게하려면 역 추적을 사용하여 매번 사각형을 제거 할 때마다 보드를 1. 해결할 수 있고 2. 솔루션이 하나뿐입니다.스도쿠 역 추적 알고리즘 실패

문제는 I합니다 (제로가 빈 사각형이다) this board 내 역 추적 알고리즘을 테스트

, 그것은 this solution를 반환합니다. 분명히 예를 들어 첫 번째 줄에 여러 개의 9로 끝나지 않는 것을 선호합니다.

내 코드

- (BOOL) solveArray: (NSArray*) numArray { 
    NSMutableArray* board = [numArray mutableCopy]; 
    for (int i=0; i<9; i++) { //make all of the arrays mutable as well (since it's 2D) 
     [board replaceObjectAtIndex:i withObject:[board[i] mutableCopy]]; 
    } 

    //if everything is filled in, it's done 
    if (![self findUnassignedLocation:board]) { 
     NSLog(@"\n%@", [SudokuBoard sudokuBoardWithArray:board]); 
     return TRUE; 
    } 

    NSArray* poss = [[SudokuBoard sudokuBoardWithArray:board] possibleNumbersForRow:self.arow Col:self.acol]; 


    //if there are no options for a location, this didn't work. 
    if ([poss count] == 0) { 
     return FALSE; 
    } 

    //otherwise, continue recursively until we find a solution 
    else { 
     for (int i=0; i<[poss count]; i++) { 
      //make a tentative assignment 
      board[self.arow][self.acol] = poss[i]; 
      //return, if successful, done 
      if ([self solveArray:board]) { 
       return TRUE; 
      } 
      //if that didn't work, unmake it and retry with other options 
      board[self.arow][self.acol] = [NSNumber numberWithInt:0]; 
     } 
    } 
    return FALSE; 
}

내가 잘못 갈 수있는 위치에 어떤 생각을?

출처

2014-03-05 maripeza

각 재귀 수준에는 고유 한 행 및 열 변수가 필요합니다. 즉 행과 열은 멤버 변수가 아닌 solveArray 및 findUnassignedLocation의 출력이어야합니다. 그대로, 역 추적이있을 때 실패한 레벨의 행과 열이 호출자에 의해 재사용됩니다.

할당 된 위치 중 일부를 덮어 쓰는 경우 findUnassignedLocation에도 오류가있을 수 있습니다.

결과가 유효하지 않은 경우 possibleNumbersForRow에도 오류가있을 수 있습니다.

출처

2014-03-06 00:41:36 xan

감사합니다. 실제로 전역 변수를 사용하지 않도록 전체 내용을 다시 작성하고 전역 변수 대신 변수를 전달하기 위해 언급 한 두 가지 기능을 변경했습니다. 그게 내가 필요한 것! – maripeza

스도쿠 역 추적 알고리즘 실패

답변

관련 문제