계산 문제 : 가능한 스도코 테이블?

Question

나는 sudoko 해결사 (파이썬)에서 일하고있다. 내 방법은 게임 트리를 사용하고 DFS 알고리즘에 의해 각 자릿수에 대한 가능한 순열을 탐색합니다.

문제를 분석하기 위해 가능한 카운트가 무엇인지 알고 싶습니다 스도코 테이블이 유효합니까?

-> 9 9, 9 2, ..., 9 9가있는 9 * 9 테이블.

(이 정확한 this question에 의해 중복되지 않음)

내 솔루션은 다음과 같습니다

는

1 먼저 1 초 동안 9 개 셀을 선택 (*)

2와 같은 (1) 다른 숫자의 경우 (매회 9 셀은 남은 사용 가능한 셀에서 삭제됩니다.) C (81-9,9), C (81-9 * 2,9) .... =

3- 마지막으로 결과를 9로 곱하십시오! (*에서 1s-2s-3s ...- 9s의 순열)

이것은 받아 들인 응답과 같지 않습니다. this question 그러나 문제는 같습니다. 내가 뭘 잘못 했니?

Answer 1

표준 9 × 9 격자에 대한 유효한 스도쿠 솔루션 격자 수는 2005 년 Bertram Felgenhauer와 Frazer Jarvis에 의해 6,670903752021072936960으로 계산되었습니다.

Mathematics of Sudoku | source

당신의 솔루션에 문제가 있다고 생각합니다 가능한 셀에서 매번 9 셀을 삭제하면 반드시 유효한 그리드를 만들지 않습니다. 내 말은 9 셀을 삭제하면 충분하지 않다는 것입니다.

그 이유는 81!/(9!)^9는 실제 유효한 솔루션보다 훨씬 더 많습니다.

편집 : 당신은 모든 테이블뿐만 아니라 유효 스도쿠 테이블을 원하는 경우

Permutations with repeated elements

솔루션은 거의 정확합니다.

수식있다 :

(A + B + C + ...)!/[a! 비! 기음! ....]

이 다섯 남자와 세 여자입니다 그리고 그들은이 수용 할 수있는 다른 방법의 수는

(+ 3 5) 우리가 8 개 자리가 있다고 가정!/(5! 3!)

문제는이 문제와 유사합니다.

9 1s, 9 2s ... 9s가 있습니다. 및 81 장소

그래서 답변은 (9 + 9 + ...)이어야합니다!/(9!)^9

이제 다시 9를 곱하면!다음이 그들을 셔플에 의해 숫자에 중복 된 조치를 추가합니다.

Answer 2

this Wikipedia article (또는 this OEIS sequence)에 따르면, 대략 6.6 * 10^21 개의 다른 스도쿠 사각형이 있습니다.

Answer 3

마지막 단계는 잘못된 것이 었습니다. 답을 곱하면 안됩니다. 9!. 가능한 모든 사각형을 이미 계산하셨습니다.

가능한 스도쿠 테이블을 계산할 때 많은 도움이되지 않습니다. 당신이 할 수있는 또 하나의 일은 "행 - 조건"이 보유하고있는 테이블을 세는 것입니다 : 단지 (9!)^9입니다. 모든 행에 하나의 순열을 1..9으로 선택하기 때문입니다.

여전히 스도쿠 문제에 더 가까운 것은 Latin squares입니다. 라틴 사각형은 "행 조건"과 "열 조건"을 모두 만족시켜야합니다. 그것은 이미 어려운 문제이며 폐쇄 형식 공식은 알려져 있지 않습니다. 스도쿠 (Sudoku)는 라틴 사각형으로 "서브 스퀘어 조건"이 추가되었습니다.