하스켈 재귀 회귀

Question

좋아, 하스켈에서 스도쿠 해 찾기를 만들려고했지만 예상되는 유형 [[Int]]을 실제 유형 IO()와 일치시킬 수 없다는 오류가 나타납니다.

재귀 찾기 시도 : 내가 유효한에 대한 모든 정의를 포함하는 경우

는

test i j q s_board = if ((valid_row i q s_board)&&(valid_column j q s_board)&& (valid_sub_board i j q s_board)) then (solve (set_value i j q s_board)) else s_board 

foo i j s_board = if ((get_value i j s_board) == 0) then [test i j q s_board | q <- [1..9]] else s_board 

solve s_board = if (full_board s_board) then (print_board s_board) else [foo i j s_board | i <- [0..8], j <- [0..8]] 

이 질문은 매우 긴 것 여기 내 재귀 적 해석에서 시도, 오류 메시지 및 코드의 기타 관련 부분입니다 열, 행 등의 기능을 제공하지만 이러한 기능이 작동하는지 확인했습니다. 내 보드를 인쇄하기 위해 사용하고 코드를 또한 여기

Couldn't match expected type `[[Int]]' with actual type `IO()' 
In the return type of a call of `print_board' 
In the expression: (print_board s_board) 
In the expression: 
    if (full_board s_board) then 
     (print_board s_board) 
    else 
     [foo i j s_board | i <- [0 .. 8], j <- [0 .. 8]] 

있다 :이 코드 나는 다음과 같은 오류 메시지가 받고 있어요

-- showLine: this function provides formating for a single row 
showLine :: [Int] -> String 
showLine = intercalate " | " 
     . map unwords 
     . chunksOf 3 
     . map show 

-- showBoad: this function provides formating for the entire board  
showBoard :: [[Int]] -> String 
showBoard = intercalate "---------------------\n" 
      . map unlines 
      . chunksOf 3 
      . map showLine 


-- print_board: this function is meant to print out the entire board 
print_board :: [[Int]] -> IO() 
print_board s_board = putStrLn $ showBoard s_board 

너희들의 문제 무엇이 보입니까 무엇 나는 지금까지 가지고있다. 저는 하스켈에게 완전히 새로운 것입니다. 그리고 이것은 제가 시도한 최초의 실제 프로그램입니다. 어떤 도움이라도 대단히 감사하겠습니다.

Answer 1

:

print_board s_board = putStrLn $ show $ solve s_board 

다음이 독서에 대한 좋은 다음 단계를 만들 것 :

그래서 당신은 당신의 프로그램 작업의 실제 고기를 가지고하면, 당신은 IO의 혼란을 해결할 수 있습니다 반면,)를 if의 두 가지가 동일한 유형이 있어야하지만

if (full_board s_board) then 
    (print_board s_board) 
else 
    [foo i j s_board | i <- [0 .. 8], j <- [0 .. 8]] 

