Утверждается, что ответ всегда YES. Построим двудольный граф «строки-столбцы» и проведём ребро между строкой $$$i$$$ и столбцом $$$j$$$, если на их пересечении пустая клетка. Теперь будем расставлять отсутствующие знания по одному. Каждое значение будет стоять в клетках, соответствующих некоторой перестановке (то есть значение $$$v$$$ стоит в клетках $$$(i, p_i)$$$ некоторой перестановки $$$p$$$). Такая перестановка эквивалентна паросочетанию в графе. То есть нам нужно разбить данный граф на $$$n$$$ — (количество фиксированных чисел) паросочетаний. Это можно делать жадно, то есть просто искать каждое паросочетание и удалять эти ребра из графа. Время работы $$$O(n^4)$$$.

Доказательство этого факта: граф регулярный (степени всех вершин в долях равны), из леммы Холла следует, что в таком графе всегда есть паросочетание. Когда мы удалим паросочетание, граф останется регулярным.