예전 자유 게시판

[프로그래머 두뇌 단련 퍼즐 44제] 스도쿠 풀이 알고리즘 specsud() 오류

comkid 2008-04-07 23:04

프로그래머 두뇌 단련 퍼즐 44제의 스도쿠 문제 풀던 도중에 의사코드에 오류가 있어 리포트 드립니다.

p.178에 가설-검증 추론을 이용한 스도쿠 풀이 의사코드 specsud()가 있는데요

proc specsud(state s)
    s' := basicsud(s)
    if (s' == "일관되지 않은 상태") then
        return "일관되지 않은 상태"
    endif
    if (s'이 완성된 상태이면) return s'
    else
        s'의 빈칸들 중 가능한 값이 둘 이상인
        빈칸들의 집합을 R이라고 하자
        for ( R의 각 빈칸 e에 대해)
            e에 대해 가능한 값들의 집합을 V라고 할 때
            for( V의 값 값 v에 대해)
                s'을 상태 저장 스택에 넣는다
                s'' := s'에서 e에 v를 배정한 상태
                s''' := specsud(s'')
                if ( s'''이 완성된 상태이면)
                    return s'''
                endif
                스택에서 s'을 뽑는다
            end for
        end for
    end if
end proc specsud

에서 for( V의 값 값 v에 대해) .. end for 부분에서 모든 v (∈V)를 적용한 가설들이 모두 잘못된 경우 for문을 빠져나오게 되는데 이 경우 "일관되지 않은 상태"를 리턴해야 맞을 것 같은데 위 의사코드 대로면 적용할 수 있는 값이 없는데도 다음 칸으로 이동하여 값을 적용하게 됩니다.

이런 식으로 수정되어야 맞을 것 같습니다.

        for ( R의 각 빈칸 e에 대해)
            e에 대해 가능한 값들의 집합을 V라고 할 때
            for( V의 값 값 v에 대해)
                s'을 상태 저장 스택에 넣는다
                s'' := s'에서 e에 v를 배정한 상태
                s''' := specsud(s'')
                if ( s'''이 완성된 상태이면)
                    return s'''
                endif
                스택에서 s'을 뽑는다
            end for
            return "일관되지 않은 상태"  // 빈칸 e에 들어갈 수 있는 값이 V에 존재하지 않음
        end for

제가 원서는 보질 않아서 누락된 것인지 아니면 실제 같은 오류가 있는지는 잘 모르겠네요. 페이지가 넘어가는 지점이라 누락 되었을 수도 있을 것 같고요.

처음 의사코드대로 구현했다가 결과가 계속 나오질 않아서 자기 전에 돌려놨는데 아침까지도 결과가 나와있지 않더군요. 책 대로라면 최신 PC에서 3초 안에 결과가 나와야 하는데 제가 뭘 잘 못한지 알고 꽤나 좌절했습니다;

확인 부탁드립니다.
그리고 좋은 책 많이 번역해주셔서 감사합니다. :)
(다 소화해내지 못하는 자신이 원망스러울뿐...)

ps. 혹시 이미 리포트 된 내용인지 모르겠네요? (일단 게시판에서는 못 본 것 같은데..)