Who know how to solve it. I think all the varians will be
4^(9 + 7 + 5 + 3 + 1) = 4^25 when n = 10. So i cannot count from 1st to kth variant

O(N^4) simple algo exists.

Can you tell anything else? I mean is the algo search(Binary Search or smth else). Please give me a clue

Suppose you have already built a part of a grille and is thinking what symbol is to put in the following cell. Can you count the number of grilles which can be built with such a beginning and symbol?

Given advices too weak to be helpfull.
For me key idea was forming n*n/4 classes with 4 cell in each and working
with level, where 1<=level<=n*n;
We counting all combinations under level in each classes exept whose are used already.

My algo was same as Vedernikoff 'Goryinyich' Sergey (HSE: АОП) said.
Algo is very simple and wasn't too hard to implement.

Edited by author 08.11.2011 00:01

I suppose that O(n^2) algorithm is even more simple. Both in inventing and coding.

That's right. I track amount of remaining variations for every cycle and their total product. This information is enough at each of N^2 steps to decide if it should be '0' or '1'