Erlang 스도쿠 해결사 - 빈 자리를 찾아 가능한 값을 재귀 적으로 찾는 방법

Question

나는 어제와 오늘 얼랑 (Erlang)에서 스도쿠 해결사로 바빴습니다. 내가 지금 가지고있는 작업 기능 목록, 예를 들면 형태의 스도쿠,

[6,7,1,8,2,3,4,9,5,5,4,9,1,7,6,3,2,8,3,2,8,5,4,9,1,6,7,1,3,2,6,5,7,8,4,9,9,8,6,4,1,2,5,7,3,4,5,7,3,9,8,6,1,2,8,9,3,2,6,4,7,5,1,7,1,4,9,3,5,2,8,6,2,6,5,7,8,1,9,3,4]. 

가 제약에서 (사각형, 행 및 컬럼에는 중복을)보고하지가 유효인지 아닌지 내가 확인 할 수 있다는 것입니다 .

이 함수는 스도쿠 S를 취하여 유효한 스도쿠이면 true를 반환하고 그렇지 않으면 false를 반환합니다. 이 함수는 빈 값을 나타내는 데 사용되는 0을 무시합니다.

이

[0,7,1,8,2,3,4,0,5,5,4,9,0,7,6,3,2,8,3,0,8,5,0,9,1,6,7,1,3,2,6,5,7,8,4,9,0,8,6,4,1,2,5,7,0,4,5,7,3,9,8,6,1,0,8,9,3,2,6,4,7,5,1,7,1,4,9,3,0,2,8,6,2,6,5,7,8,1,9,3,4]. 

다음 단계는 목록의 첫 번째 공을 발견하고 유효한 스도쿠를 생산하는 경우 (1 ~ 9)에서 값을 시도하고 확인하는 것입니다 : 이것은 어떤 임의의 빈 값과 같은 스도쿠의 예입니다 . 만약 그렇다면 우리는 다음 0을 계속해서 거기에있는 값을 시도하고 유효한지 확인하십시오. 일단 우리가 더 이상 갈 수 없으면 우리는 이전의 0으로 돌아가서 우리가 해결 된 스도쿠로 끝날 때까지 다음 값 등을 시도합니다.

지금까지 다음과 같습니다 한 코드는 (그것을 가지고 사람이 거의 작업 기준) :

solve(First,Nom,[_|Last]) -> try_values({First,Nom,Last},pos()). 

try_values(_,[]) -> {error, "No solution found"}; 
try_values({First,Nom,Last},[N|Pos]) -> 
    case valid(First++[N]++Last) of 
    true -> 
     case solve({First++[N]},Nom,Last) of 
     {ok,_} -> {ok, "Result"}; 
     {error,_} -> try_values({First,N,Last},Pos) 
     end; 
    false -> try_values({First,N,Last},Pos) 
    end. 

POS()을 아이디어는 점이다 9. 1에서 값으로 구성된 목록입니다 First에 대한 빈 목록과 [_ | Last]에 대한 Sudoku 목록을 입력하여 0 (Nom?)을 찾습니다. 그런 다음 우리는 가치를 시험해보고 그 결과에 해당하는 목록이 우리의 기능에 따라 유효하다면 우리는 그 직책에 실패하거나 결과를 얻을 때까지 계속됩니다. 우리가 실패하면 우리의 가능성의 나머지 (Pos) 값을 가진 새로운 try_values를 반환합니다.

당연히,이 일을하고 반환하지 않습니다

5> sudoku:solve([],0,S). 
** exception error: bad argument 
    in operator ++/2 
     called as {[6]} 
        ++ 
        [1,1,8,2,3,4,0,5,5,4,9,0,7,6,3,2,8,3,2,8,5,4,9,1,6,7,1,3,2|...] 
    in call from sudoku:try_values/2 (sudoku.erl, line 140) 
    in call from sudoku:try_values/2 (sudoku.erl, line 142) 

을 내 경험 부족으로 내가 코드의 논리와 작업하기 위해해야 ​​할 일을 파악 할 수 없다. 더 많은 경험을 가진 사람이 나에게 몇 가지 조언을 해줄 수 있다면 정말 고마워.

Answer 1

try_values([], []) -> error("No solution found"); 
try_values([Solution], []) -> Solution; 
try_values(_, []) -> error("Bad sudoku: multiple solutions"); 
try_values(Heads, [0|Tail]) -> 
    NewHeads = case Heads of 
        [] -> [[P] || P <- pos()]; 
        _ -> [Head++[P] || P <- pos(), Head <- Heads] 
       end, 
    ValidHeads = [Head || Head <- NewHeads, valid(Head++Tail)], 
    try_values(ValidHeads, Tail); 
try_values([], [H|Tail]) -> try_values([[H]], Tail); 
try_values(Heads, [H|Tail]) -> try_values([Head++[H] || Head <- Heads], Tail). 

solve(Board) -> 
    case valid(Board) of 
     true -> try_values([], Board); 
     false -> error("No solution found") 
    end. 

try_values 당신이 설명한 것을 않습니다. Board을 거쳐 0을 찾아 솔루션을 모으기 위해 가능한 모든 솔루션 (pos())을 시도하고 계속하려면 더 많은 정보를 전달하여 솔루션을 구축합니다. 따라서 가능한 모든 방법이 있습니다. 어떤 시점에 복수 valid 스도쿠가있는 경우 모두 Heads에 추가되고 다음 단계에서 valid으로 테스트됩니다. solve은 try_values([], Board)을 호출하기위한 래퍼입니다.

기본적으로, iterate recursively over 0's하는 방법은 모든 비 - 제로 (2 마지막 try_values 표현)를 생략하고 제로에서 작업 (제 4 try_values 표현을)하는 것입니다.

첫 번째 세 개의 try_values 표현식은 해가 존재하는지 확인하고 그 결과를 반환합니다.