GN⁺: 아서 휘트니의 원라이너 Sudoku 솔버 (2011)

스도쿠 문제 해결 알고리듬

• 스도쿠 문제 설명

  • 스도쿠 퍼즐은 3×3 그리드의 3×3 박스로 구성되며, 각 셀은 비어 있거나 1에서 9 사이의 숫자를 포함함.
  • 각 3×3 박스, 9개의 행, 9개의 열에 중복 없이 9개의 숫자가 포함되어야 함.
  • 예시 문제와 해결 방법이 제공됨.

• 알고리듬 개요

  • 행렬을 벡터로 처리하여 행, 열, 스도쿠 영역을 인덱스 벡터로 표시함.
  • 퍼즐의 기본 검사를 수행하고, 가능한 요소를 필터링하여 해결책을 찾음.
  • 셀이 비어 있으면 다음 목록으로 이동하고, 셀에 여러 숫자가 포함되면 가장 좁은 그룹에서 선택하여 목록에 추가함.
  • 모든 셀이 하나의 숫자를 포함하면 해결책을 찾은 것임.

• 기술적 노트

  • Veli-Matti Jantunen이 제공한 솔루션으로, 스도쿠 직사각형을 나타내기 위해 ⍺를 사용할 수 있음.
  • 결과는 모든 해결책의 벡터, 없으면 ⍬, 오류가 있으면 ''를 반환함.
  • 알고리듬은 간단하며, 행렬을 벡터로 처리하고, 가능한 요소를 필터링하여 해결책을 찾음.

• 다른 접근 방식

  • David Crossley와 Arthur Whitney의 대안 코딩이 제공됨.
  • 다양한 코딩 스타일과 접근 방식이 설명됨.

• 예시 및 활용

  • 스도쿠 문제를 해결하는 다양한 예시가 제공됨.
  • 스도쿠 문제를 쉽게 읽을 수 있도록 내부 박스를 분리하는 함수도 제공됨.

GN⁺의 정리

• 스도쿠 문제 해결을 위한 다양한 알고리듬과 코딩 스타일이 소개됨.
• 스도쿠 퍼즐은 논리적 사고와 문제 해결 능력을 향상시키는 데 유용함.
• 다양한 접근 방식을 통해 문제 해결의 유연성을 높일 수 있음.
• 스도쿠와 유사한 기능을 가진 퍼즐로는 Kakuro, KenKen 등이 추천됨.

[neo]

Hacker News 의견

• K 언어는 APL과 Scheme을 기반으로 Arthur Whitney가 만든 언어로, 속도, 배열 처리 능력, 표현력 있는 문법이 강조됨
• 코드 복잡도를 측정할 때 코드 줄 수와 압축 정도를 비교함
  • APL 코드는 압축된 이진 데이터처럼 느껴지며, 이를 이해할 수 있는 사람들에게 감명을 받음
• 코드 줄 수는 언어마다 다르게 사용되므로 좋은 측정 기준이 아님
  • 구문 트리의 노드 수와 깊이, 분기 요소를 고려하는 것이 더 나은 측정 방법임
• 문제의 명확성이 중요하며, Iversonian 언어(J와 K 포함)는 다른 언어와 차별화됨
  • 한 줄 해결책은 놀랍고, 배열을 효율적으로 설명하고 수행하는 데 유용함
• K 프로그램은 QED로 끝나야 한다는 의견이 있으며, KQED와의 연관성을 궁금해함
  • KQED는 Bay Area의 PBS 파트너임
• APL/k 같은 언어가 문제를 더 효율적으로 생각할 수 있게 하는지 궁금해함
• APL과 배열 언어를 배우는 것이 다른 언어에 도움이 되었지만, 일상적으로 사용하지 않게 됨
  • APL은 특정 문제 해결 방법을 모르면 해결이 어려움
• 일부 알고리즘 디자인 핸드북에서 본 비효율적인 해결책보다 나은 해결책이 있음
  • 2015년에 이에 대한 블로그 게시물을 작성함
• Scryer Prolog를 사용한 Sudoku 해결책은 읽기 쉽고 강력하며, 제약 해결 기능이 뛰어남
  • Scryer Prolog는 현대적이고 성능이 뛰어난 ISO 준수 Prolog임