카쿠로

Kakuro
쉬운 카쿠로 퍼즐
상기 퍼즐의 해결 방법

Kakuro or Kakkuro or Kakoro (Japanese: カックロ) is a kind of logic puzzle that is often referred to as a mathematical transliteration of the crossword.카쿠로 퍼즐은 전 세계 많은 수학논리 퍼즐 출판물의 일반적인 특징이다.1966년 [1]캐나다인 제이콥 E.풍크, 델 Magazines의 직원인을 크로스 외 같은 다른 이름들 또한 사용되어 온 원래 영어 이름 크로스 Sums[2], 했지만 일본 이름 Kakuro, 일본kasan kurosu(加算クロス,"추가 크로스")의 약어, 퍼즐은 지금은 대부분의 publica에 이처럼라는 제목의 것처럼 보이지만 일반적인 수락이 찐 것 같았다.ti일본에서 카쿠로의 인기는 대단하다.니콜리의 유명한 논리퍼즐 중 스도쿠에 버금간다.[2]

표준 카쿠로 퍼즐은 채워진 세포와 막힌 세포인 "검은색"과 "흰색"의 격자 모양으로 플레이됩니다.퍼즐의 크기는 보통 16×16이지만, 이러한 치수는 매우 다양합니다.맨 위 행과 맨 왼쪽 열은 완전히 검은색이지만 그리드는 검은색 셀에 의해 흰색 셀 라인인 "엔트리"로 구분됩니다.블랙 셀에는 왼쪽 상단에서 오른쪽 하단으로 대각선 슬래시와 한쪽 또는 양쪽 절반에 숫자가 포함되어 있습니다.이렇게 하면 수평 엔트리마다 왼쪽 바로 옆에 검은색 하프 셀에 번호가 표시되고 수직 엔트리마다 그 바로 위에 검은색 하프 셀에 번호가 표시됩니다.크로스워드 용어를 차용한 이 숫자는 일반적으로 "clues"라고 불립니다.

퍼즐의 목적은 각 화이트 셀에 1~9의 숫자를 삽입하여 각 엔트리의 숫자의 합계가 관련된 단서와 일치하고 어떤 엔트리에서도 숫자가 중복되지 않도록 하는 것입니다.그 중복이 부족하기 때문에 독특한 해법으로 카쿠로 퍼즐을 만들 수 있다.스도쿠와 마찬가지로 가쿠로 퍼즐을 푸는 것은 조합과 순열을 조사하는 것을 포함한다.가쿠로 퍼즐에는 수학적으로 숫자 하나만 포함시키는 것은 간단하기 때문에 각 단서가 합산하는 숫자를 2개 이상 가지고 있어야 한다는 불문율이 있다.

적어도 하나의[3] 출판사는 주어진 숫자의 조합을 각 그리드에서 한 번만 사용할 수 있다는 제약을 포함하지만, 여전히 일반 카쿠로로서 퍼즐을 판매한다.

일부 출판사는 검은 셀에 라벨을 붙이지 않고 대신 입력에 번호를 매겨 크로스워드 단서 목록과 같은 단서 목록을 제공하는 등 크로스워드 격자처럼 인쇄하는 것을 선호한다.(이렇게 하면 완전히 검은색인 행과 열이 제거됩니다.)이는 이미지의 문제일 뿐 솔루션이나 해결에 필요한 논리에는 영향을 주지 않습니다.

카쿠로 퍼즐이나 전술에 대해 이야기할 때, 엔트리를 나타내는 일반적인 줄임말은, 「16-in-two」나 「25-in-5」와 같이, 「clue」(숫자)-in-(입력 셀 수)이다.예외는 '45-in-nine'이라고 불리는 것입니다.단순히 '45'가 사용됩니다.이는 "-in-nine"이 수학적으로 암시되기 때문입니다(9개의 셀이 가장 긴 엔트리로, 1개의 자리수를 복제할 수 없기 때문에 1회부터9까지의 모든 자릿수로 구성되어야 합니다).이상하게도, "43-in-8"과 "44-in-8"은 똑같이 암시되어 있음에도 불구하고 여전히 자주 그렇게 불린다.

해결 방법

조합 기술

무차별적인 추측은 가능하지만, 보다 효율적인 접근법은 엔트리가 다양한 단서와 엔트리의 길이에 대해 취할 수 있는 다양한 조합 형식을 이해하는 것입니다.수평합계와 수직합계의 허용 교차를 해결하거나 필요치 또는 결측치를 고려함으로써 솔루션 공간을 줄일 수 있습니다.

길이에 대해 충분히 크거나 작은 단서를 가진 엔트리는 고려할 수 있는 조합이 적어지며, 그것들을 교차하는 엔트리와 비교함으로써 적절한 치환 또는 그 일부를 도출할 수 있습니다.가장 간단한 예는 3-in-2가 4-in-2를 교차하는 경우입니다. 3-in-2는 어떤 순서로 "1"과 "2"로 구성되어야 하며 4-in-2는 어떤 순서로 "1"과 "3"으로 구성되어야 합니다.따라서 이들의 교차는 공통되는 유일한 숫자인 "1"이어야 합니다.

더 긴 합계를 풀 때 정확한 숫자를 찾을 수 있는 단서를 찾을 수 있는 추가 방법이 있습니다.그러한 방법 중 하나는 몇 개의 제곱이 가능한 값을 공유하여 그 합계의 다른 제곱이 이러한 값을 가질 가능성을 제거하는 것이다.예를 들어, 2개의 4-in-two 단서가 더 긴 합계와 교차하는 경우 솔루션의 1과 3은 두 개의 정사각형 안에 있어야 하며 이 [4]합계의 다른 자리에서는 사용할 수 없습니다.

