What algorithm should be used in this problem?

Question

Algorithms

Today there was a task at the Olympiad. I successfully filled it up, but I'm still wondering how to solve it. Here is the problem itself:
There are numerical values ​​n, k, s.
n = 2..64
2 <= k <= n
s = 1..k^2
You need to create a matrix of n*n elements and arrange zeros and ones so that there are exactly s ones in any square of size k*k.
My only suggestion was to write a function that checks if the array matches the rules (which I did) and then run all possible options through it, but I understand that this is not efficient. Yes, and I did not manage to get all the options in the array.

Answer 1

While I waited, I googled it myself.
This is a challenge for an idea. When you know it, the solution seems obvious. However, coming up with such a
solution yourself is sometimes (or rather, even very often) not so easy. Let's reveal the secret of the problem: it
is enough to generate any K*K square containing exactly S ones, and then simply fill
the N*N square with it.
More details (+ pascal code): tyts

Answer 2

Well, you already found the answer yourself. However, if you want a "pattern" of 1s and 0s that doesn't repeat primitively, as in your solution, then you should do the following:
1. Create an empty n*n matrix.
2. At the origin, randomly fill in the k*k square with units in the number S.
3. Move the k*k square by one cell.
4. Check the number of units in the square.
5. Add the required number of units to the new cells, so that there are S. Again, distributing them randomly.
6. Repeat steps 3-5 until the n*n matrix ends.
7. Profit!!!
Thus, we get an n*n matrix with a unique and non-repeating pattern.

Answer 3

Why not just start filling from the top left corner? Well, that is, in the first square we put down randomly, and then we put it. Wherever we move (down or to the right in a row), we cannot get into a hopeless situation, which means that problems cannot arise. To speed up, you should use the calculations in the previous steps.