ピクロスの一意性

1週間に1度は更新をしたいと思います。
それはそうと、今日はピクロス（お絵かきロジック・Nonogram）についての話です。
ルールはこちらを参照のこと。

中学生の頃だったか、ピクロスの1つの問題に対して、その解は常に一意に定まるのか、と考えたことがあります。
一意に定まるとは限らないのであれば、問題を作る方も大変です。
で、しばし考えたのですが、簡単に結論が出ました。
次のような問題を考えてみます。

　１１

１□□

１□□

これには、次の2通りの解があります。

　１１

１■□

１□■

　１１

１□■

１■□

したがって、一意に定まるとは限らない、が正解です。
少し一般化して、上のような問題を n×n に拡張すると、その解は n! 通りあることが分かりますね。
また、そういった形を適当に含む問題も、解は一意に定まりません。

解が一意に定まるための必要十分条件について考えてみると面白いかも。

ちなみに、ピクロスDSではオリジナル問題を作れるそうなのですが、上述のような問題にはどう対処しているのでしょうね。
買って確かめてみようかな…。

ついでに、問題を考えてみました。
n 個のマスのいくつかを削るとして

をみたす k 個の自然数（0を除く） が与えられたとき、可能な削り方は何通りあるか。
うわ、結構難しそうです。
いや、簡単か。
あー、できるできる。