• Цифровой квадрат
  DIGSQUARE

Описание
Эта головоломка была придумана Hirofumi Fujiwara. В квадрате 9x9 нужно расставить цифры от 1 до 9, таким образом, чтобы в каждой строке, в каждом столбце и в каждом маленьком квадрате 3x3 цифры от 1 до 9 встречались по одному разу.



Задача
В головоломке задается расположение некоторых цифр, необходимо расставить согласно правилам остальные цифры. Составьте программу DIGSQUAR для решения этой головоломки.


Формат входных данных
Во входном файле DIGSQUAR.IN 9 строк по 9 символов в строке, соответствующие клеткам квадрата. Если цифра в клетке задана, то соответствующий символ входного файла это цифра от 1 до 9. Если цифра в клетке не задана, то указывается символ ‘.’ (точка).

Формат входных данных
В выходной файл DIGSQUAR.OUT вывести одно из решений головоломки (также 9 строк по 9 символов). Если решение найти не удается, то вместо решения вывести слово "IMPOSSIBLE" (без кавычек, прописными буквами!)

Например:

DIGSQUAR.IN
.....2.3.
374..6.2.
.....8.1.
258......
.........
......493
.4.1.....
.2.8..675
.6.5.....

DIGSQUAR.OUT
185742936
374916528
692358714
258493167
439671852
716285493
543167289
921834675
867529341