Японский кроссворд #538695

Рассмотрим черно-белый размера n*m Вопрос: сколько различных заведомо решаемых кроссвордов можно построить?  То есть найти зависимость числа решений от n и m. Тот же вопрос для кроссвордов имеющих единственное решение. Например, для кроссворда ниже имеется 2 решения:

задача решабельная?

J(n,m) - число решаемых кроссвордов SJ(n,m) - число однозначно решаемых кроссвордов J(n,1)=J(1,n)=SJ(1,n)=SJ(n,1)=2^n

во во!

А нафига или романтик?

Какие ваши доказательства? ©

Возьмем 2 кроссворда с размерность 2*1 и 1*2. По формуле получается, что в первом случае 4, а во втором 2 кроссворда?

В любом случае нет критерия "нерешаемости", т.е. только опытным путем

Опять таки возьмем поле 2*2 Если по горизонтали и вертикали поставить во все поля 1, т.е. .|1|1| 1|.|.| 1|.|.| То получаем неопределенно, т.е. он решается при некотором допущении, и необязательно решение будет совпадать с исходным ответом

Да кстати формулировка в неверно, так как для размерности поля 2*2 можно построить как минимум 15 различных кроссвордов

клетка либо заполнена, либо нет нет, J(n,1)=J(1,n) "нерешаемость" это когда нельзя закрасить клеточки согласно чисел на крах по правилам именно данный кроссворд имеет всего 2 решения я имел ввиду единственный приведенный, а всего я еще не считал

Тогда причем тут размерность поля? Если мы привязываемся к заполнению (к числам на полях)

J(n,1)=J(1,n) = 2^n ваша формула?, где n размерность одного из края. Или я неправильно ее интерпретирую?

если один из аргументов равен 1 (n или m) то получается данная формула, общего результата нет

На Algolist.Ru есть статья

спасибо, правда там стать о решении кроссворда, а не поиски числа решений

Решаемых построить можно 2 ^ (n*m) - 1. Любая клетка либо заполнена, либо нет, "все пустые клетки" - убираем (это не кроссворд) :)

2^(n*m) - это количество возможных решений, а не различных кроссвордов. В пример кроссворда, имеющего 2 рашения => для n=m=2 число различных кроссвордов <2^4

да: J(2,2)=15 SJ(2,2)=14

уточняю: под кроссвордом понимается исходная позиция, то есть наборы чисел вдоль строк и столбцов кроссворд разрешим, если его можно заполнить по правилам кроссворд разрешим однозначно, если такое заполнение единственно

Вона как... не дочитал... не все буквы - прочитал только любимые.

SJ(n,m) - число однозначно решаемых кроссвордов Где то так: SJ(n,m)=Сумма(2^(k*l+n-k+m-l)), где суммирование идет по всем k<=n и l<=m

утром в метро ехал, считал: J(2,3)=58 SJ(2,3)=52

Начну потихоньку. Жаль на мисте нельзя формулы писать и картинки нормально постить. Вопрос: сколько различных заведомо решаемых кроссвордов можно построить? Построим вектор сумм строк некоторой матрицы m*n состоящей из 0 и 1. (А1,А2,...Аm) Очевидно 0<=Ai<=n Различных векторов будет (n+1)^m. Из каждого вектора можно получить хотя бы одну картинку. Возьмем (А1,А2,...Аm) количество картинок которые можно построить по этому вектору: С(n,А1)*С(n,А2)*...*С(n,Аm), где С(n,k) число сочестаний из n по k. осталось проссумировать по всем допустимым векторам (А1,А2,...Аm). Формула получилось громозкая, но ее можно пропустить. Надо почитать книжки по комбинаторике или написать производяшую функцию. Еще наблюдение, в полученной формуле явно просматривается бином Ньютона.

формулы можно постить так, открываем и создаем формулу, внизу выбираем тип URL и копируем ссылку сюда, например:

Тот же вопрос для кроссвордов имеющих единственное решение. Пусть картинка представлена ввиде матрицы n*m B. Свойство №1. Если в матрице есть такие k,l,i,j, что B(k,l)=B(i,j) и B(k,j)=B(i,l), То суммы строк и столбцов, полученные по этой мтрице имеют несколько решений. Гипотеза. Свойство №1 является достаточным. Свойство №2. Если в матрице B, имеющей единственное решение, поменять местами две строки (столбца), то полученная матрица B' тоже имеет единственное решение.

к сожалению даже с скриптом они визуализируются ((

+ НЕ визуализируются

нет, например матрица 2*3 единственна у данного кроссворда (* это закрашено): .*. *.*

везет людям. На работе видно вообще делать нечего.

не завидуй

010 101 ------ 100 011 ---- 001 110 ----- Все они порождают векторы сумм 1 2 111

нет, по строкам и столбцам стоят не просто числа, а упорядоченные наборы чисел (прочти про японские кроссворды) в твоем посте первая матрица по строкам имеет наборы: {1} {1,1}

Там сдвинулось. Три вышеприведннеые мтрицы имеют одиноковые: Вектор сумм по строкам (1,2) Вектор сумм по столбцам (1,1,1)

А блин, все перпутал.

сумм может быть, но кроссворд не суммами определяется, а наборами у каждой строки/столбца если по строкам: {1} {1,1} то решение кроссворда единственно, а если: {1} {2} то решений 2