Тема: Пентамино
Доброго времени суток.
Есть пентамино. (можно посмотреть на вики что это за штука. 12 различных фигур , составленных из 5 квадратиков)
задачка:
написать программу, позволяющую задать фигуру из 60 квадратиков и выясняющую, может ли эта фигура быть покрыта пентаминошками.(каждая из 12 пентамино используется ровно один раз, но их можно переворачивать и вращать).
прочитал несколько статей по поводу этой игрушки 'пентамино'
особенно заинтересовала вот эта статья :
http://www.cs.brandeis.edu/~storer/JimP … ivasch.pdf
Есть у нас алгоритм решения задачи точного покрытия. Для него собственно нужна матрица, к которой мы его уже будем применять.
Now we get to the relation between the pentomino puzzle and the Exact Cover problem. Construct a matrix
with 72 columns: 12 for the twelve pentominoes and 60 for the cells of the board. Now, for each way a
pentomino can be placed on the board, insert a row in the matrix. The row should contain a 1 in one of the
first 12 columns, indicating the pentomino, and five 1's among the other 60 rows, indicating the five cells of
the board the pentomino occupies; everywhere else the row should contain zeros. This should be done for all
possible ways of placing each of the twelve pentominoes on the board. The matrix corresponding to the 8x8
square shown above, for example, has 1568 rows.
Собственно, не придумать как эту матрицу заполнить.. 12 столбцов под пентамино(кстати. если же сказано, что можно вращать и тд, то 63 различных фигуры выходит) и 60 столбцов под все клетки, которые нам дают на вход. нужно создавать строчки, как сказано в статье..
На вход программе, подается матричка размера NxM из нулей и единичек. (насколько я понял)
Подскажите, пожалуйста, как бы это реализовать. Или быть может можно без заморочек этих решить ?
Ограничений по времени не дано. Но грубый перебор делать как-то не хочется.
п.с. язык С++ .