스도쿠 해결 알고리즘

표준 스도쿠는 9×9 격자로 81개의 셀을 포함하고 있으며 9개의 박스를 가지고 있으며 각 박스는 1열, 중간 또는 마지막 3열과 1열, 중간 또는 마지막 3열의 교차점이 된다.각 셀은 1부터 9까지의 숫자를 포함할 수 있으며, 각 숫자는 각 행, 열, 상자에 한 번만 발생할 수 있다.스도쿠는 숫자(클러지)를 포함한 일부 세포로 시작하며, 목표는 남은 세포들을 해결하는 것이다.제대로 된 수도쿠스는 하나의 해결책이 있다.플레이어들과 수사관들은 광범위한 컴퓨터 알고리즘을 사용하여 수도쿠스를 풀고, 그들의 속성을 연구하며, 흥미로운 대칭과 다른 성질을 가진 수도쿠스를 포함한 새로운 퍼즐을 만든다.

9×9 퍼즐(n=9)을 1초 분량으로 풀 수 있는 컴퓨터 알고리즘이 여러 개 있지만, n이 증가하면서 콤비네이터 폭발이 일어나 n이 증가하면 구성하고 분석하고 해결할 수 있는 스도쿠스의 속성에 한계가 생긴다.

기술

역추적

일부 취미 활동가들은 강제 수색의 일종인 역추적 알고리즘을 이용해 스도쿠 퍼즐을 푸는 컴퓨터 프로그램을 개발했다.^[2]역추적(backtracking)은 다른 지점으로 이동하기 전에 가능한 해결책에 대해 한 가지를 완전히 탐색하기 때문에(넓은 선 검색과는 대조적으로) 깊이 우선 검색이다.대략 5.96 x 11²⁶ 최종 그리드가 존재한다는 것이 확인되었지만, 브뤼트 포스 알고리즘은 스도쿠 퍼즐을 푸는 실용적인 방법이 될 수 있다.

브루트 포스 알고리즘은 빈 셀을 어떤 순서로 방문하여 순차적으로 숫자를 채우거나 숫자가 유효하지 않은 것으로 판명될 때 역추적한다.^[3][4][5][6]간단히 말해서, 프로그램은 첫 번째 셀에 숫자 "1"을 배치하고 그것이 그곳에 있을 수 있는지 확인함으로써 퍼즐을 풀 것이다.위반(열, 열 및 상자 제약 확인)이 없는 경우 알고리즘은 다음 셀로 이동하여 해당 셀에 "1"을 배치한다.위반 여부를 확인할 때 "1"이 허용되지 않는 것으로 확인되면 값이 "2"로 진전된다.9자리 숫자 중 어느 것도 허용되지 않는 곳에서 셀이 발견되면 알고리즘은 해당 셀을 공백으로 두고 이전 셀로 다시 이동한다.그리고 나서 그 세포의 값은 1씩 증가한다.이는 마지막(81번째) 셀에서 허용된 값이 발견될 때까지 반복된다.

이 애니메이션은 스도쿠가 어떻게 이 방법으로 해결되는지를 보여준다.알고리즘이 가능한 해결책으로 각각의 미해결 셀을 시험하는 동안 퍼즐의 단서(빨간 숫자)는 고정된 상태로 남아 있다.알고리즘이 기존 집합이 스도쿠의 제약을 충족하지 못하는 것을 발견하면 이전에 테스트한 모든 값을 폐기할 수 있다는 점에 유의하십시오.

이 방법의 장점은 다음과 같다.

• 해결책은 보장된다(퍼즐이 유효한 한).
• 시간을 푸는 것은 대부분 난이도와 무관하다.
• 알고리즘(따라서 프로그램 코드)은 특히 가장 어려운 퍼즐에 대한 해결책을 보장하는 강력한 알고리즘에 비해 다른 알고리즘보다 간단하다.

이 방법의 단점은 연역적 방법을 모델로 한 알고리즘에 비해 해결 시간이 느릴 수 있다는 점이다.한 프로그래머는 그러한 알고리즘이 일반적으로 스도쿠를 해결하기 위해 적게는 15,000 사이클, 많게는 90만 사이클이 필요할 수 있다고 보고했는데, 각 사이클은 스도쿠의 세포를 통해 이동하면서 "점자"의 위치가 바뀌는 것이다.^[7][8]

