Какой алгоритм использовать в этой задаче?
Пока ждал, нагуглил сам. 
Это задача на идею. Когда ее знаешь, то решение кажется очевидным. Однако придумать такое
решение самому иногда (а точнее даже очень часто) не так-то просто. Раскроем секрет задачи:
достаточно сгенерировать любой квадрат K*K, содержащий ровно S единиц, а затем просто заполнить
им квадрат N*N. 
Подробнее (+ код на паскале): тыц
Ну уже вы сами нашли ответ. Однако если вам хочется что-бы "узор" из единиц и нулей не повторялся примитивно, как в вашем решении, то стоит делать следующим образом:
1. Создать пустую матрицу n*n.
2. В начале координат заполнить рандомно квадрат k*k единицами в кол-ве S.
3. Сместить квадрат k*k на одну клетку.
4. Проверить кол-во единиц в квадрате.
5. Добавить необходимое кол-во единиц в новые клетки, так что бы их было S. Опять же распределив их рандомно.
6. Повторять пункты 3-5 пока матрица n*n не закончится.
7. Профит!!!
Таким образом получаем матрицу n*n с уникальным и не повторяющимся рисунком.