스도쿠 판을 생성하고자 합니다.


먼저 다음 알고리즘으로는 잘 안 됩니다.

각 81개의 세포에 {1, 2, ..., 9}를 후보로 두고,

하나의 세포 c를 선택하여 그것의 후보 중에 하나 e를 당선시키고,

c가 속한 행, 열, 그리고 네모에 속한 다른 세포들의 후보 고른 후보 중에서 e를 빼는 방법입니다.

이렇게 하면 후보의 갯수가 0이 되어버리기도 합니다.

후보의 개수가 1일 때 당선시키도록 하면, 스도쿠 규칙을 어기는 경우가 생깁니다.


그래서 생각해 낸 방법이 섞기 입니다.

먼저 스도쿠의 한 해를 S라 합시다.

(i, j) ∈ {1, 2, 3} × {1, 2, 3} ∪ {4, 5, 6} × {4, 5, 6} ∪ {7, 8, 9} × {7, 8, 9}인 임의의 i ∈ N와 j ∈ N에 대하여,

S의 i행과 j행을 교체한 것을 S_1이라 하고 S의 i열과 j열을 교체한 것을 S_2라 하면, S_1과 S_2는 모두 스도쿠의 해입니다.


이제 다음을 만족시키는 연산들의 집합 F를 찾고자 합니다:


스도쿠의 한 해 S가 주어졌을 때, F에 속한 연산들을 유한 번 적용하여 얻은 모든 판들이 정확히 모든 스도쿠의 해가 된다.


이 문제도 수학적으로 접근할 수 있을까요?

읽어주셔서 감사합니다.


----

수정1: 그냥 연산이라고 말하면 애매한 것 같네요. 연산이란 가역적인 과정으로 정의합시다.