스도쿠는 역추적을 막기 위해 건설될 수 있다.해결사가 위에서 아래로 (애니메이션에서처럼) 작동한다고 가정하면, 맨 위 줄에 단서가 거의 없고, 단서가 없는 퍼즐(17)이 알고리즘과 반대로 작동하게 된다.따라서 이 프로그램은 퍼즐을 만족시키는 그리드에 도달하기 전에 "계수"를 증가시키는 데 상당한 시간을 할애할 것이다.한 경우에 프로그래머는 그러한 스도쿠를 위한 해결책에 도달하는데 6시간이 걸리는 짐승 같은 힘 프로그램을 발견했다.이러한 스도쿠는 오늘날 철저한 검색 루틴과 더 빠른 프로세서를 사용하여 1초도 안 되는 시간에 해결할 수 있다.^{[citation needed]}

확률적 검색/최적화 방법

스도쿠는 확률적(랜덤 기반) 알고리즘을 이용해 해결할 수 있다.^[9][10]이 방법의 예는 다음과 같다.

1. 그리드의 빈 셀에 숫자를 임의로 할당하십시오.
2. 오차 수를 계산한다.
3. 삽입된 숫자를 실수 횟수가 0으로 줄어들 때까지 " 섞어라"

그리고 나서 퍼즐의 해결책이 발견된다.숫자를 섞기 위한 방법에는 시뮬레이션된 어닐링, 유전 알고리즘 및 타부 검색이 포함된다.확률 기반 알고리즘은 연역 기술만큼 빠르지는 않지만 빠른 것으로 알려져 있다.그러나 후자와는 달리 최적화 알고리즘은 반드시 문제를 논리적으로 해결할 필요가 없으므로 더 광범위한 문제를 해결할 수 있는 잠재력을 제공한다.그래프 착색용으로 설계된 알고리즘은 수도쿠스에서도 잘 작동하는 것으로 알려져 있다.^[11]스도쿠를 정수 선형 프로그래밍 문제로 표현하는 것도 가능하다.그러한 접근법은 해결책에 빠르게 접근하고, 그리고 나서 끝을 향해 분기하는 것을 사용할 수 있다.심플렉스 알고리즘은 스도쿠스가 유효하지 않은지(해결책이 없음)를 나타내는 적절한 스도쿠스를 해결할 수 있다.둘 이상의 솔루션(비속성 수도쿠스)이 있는 경우, 심플렉스 알고리즘은 일반적으로 일부 사각형에서 소수점 이상의 비율로 솔루션을 산출한다.그러나 적절한 수도쿠스의 경우, 선형 프로그래밍 프리솔브 기법만으로도 간단한 반복 없이 솔루션을 추론할 수 있을 것이다.LP문제의 축소를 위해 선행기술이 사용하는 논리규칙에는 인간이 수도쿠스를 해결하기 위해 사용하는 논리규칙이 포함되어 있다.

제약 프로그래밍

스도쿠는 제약 만족도 문제로 모델링될 수도 있다.헬무트 사이몬리스는 그의 논문 '제약 문제'에서 모델과 문제 해결에 적용할 수 있는 제약조건에 기초한 많은 추론 알고리즘을 기술하고 있다.^[12]일부 제약 해결사에는 수도쿠스를 모델링하고 해결하는 방법이 포함되어 있으며, 프로그램은 단순한 수도쿠를 해결하기 위해 100줄 미만의 코드가 필요할 수 있다.^[13][14]만약 코드가 강력한 추론 알고리즘을 채택한다면, 역추적 통합은 가장 어려운 수도쿠스에 대해서만 필요하다.제약조건 모델 기반 알고리즘과 역추적을 결합한 알고리즘은 빠른 해결 시간(몇 밀리초^[15] 순서)과 모든 수도를 해결할 수 있는 능력을 가지고 있다.^[16]

정확한 표지

스도쿠 퍼즐은 정확한 표지 문제로 묘사될 수 있다.이것은 문제에 대한 우아한 설명과 효율적인 해결책을 가능하게 한다.스도쿠를 정확한 커버 문제로 모델링하고 크누스의 알고리즘 X와 같은 알고리즘을 사용하면 몇 밀리초 안에 스도쿠를 해결할 수 있다.^{[citation needed]}대안적 접근방식은 기둥과 행 스트라이크를 조합하여 가우스 제거를 사용하는 것이다.

관계 및 잔차

Q를 9x9 스도쿠 행렬로 하고, N = {1, 2, 3, 4, 5, 6, 7, 8, 9}, X는 일반적인 행, 열 또는 블록을 나타낸다.N은 Q를 채우기 위한 기호와 X의 9개 요소에 대한 인덱스 세트를 제공한다.Q의 주어진 요소 Q는 Q에서 N까지의 부분 함수를 나타낸다.솔루션 R은 전체 관계로서 기능이다.스도쿠 규칙은 R에서 X까지의 제한은 편향이라고 규정하고 있으므로 X로 제한되는 모든 부분적 해결책 C는 N의 부분 순열이다.

