"사각형"프롤로그

Question

논리 수수께끼 해결

"사각형"

입력 : N ×

보드 사이즈 m (m, n은 ∈ {1, ...이, 32}) 트리플 목록 (0, ..., (n-2) · (m-2)}))을 기술하고, 여기서 ∈ {1, ..., m}이라면, (i, j, k)이다. 숫자가있는 필드.

출력 : 해결 수수께끼를 보여주는 트리플 (i, j, d)의

목록. 트리플 (i, j, d)은 좌표가 (i, j) 및 (i+d, j+d) 인 반대 정점을 갖는 정사각형을 설명합니다.

예 :

입력 :

7. 7. [(3,3,0), (3,5,0), (4,4,1), (5,1,0), (6,6,3)].

출력 :

[(1,1,2), (1,5,2), (2,2,4), (5,1,2), (4,4,3)] 

이미지 :

설명 :

I have to find placement for x squares(x = fields with numbers). On the circuit of the each square, exactly at one of his corners should be only one digit equal to amount of digits inside the square. Sides of squares can't cover each other, same as corners. Square lines are "filling fields" so (0,0,1) square fills 4 fields and have 0 fields inside.

나는 프롤로그에서이 수수께끼에 대한 솔루션을 코딩 약간의 도움이 필요합니다. 누군가 올바른 방향으로 나를 안내 할 수 있습니까? 어떤 술어, 규칙을 사용해야합니까.

Answer 1

Naimads의 생명력을 저축 할 가치가 있기 때문에 (!) 다음은 좀 더 지침적인 도움입니다.

프로그래머는 bottomp-up ("하위"수준의 기능부터 시작하여 전체 응용 프로그램까지) 또는 top-down (높은 수준의 "셸"기능을 시작으로) 프로젝트를 수행하는 경향이 있습니다. 입/출력이 가능하지만 이후의 세분화를 위해 솔루션 처리가 스텁 됨).

어느 쪽이든 나는 Ruby 프로그래밍 공동체에 의해 옹호 된 프롤로그 프로그래밍에 대한 접근법을 추천 할 수 있습니다 : Test Driven Development.

높은 기능과 낮은 기능을 몇 가지 선택하고이 철학이 어떻게 도움이되는지 토론합시다.

프롤로그의 상위 수준 조건자는 모든 입력 및 출력 인수를 취하여 의미 론적으로 문제를 정의하는 구문입니다. 우리는 용액 공정이 구현 얻을 것이다 방법으로 어떤 치료를 포기하지 않고 이러한 조건을 쓸 수 있습니다 : 우리가 문제를 프레임 한 지금까지

/* squaresRiddle/4 takes inputs of Height and Width of a "board" with 
    a list of (nonnegative) integers located at cells of the board, and 
    produces a corresponding list of squares having one corner at each 
    of those locations "boxing in" exactly the specified counts of them 
    in their interiors. No edges can overlap nor corners coincide. */ 
squaresRiddle(Height,Width,BoxedCountList, OutputSquaresList). 

합니다. 유용한 진전은 주석에 의해 주어지며 (높은 수준에서 입력 및 출력을 명확하게 정의 함),이 시점의 코드는 어떤 인수가 전달 되더라도 "성공"을 보장합니다.따라서이 코드의 "테스트"는 다음과 같습니다 :

무료 변수를 제외하고는 아무것도 생성되지 않습니다.

다음은 입력 목록과 출력 목록을 나타내는 방법에 대해 생각해 보겠습니다. 질문에서 정수의 세배를이 목록의 항목으로 사용하는 것이 좋습니다. 그 대신에 이름이 지정된 펑터를 사용하는 것이 좋습니다. 왜냐하면 입력 삼중 항의 의미 (셀의 x, y 좌표에 개수를 지정)가 출력 트리플의 의미와 미묘하게 다르기 때문입니다 (왼쪽 위 모서리의 x, y 좌표 부여 및 사각형의 "범위"(높이 : & 너비). 입력 사안의 항목이 출력 정사각형의 네 모퉁이 중 하나 여야 만하지만 출력 사각형은 해당 입력 항목의 구석과 다른 구석으로 설명 될 수 있습니다.

이렇게 간단한 구문 분석기 이름으로 구.을 구별하면 코드를보다 쉽게 ​​읽을 수 있습니다. BoxedCountList = [box(3,3,0),box(3,5,0),box(4,4,1),box(5,1,0),box(6,6,3)] 대 OutputSquaresList = [sqr(1,1,2), sqr(1,5,2), sqr(2,2,4), sqr(5,1,2), sqr(4,4,3)].

솔루션 검색 방법을 조금 생각해 봅시다. 출력 항목은 입력 항목과 1 대 1로 대응하므로 목록의 끝에 길이가 동일하게됩니다. 그러나 k 번째 출력 항목을 선택하는 것은 k 번째 입력 항목뿐만 아니라 모두 입력 항목 (출력 칸의 내부에 몇 개가 있는지 계산하기 때문에)과 앞의 출력 항목에 따라 달라집니다. 만나고 겹치는 모서리).

이 요구 사항과 일치하는 의사 결정의 흐름을 관리하는 데는 여러 가지 방법이 있으며 한 가지 방법을 선택하여 작동시키는 것이이 연습의 요점 인 것 같습니다. difference lists 또는 accumulators에 익숙하다면 먼저 할 수있는 방법이 있습니다.

이제 더 낮은 수준의 기능에 대해 논의하겠습니다. 입력이 box이라면 그에 상응하는 많은 수의 출력이있을 수 있습니다. sqr. 출력에 대해 양의 "범위"가 주어지면 X,Y 입력 좌표는 출력 사각형의 네 모서리 중 하나와 만날 수 있습니다. 해결책을 확인하기 위해 더 많은 검사가 필요하지만이 부분은 테스트를 시작하기에 좋은 장소 인 것 같습니다.

/* check that coordinates X,Y are indeed a corner of candidate square */ 
hasCorner(sqr(SX,SY,Extent),X,Y) :- 
    (SX is X ; SX is X + Extent), 
    (SY is Y ; SY is Y + Extent). 

이 테스트는 어떻게 사용합니까? 우리는 가능한 모든 사각형을 생성 할 수 있습니다 (아마도 "보드"의 높이와 너비에 맞는 것들로 제한 할 수 있습니다). 그리고 나서 꼭 필요한 코너가 있는지 확인하십시오. 이것은 상당히 비효율적 일 수 있습니다. 더 나은 방법은 (능률이 올라가는 한) 모서리를 사용하여 보드 크기의 매개 변수에 따라 가능한 사각형을 생성합니다 (네 방향 중 하나에서 모서리에서 연장하여 Extent). 이 "최적화"구현은 독자를위한 연습으로 남겨 둡니다.