에 True 분기 IO를 (입력이 False 브랜치는 일 목록 (이 경우 보드) 일 수 있으므로 유형은 [a]입니다 (foo :: Int -> Int -> [[Int]] -> a).

재귀 백 트랙킹은 (전체) 보드 목록을 제공해야하며, solve을 호출하는 다른 컨텍스트에서 인쇄해야합니다.

나의 제안은 그래서 이러한 기능의 각 Grid s의 목록을 반환하고, 막 다른 끝이 도달 할 수있는 솔루션의 빈 목록을 반환하여 제거됩니다

type Grid = [[Int]] 

solve :: Grid -> [Grid] 
solve s_board = if full_board s_board 
        then [s_board] -- full means no branches, singleton list 
        else concat [foo i j s_board | i <- [0 .. 8], j <- [0 .. 8]] 

test :: Int -> Int -> Int -> Grid -> [Grid] 
test i j q s_board 
    | valid_row i q s_board 
     && valid_column j q s_board 
     && valid_sub_board i j q s_board = solve $ set_value i j q s_board 
    | otherwise = [] 

foo :: Int -> Int -> Grid -> [Grid] 
foo i j s_board 
    | get_value i j s_board == 0 = concat [test i j q s_board | q <- [1 .. 9]] 
    | otherwise     = [] 

의 라인을 따라 뭔가 될 것 현재 그리드에서. 막 다른 골목에 진단되지 않았 으면 허용되는 모든 조합을 시도합니다.

그런 다음

solve_and_print :: Grid -> IO() 
solve_and_print s_board = case solve s_board of 
          [] -> putStrLn "Sorry, that board had no solution." 
          (g:_) -> print_board g 

을 가지고 있지만, 그 같은 솔루션을 여러 번을 생산 것이며, 추측의 에브리 조합이 가능한 모든 순서로 할 것이기 때문에 철저한 검색을위한 비효율적 인 몹시, 수 있습니다.

그럼 어떻게 효율적으로 만들 수 있는지 살펴 보겠습니다. 값을 추측하는 다음 위치를 선택하는 알고리즘이있는 경우 결과 목록에서 솔루션의 순열과 반복을 제거 할 수 있습니다. 가장 간단한 알고리즘은 첫 번째 자유 셀을 선택하는 것입니다. 그래서 그리드의 자유 셀을 찾는 함수를 작성하겠습니다. 그리드 방법에 의해, full_board = null . free_cells 전체인지 그와

, 우리는 또한 테스트가 있습니다. 그래서 우리는 우리가

solve :: Grid -> [Grid] 
solve s_board 
    | null frees = [s_board] 
    | otherwise = guesses s_board (head frees) 
     where 
     frees = free_cells s_board 

다음을 해결 시작할 수 있습니다, 우리는 우리가 셀 (i,j)에

possible_values :: Grid -> (Int, Int) -> [Int] 
possible_values s_board (r,c) = [q | q <- [1 .. 9], isPossible s_board q] 
    where 
    isPossible v = valid_row r v s_board 
        && valid_column c v s_board 
        && valid_sub_board r c v s_board 

를 배치하고 셀에 배치하고 진행할 수있는 값을 찾아 더

guesses :: Grid -> (Int, Int) -> [Grid] 
guesses s_board (r,c) = [solution | v <- possible_values s_board (r,c) 
            , solution <- solve $ set_value r c v s_board] 

Answer 2

하스켈을 처음 접하는 경우 Monads을 처리하기 전에 시간을 할애하는 것이 좋습니다. IO에는 모나드가 필요합니다.

먼저 함께 작업 프로그램을 가져와없이 IO 모나드 (putStrLn 등)를 사용하는 것이 좋습니다. 그냥 ghci에 프로그램을로드하고 함수를 호출하면됩니다. 당신이 그것에 익숙해지고 REPL에서 당신에게 답을 줄 수있는 함수가 있다면 STDOUT으로 그것을 출력하는 것에 대해 생각할 수 있습니다. (하스켈은 이것을 해석하기 위해 모스에 대해 약간의 이해를 요구합니다.)

그래서 우선 당신의 solve 기능을 가지고 :

는 solve 그냥하자 - 아니 더. 그래서 그 대신 같은, 바로 여기 IO를하는 :

solve s_board = 
    if (full_board s_board) then (print_board s_board) 
    else [foo i j s_board | i <- [0..8], j <- [0..8]] 

문제 if과 else 절은 동일한 유형이없는 것입니다. else은 [[Int]]을 반환합니다. 단순히 결과를 반환

-- sometimes it helps to be explicit - solve takes a puzzle, returns a solved one. 
solve :: [[Int]] -> [[Int]] 
solve s_board = 
    if (full_board s_board) then s_board    -- type of s_board is [[Int]] 
    else [foo i j s_board | i <- [0..8], j <- [0..8]] -- and so is this 

:와 ifIO 모나드에

변경을 (print_board 의 결과는 하지[[Int]])입니다. 그런 다음 solve을 ghci 안에 넣고 프로그램을 수정하고 작동 할 때까지 다시로드 한 다음 원하는 인수를 사용하여 solve를 호출하고 인쇄하는 함수를 작성하십시오.http://www.haskell.org/tutorial/io.html