해답 집합의 수가 제한된 합계를 풀 때 유용한 단서가 될 수 있습니다.예를 들어, 7개 중 30개의 합계는 {1, 2, 3, 4, 5, 6, 9}과(와) {1, 2, 3, 4, 5, 7, 8}의 두 가지 솔루션 세트만 포함합니다.만약 그 합계의 제곱 중 하나가 {8,9}의 값만을 취할 수 있다면(예를 들어 교차 단서가 17-in-2의 합인 경우), 그것은 어떤 해 집합이 이 합에 맞는지를 나타내는 지표가 될 뿐만 아니라, 두 값 중 어느 것이 맞는지를 결정하기 전에, 그 합계의 다른 자릿수가 될 가능성을 없앤다.저 광장에서요

더 복잡한 퍼즐에서 또 다른 유용한 접근법은 합계에서 다른 위치를 제거하여 숫자가 어느 정사각형에 들어가는지 확인하는 것입니다.합계의 모든 교차 단서가 많은 가능한 값을 가지지만, 문제의 합계가 가져야 하는 특정 값을 가질 수 있는 정사각형이 하나밖에 없다고 판단할 수 있는 경우, 교차 합계가 허용하는 다른 가능한 값이 무엇이든 간에 그 교차점은 격리된 값이어야 한다.예를 들어, 36-in-8 합계는 9를 제외한 모든 숫자를 포함해야 합니다.두 개의 제곱 중 하나만 2의 값을 가질 수 있다면 이 제곱이 정답이어야 합니다.

박스 기술

"상자 기술"은 또한 해결의 어떤 주어진 단계에서 채워지지 않은 흰색 셀의 기하학적 구조가 그것에 적합할 때 적용될 수 있습니다: 일련의 수평 엔트리에 대한 단서를 합산하고 (그 엔트리에 이미 추가된 숫자의 값을 제외) 대부분 겹치는 수직 엔트리에 대한 단서를 빼냄으로써.그 차이는 부분 엔트리의 값(종종 단일 셀)을 나타낼 수 있습니다.이 기법은 덧셈이 연관성과 가환성을 모두 가지기 때문에 효과가 있습니다.

한 개를 제외한 모든 것이 불가능하다는 것이 증명될 때까지 셀 모서리의 셀에 대한 잠재적 값을 표시하는 것은 일반적인 관행이다; 특히 어려운 퍼즐의 경우, 때때로 셀에 대한 모든 값의 범위가 궁극적으로 교차 엔트리로부터 런을 좁힐 수 있는 그러한 범위에 대한 충분한 제약을 찾기를 희망하여 해결자에 의해 기록된다.단일 값으로 이동합니다.공간 제약으로 인해 일부 솔버는 숫자 대신 위치 표기법을 사용합니다. 여기서 전위 수치는 셀의 특정 부분에 마크로 표시되므로 여러 전위 값을 하나의 셀에 쉽게 배치할 수 있습니다.이를 통해 잠재적 값과 솔루션 값을 더 쉽게 구분할 수 있습니다.

일부 해결사는 또한 그래프 용지를 사용하여 퍼즐 그리드에 쓰기 전에 다양한 숫자 조합을 시도합니다.

스도쿠의 경우와 같이, 상기의 기술에서는 비교적 쉬운 가쿠로 퍼즐만을 풀 수 있다.어려운 것은 스도쿠에서 볼 수 있는 것과 같은 종류의 다양한 체인 패턴을 사용할 필요가 있다(패턴 기반 제약 만족도 및 논리[5] 퍼즐 참조).

카쿠로의 수학

수학적으로 가쿠로 퍼즐은 정수 프로그래밍 문제로 표현될 수 있으며 NP-완전이다.[6]「Yato and Seeta, 2004」[7]도 참조해 주세요.

가쿠로 퍼즐에는 두 가지 수학적 대칭이 있다.최소 구속조건과 최대 구속조건은 결측값과 필수값과 마찬가지로 이중 구속조건이다.

모든 합계의 조합은 비트맵 표현을 사용하여 나타낼 수 있습니다.이 표현은 비트 논리 연산을 사용하여 결측값 및 필수값을 판별하는 데 유용합니다.

인기

가쿠로 퍼즐은 거의 100개의 일본 잡지나 신문에 실린다.1992년 스도쿠가 [8]1위를 차지할 때까지 가쿠로는 일본 인쇄 매체에서 가장 인기 있는 논리 퍼즐로 남아 있었다.영국에서, 그들은 가디언 위드 텔레그래프와 데일리 메일에 [9]처음 등장했다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Timmerman, Charles (2006). The Everything Kakuro Challenge Book. Adams Media. p. ix. ISBN 9781598690576. Retrieved November 18, 2018.
  2. ^ a b "Kakuro history". Retrieved November 18, 2018.
  3. ^ "Sudoku From Denksport". Keesing Group B.V. Retrieved November 18, 2018.
  4. ^ "Kakuro rules". Retrieved November 18, 2018.
  5. ^ Berthier, Denis (April 5, 2013). "Pattern-Based Constraint Satisfaction and Logic Puzzles". arXiv:1304.1628 [cs.AI].
  6. ^ Takahiro, Seta (February 5, 2002). "The complexities of puzzles, cross sum and their another solution problems (ASP)" (PDF). Retrieved November 18, 2018.
  7. ^ Yato, Takayuki; Seta, Takahiro (2004). "Complexity and Completeness of Finding Another Solution and Its Application to Puzzles" (PDF). Retrieved November 18, 2018. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  8. ^ "What is Kakuro". Retrieved November 18, 2018.
  9. ^ "Kakuro History". Retrieved November 18, 2018.

외부 링크

Wikimedia Commons에는 Kakuro와 관련된 미디어가 있습니다.