Let T = {X : X는 Q}의 행, 열 또는 블록이기 때문에 T는 27개의 요소를 가진다.약정은 부분 순열 또는 N에 대한 순열이다. Z를 N에 대한 모든 약정의 집합으로 한다. 부분 해결책 C는 양립 가능한 약정이 필요한 A(1 대 3)와 B의 구성으로 규칙을 포함하도록 개정할 수 있다.

${\displaystyle Q\xrightarrow {A}T\xrightarrow {B}Z\quad {\text{with}}\quad A;B\subseteq C.}$

퍼즐의 해결책, 새로운 Q에 대한 제안은 QxZ에서 C의 보완책인 금지약정 $C$의${\displaystyle \stackrel{}{},}${\$displaystyle {\c},}$에서 나온 것이다$.$ 관계의 미적분학에서 유용한 도구는 다음과 같다.

${\$$T$$};{\bar {{C}}}$ 맵 T에서 Z까지 및

$'{\$T$}}}$ 지도$$ Q~T.

수도쿠스 개발(검색)

17개의 단서와 대각선 대칭을 가진 스도쿠.

18개의 단서와 2방향 대각선 대칭이 있는 자동형 스도쿠.

비슷한 무늬의 17개의 단서 스도쿠. (오렌지 서클: 단서 제거, 녹색 서클: 단서 추가, 파란색 밑줄: 다른 숫자).

18개의 단서 스도쿠. (수평 대칭).

컴퓨터 프로그램은 단서 수가 적거나 대칭의 특정한 유형과 같은 특정한 성질을 가지고 수도쿠스를 "검색"하는 데 종종 사용된다.17개의 단서를 가진 4만 9천 개가 넘는 수도쿠스가 발견되었지만, 발견되지 않은 수도쿠스가 희귀해지면서 새로운 뚜렷한 새로운 수도쿠스(기존 알려진 수도쿠스의 변형이 아닌)를 발견하는 것은 더욱 어려워지고 있다.^[17]

특정한 특징을 가진 수도쿠스를 찾는 한 가지 일반적인 방법은 이웃 찾기라고 불린다.이 전략을 사용하여, 검색되는 특성을 만족시키거나 거의 만족시키는 하나 이상의 알려진 수도쿠스가 출발점으로 사용되며, 이러한 수도쿠스는 그 재산을 찾는 다른 수도쿠스를 찾기 위해 변경된다.그 변화는 하나 이상의 단서 위치를 재배치하거나, 소수의 단서들을 제거하고, 다른 수의 단서로 대체하는 것일 수 있다.예를 들어, 알려진 스도쿠로부터, 하나의 실마리를 덜 가진 새로운 실마리를 찾는 것은 두 개의 실마리를 제거하고 새로운 장소에 하나의 실마리를 추가하는 방법으로 행해질 수 있다.(이것은 {-2,+1} 검색이라고 할 수 있다.)각각의 새로운 패턴은 하나 또는 그 이상이 유효한 스도쿠(즉, 해결할 수 있고 하나의 해결책이 있을 수 있다)를 산출한다는 희망으로 모든 단서 값의 조합에 대해 철저히 검색될 것이다.본질적으로 동등한 수도쿠스가 중복적으로 시험되는 것을 방지하기 위한 방법도 채택할 수 있다.

구체적인 예로서, 17클루 스도쿠에 대한 검색은 알려진 18클루 스도쿠에서 시작하여 3개의 단서를 제거하고 단 2개의 단서로 교체함으로써 변경할 수 있다(마지막 두 개의 이미지 참조).이것은 새로운 수도쿠스를 발견할지 모르지만, 그들이 이미 알려진 수도쿠스와 본질적으로 다르다는 즉각적인 보장은 없을 것이다.만일 진정으로 새로운 (발견되지 않은) 수도쿠스를 찾는다면, 각각의 발견이 이미 알려진 수도쿠의 변형이 아니라는 것을 확실히 하기 위해 추가적인 확인이 필요할 것이다.^{[18][better source needed]}

참고 항목

• 스도쿠
• 스도쿠의 수학
  • § 단서가 거의 없는 수도쿠스(최소 기븐 수)
  • § 오토모픽 수도쿠스
• 콤비네이터 폭발 (라틴 사각형 대비 스도쿠 격자수 요약)
• 스도쿠의 용어집

참조

외부 링크

• http://diuf.unifr.ch/pai/people/juillera/Sudoku/Sudoku.html 니콜라스 줄리어트의 스도쿠 설명자(일반적으로 스도쿠스 등급으로 인기)
• 글렌 파울러의 http://gsf.cococlyde.org/download/sudoku 스도쿠 (다른 것 중에서 가장 어려운 스도쿠스의 등급을 매긴 것으로 인기)
• 스도쿠 퍼즐을 푸는 연필과 종이 알고리즘