Саша любит задачи по комбинаторике, а также любит разгадывать судоку. Однажды он задумался: «Сколькими способами может стоять конкретная цифра в судоку?». Помогите Саше, т.е. укажите, сколькими способами можно выбрать 9 клеток доски 9×9, разделённой на девять квадратиков 3×3 так, чтобы в каждой строчке, в каждом столбце, и в каждом из девяти квадратиков 3×3 была выбрана ровно одна клетка.

Решим конкретный пример. Если я правильно понял задачу, то вопрос сколькими способами можно расставить например цифру "1" на поле в судоку.
Расставлять буду по квадратам 3х3, которых 9 штук. Пронумерую их начиная с левого верхнего угла.
Смотрим рисунок для наглядности.
Для 1 квадрата: 9 способов выбрать клетку.
Выбрав клетку (вычеркиваем 1 строку и 1 столбец)
Для 2 квадрата: 1 строчка занята (выбывает 3 клетки), остается 6 клеток
Для 3 квадрата: 2 строчки заняты (выбывает 6 клеток), остается 3 клетки
Аналогично по стобцам
Для 4 квадрата: 1 столбец занят (выбывает 3 клетки), остается 6 клеток
Для 5 квадрата: 2 столбца заняты (выбывает 6 клеток), остается 3 клетки
Для 6 квадрата: Занят 1 столбец (от 2 квадрата) и 1 строка (от 4 квадрата) (выбывает 5 клеток), остается 4 клетки.
Для 7 квадрата: заняты 2 строки (от 4 и 6 квадратов) и 1 столбец (от 3 квадрата)(выбывает 7 клеток), остается 2 клетки
Аналогично
Для 8 квадрата: заняты 2 столбца (от 2 и 6 квадратов) и 1 строка (от 5 квадрата)(выбывает 7 клеток), остается 2 клетки
Для 9 квадрата: Заняты 2 строки (от 5 и 8 квадратов) и 2 столбца (от 3 и 7 квадратов) (выбывает 8 клеток), остается 1 клетка.
Теперь осталось перемножить все варианты:
9•6•3•6•3•4•2•2•1 = 46656
Ответ: 46656       
                                                                              

Ответ какой-то странный, подозрительный получился...
Пусть доска имеется размеры n строк на n столбцов, а каждая её клетка сама разбита на субклетки и имеется размеры n субстрок на  n субстолбцов. Строки и столбы пусть нумеруются с нуля (индексы пробегают значения из интервала [1; n[). Количество способов выбрать свободную субстроку в клетке, стоящей на пересечении строки i и столбца j обозначим как r(i, j). Аналогично, количество способов выбрать субстолбец в клетке с координатами (i, j) равно c(i, j).
Определим начальные условия. Очевидно, r(0, 0)=c(0, 0)=n, т.е. в первой, "верхней-левой" клетке, все субстроки и субстолбцы свободны для заполнения. Более того, для любых i и j выполняется r(i, 0)=n и c(0, j)=n (проверьте!).
Если известно r(i, j), то перейдя в следующий столбец (если существует), для выбора субстроки существует ровно на один способ меньше, т.е. r(i, j+1) = r(i, j)-1. Похожим образом выводится рекуррентное определение и для c(): c(i+1, j) = c(i, j)-1.
Найдём замкнутое решение для первого уравнения r(i, j+1)=r(i, j)-1. Для этого, просуммируем обе части по j от 0 до некоторого числа m: sum(r(i, j+1), 0<=j<=m) = sum(r(i, j)-1, 0<=j<=m). В правой части, sum(-1, 0<=j<=m)=-m-1. В левой части сместим индекс: sum(r(i, j+1), 0<=j<=m)=sum(r(i, j), 1<=j<=m+1). Снова приравнивая левую и правую части получаем sum(r(i, j), 1<=j<=m+1) = sum(r(i, j), 0<=j<=m)-m-1. В сумме, находящейся в правой части, есть лишнее слагаемое r(i, 0), в левой части -- лишнее слагаемое r(i, m+1). Вынесем их за знак суммы и получим
r(i, m+1)+sum(r(i, j), 1<=j<=m) = sum(r(i, j), 1<=j<=m)+r(i, 0)-m-1.
Выражения вида sum(...) в обеих частях оказались одинаковыми и их можно сократить: r(i, m+1)=r(i, 0)-m-1. Подстановка m+1 -> j и применение начального условия r(i, 0)=n даёт искомое решение в замкнутой форме:
r(i, j) = n-j.
Случай с функцией c(..., ...) полностью аналогичен и даёт решение
c(i, j)=n-i.
По построению, в каждой клетке мы искали свободную субстроку и субстолбец и использовали лишь одну стоящую на их пересечении субклетку. Это условие выполнено. Осталось найти общее количество способов выбрать n субклеток, по одной в каждой клетке. А именно, искомое количество находится как произведение всех способов выбора субклетки во всех клетках. Т.е. решение выглядит как
prod(r(i, j)*c(i,j), 0<=i<n, 0<=j<n),
где символ prod аналогичен символу sum, но вместо суммирования производит перемножение выражения в скобках до запятой по индексам, указанным, вместе с интервалами допустимых значений, после запятой.
Подстановка полученных ранее выражений для r(i, j) и c(i, j) в это произведение даёт
prod((n-i)*(n-j), 0<=i<n, 0<=j<n).
Замечаем, что произведение по n-i при 0<=i<n можно заменить на произведение prod(i) при 1<=i<=n. То же справедливо и для выражения n-j. В итоге, получаем,
prod(i*j, 1<=i<=n, 1<=j<=n).
Сравним с факториалом: n!=prod(i, 1<=i<=n). Очень похоже! Но в нашем случае для каждого i, индекс j пробегает все значения и тоже участвует в общем произведении. Ещё раз, для каждого i, т.е. для всех его n возможных значений, j формирует ещё один факторил и "добавляет" (мультипликативно) его в общее выражение. Окончательно, получается, что у нас есть факториал от n и он n раз умножается на факториалы от n (ведь j тоже пробегает n значений). Т.е.,
prod(i*j, 1<=i<=n, 1<=j<=n) = n!*(n!)^n = (n!)^{n+1}.
При n=3, ответ равен (3!)^4 = 6^4 = 1296.
P.S.: Ну когда же на БВ добавят поддержку формул. Думаю, участники-авторы даже готовы пожертвовать одним рублём/кредитом в месяц для улучшения условий хостинга с целью запуска простейшей поддержки latex-вёрстки формул; а на крайний случай можно и бесплатно какой-нибудь mathjax прикрутить. Эх...