php easy 스도쿠 해결사 backtracking 사용

Question

최근에 PHP 내에서 쉽게 스도쿠를 풀 수 있는지보고 싶었습니다. 나는 PHP가 프로그래밍상의 이유로 정말로 선택되지는 않는다는 것을 알고있다. 그러나 나는 PHP를 가장 잘 안다. 그리고 자바와 C에서 디자인에 문제가있다. 그럼에도 불구하고 작동하지 않아야하는 이유는 없습니다.

먼저 해결 된 스레드가 있기 때문에 처음에는 묻지 않았습니다. 그러나 나는 그 솔루션이 너무 복잡해서 (다른 언어, 복잡한 구조체) 내 목표를 이해할 수 없다는 것을 알았다.

내 질문은 : 누군가 내 목표에 따라 나에게 힌트를 줄 수 있습니까? 추측없이 단순한 스도쿠 해결사를 원합니다. 역 추적 만하면됩니다.

알고리즘은 다음과 같다 : 치명적인 오류 : 134,217,728의 허용 메모리 크기 나 빈 스도쿠를 만드는 경우

$cell; // 1-81 - as parameter of the recursive function solve() 
$value; // 1-9 - as parameter ... 

class Sudoku { 

function solve($cell = 1, $value = 1) { 

    // skipping values 

    if the current cell is fix: 

     return solve(cell++, $value); 

    // testing values (logic) 

    if not: 

     if the value is within the square (3x3) itself: 

      return solve($cell, $value++); 

     if the value is within the row: 

      return solve($cell, $value++); 

     if the value is within the col: 

      return solve($cell, value++); 

     if the value is bigger than 9: 

      return solve($cell--, $value_prev); 

     // all test passed, add the new value to list 
     $this->values[$cell] = $value; 

     if all fields are filled: 
      return; 

     if there are fields left: 
      return solve($cell++, 1); 
} 
} 

가 모두 제대로 될 때까지 스크립트는 치명적인 오류와 충돌이 셀에 43을 채울 것입니다 바이트가 고갈되었습니다 (261904 바이트 할당 시도).

숫자가 같은 충전되어

1 2 3 | 4 5 6 | 7 8 9
4 5 6 | 7 8 9 | 1 2 3
7 8 9 | 1 2 3 | 4 5 6
2 1 4 | 3 6 5 | 8 9 7
3 6 5 | 2 1 4 | . . .

무한 루프 또는이 충돌을 일으키는 것으로 추측됩니다. 아마 이런 식으로 해결할 수는 없을 것입니다. 나는 단지 내가 올바르게하고 있는지 또는 내가 잊어 버린 것을 알고 싶었다. 나는 easy-sudoku에서 고정 값으로이 알고리즘을 시도했다. 그것은 너무 추락합니다 ... 아마도 많은 역 추적이있을 것입니다.

마지막으로, 나는 더 나은 해결책을 반대하는 것이 아니라 단지 이것을 원한다고 말하고 싶습니다. 날이 기반으로하는 대답을 할 수없는 경우에는 PHP 파일을 살펴 가질 수

이

sudoku.php

편집 : 사전에 sudoku2.php

감사합니다.

Answer 1

이 주요 문제 :

당신은 (아무것도 작동하지 않습니다 어디 돌아가서 이전에 뭔가를 변경해야하므로), 당신은 당신이로 깊은 재귀 수없는 지점에 도착

if the value is bigger than 9: 
    return solve($cell--, $value_prev); 

, 스택이 너무 커져 실수가 누적되기 때문입니다. 실제로 이전 스택 레벨로 돌아가서 계속 진행해야합니다.

예. solve이 완료되면 TRUE, 그렇지 않은 경우 FALSE을 반환 할 수 있습니다. 그런 다음 solve을 반복적으로 호출 할 때마다 TRUE을 반환하면 TRUE을 반환하고 FALSE을 반환하면 $value++으로 다시 호출합니다.