2580

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf8").trim().split("\n");

const grid = input.slice().map((line) => line.split(" ").map(Number));

let blanks = [];
grid.forEach((line, i) => line.forEach((v, j) => (v === 0 ? blanks.push([i, j]) : null))); // 빈칸들의 위치를 [r, c] 로 저장

let find = false;

const rows = Array.from({ length: 9 }, () => new Set());
const cols = Array.from({ length: 9 }, () => new Set());
const smallGrid = Array.from({ length: 9 }, () => new Set());

for (let i = 0; i < 9; i++) {
  for (let j = 0; j < 9; j++) {
    if (grid[i][j] !== 0) {
      rows[i].add(grid[i][j]);
      cols[j].add(grid[i][j]);
      smallGrid[smallGridIndex(i, j)].add(grid[i][j]);
    }
  }
}

backtrack(0);

function backtrack(idx) {
  // 종료 조건
  if (idx === blanks.length) {
    grid.forEach((row) => console.log(row.join(" ")));
    find = true;
    return;
  }

  let [r, c] = blanks[idx];
  // 기본 동작
  for (let num = 1; num <= 9; num++) {
    if (!already(r, c, num)) {
      grid[r][c] = num;

      rows[r].add(num);
      cols[c].add(num);
      smallGrid[smallGridIndex(r, c)].add(num);

      backtrack(idx + 1);

      grid[r][c] = 0;

      rows[r].delete(num);
      cols[c].delete(num);
      smallGrid[smallGridIndex(r, c)].delete(num);
    }

    if (find) return;
  }
}

function already(r, c, num) {
  if (rows[r].has(num)) return true;

  if (cols[c].has(num)) return true;

  if (smallGrid[smallGridIndex(r, c)].has(num)) return true;

  return false;
}

function smallGridIndex(r, c) {
  return Math.floor(r / 3) * 3 + Math.floor(c / 3);
}