sudoku solver

스도쿠 해결사

PHP로 작성된 간단한 스도쿠 퍼즐 해결사입니다.

참고: 이 프로젝트는 아직 공사 중입니다.

설치

Sudoku-solver를 설치하려면 프로젝트 루트에서 다음을 실행하세요.

 composer install

술어

 Square      One of the m x n values on the puzzle board
Row         Horizontal M squares
Column      Vertical N squares
Region      An m x n subset of squares
Group       M/N number of squares in a row (horizontally or vertically) 

퍼즐 해결 전략

이 솔버가 사용하는 전략은 Sudoku Dragon에서 설명한 전략을 기반으로 합니다.

전략

퍼즐이 풀릴 때까지 전략을 반복적으로 적용해야 합니다.

1. 유일한 선택 규칙

   • 그룹에서 단일 선택 항목을 찾기 위해 각 행, 열 및 영역을 스캔합니다.

2. 단일 가능성 규칙

   • 그룹에서 단일 선택 항목을 찾기 위해 교차하는 각 행과 열을 검색합니다.

3. 유일한 제곱 법칙

   • 두 개의 빈 셀로 각 행/열을 스캔합니다.
   • 두 개의 누락된 숫자 A와 B를 식별합니다.
   • 교차하는 각 행, 열 또는 영역을 스캔하고 옵션 A를 제거해 보세요.
   • 특정 셀에 대해 옵션 A를 제거할 수 있는 경우 해당 셀에 옵션 B를 입력합니다.
   • 다른 빈 셀에 옵션 A를 입력합니다.

4. 3개 중 2개 규칙

   • 위에서 아래로 한 번에 세 개의 행 또는 열을 스캔하여 1부터 시작하는 특정 숫자를 찾으세요.

5. 하위 그룹 제외 규칙

   • TODO

6. 무차별 대입

   • 해결책을 찾을 때까지 모든 옵션을 시도해 보세요 :)

자원

• https://www.educative.io/edpresso/how-to-check-if-a-sudoku-board-is-valid
• https://puzzling.stackexchange.com/questions/158/how-many-minimal-clue-sudoku-puzzles-are-there
• https://www.technologyreview.com/s/426554/mathematicians-solve-minimum-sudoku-problem/