# frozen_string_literal: true

def sd_genmat
  mr = Array.new(324) { [] }
  mc = Array.new(729) { Array.new(4, 0) }
  r = 0

  i = 0
  while i < 9
    j = 0
    while j < 9
      k = 0
      while k < 9
        mcr = mc[r]
        mcr[0] = 9 * i + j
        mcr[1] = (i / 3 * 3 + j / 3) * 9 + k + 81
        mcr[2] = 9 * i + k + 162
        mcr[3] = 9 * j + k + 243
        r += 1
        k += 1
      end
      j += 1
    end
    i += 1
  end

  r2 = 0
  while r2 < 729
    c2 = 0
    while c2 < 4
      mr[mc[r2][c2]] << r2
      c2 += 1
    end
    r2 += 1
  end

  [mr, mc]
end

def sd_update_forward(mr, mc, sr, sc, r)
  min = 10
  min_c = 0
  mcr = mc[r]

  c2 = 0
  while c2 < 4
    sc[mcr[c2]] += 128
    c2 += 1
  end

  c2 = 0
  while c2 < 4
    mrc = mr[mcr[c2]]
    r2 = 0
    while r2 < 9
      rr = mrc[r2]
      if (sr[rr] += 1) == 1
        p = mc[rr]
        cc2 = 0
        while cc2 < 4
          cc = p[cc2]
          if (sc[cc] -= 1) < min
            min = sc[cc]
            min_c = cc
          end
          cc2 += 1
        end
      end
      r2 += 1
    end
    c2 += 1
  end

  [min, min_c]
end

def sd_update_reverse(mr, mc, sr, sc, r)
  c2 = 0
  while c2 < 4
    sc[mc[r][c2]] -= 128
    c2 += 1
  end

  c2 = 0
  while c2 < 4
    c = mc[r][c2]
    r2 = 0
    while r2 < 9
      rr = mr[c][r2]
      if (sr[rr] -= 1) == 0
        p = mc[rr]

        sc[p[0]] += 1
        sc[p[1]] += 1
        sc[p[2]] += 1
        sc[p[3]] += 1
      end
      r2 += 1
    end
    c2 += 1
  end
end

def sd_solve(mr, mc, s)
  sr = Array.new(729, 0)
  sc = Array.new(324, 9)
  hints = 0

  i = 0
  while i < 81
    char = s[i]
    a = (char >= '1' && char <= '9') ? char.ord - 49 : -1
    if a >= 0
      sd_update_forward(mr, mc, sr, sc, i * 9 + a)
      hints += 1
    end
    i += 1
  end

  cr = Array.new(81, -1)
  cc = Array.new(81, 0)
  i = 0
  min = 10
  dir = 1

  while true
    while i >= 0 && i < 81 - hints
      if dir == 1
        if min > 1
          c = 0
          while c < 324
            if sc[c] < min
              min = sc[c]
              cc[i] = c
              break if min < 2
            end
            c += 1
          end
        end

        if min == 0 || min == 10
          cr[i] = dir = -1
          i -= 1
        end
      end

      c = cc[i]
      if dir == -1 && cr[i] >= 0
        sd_update_reverse(mr, mc, sr, sc, mr[c][cr[i]])
      end

      r2 = cr[i] + 1
      while r2 < 9 && sr[mr[c][r2]] != 0
        r2 += 1
      end

      if r2 < 9
        min, cc[i + 1] = sd_update_forward(mr, mc, sr, sc, mr[c][r2])
        cr[i] = r2
        dir = 1
        i += 1
      else
        cr[i] = -1
        dir = -1
        i -= 1
      end
    end

    break if i < 0

    o = Array.new(81, 0)
    j = 0
    while j < 81
      o[j] = s[j].ord - 48
      j += 1
    end

    j = 0
    while j < i
      r = mr[cc[j]][cr[j]]
      o[r / 9] = r % 9 + 1
      j += 1
    end
    puts o.join

    i -= 1
    dir = -1
  end
end

hard20 = [
  "..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9",
  ".......12........3..23..4....18....5.6..7.8.......9.....85.....9...4.5..47...6...",
  ".2..5.7..4..1....68....3...2....8..3.4..2.5.....6...1...2.9.....9......57.4...9..",
  "........3..1..56...9..4..7......9.5.7.......8.5.4.2....8..2..9...35..1..6........",
  "12.3....435....1....4........54..2..6...7.........8.9...31..5.......9.7.....6...8",
  "1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1",
  ".......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....",
  "12.3.....4.....3....3.5......42..5......8...9.6...5.7...15..2......9..6......7..8",
  "..3..6.8....1..2......7...4..9..8.6..3..4...1.7.2.....3....5.....5...6..98.....5.",
  "1.......9..67...2..8....4......75.3...5..2....6.3......9....8..6...4...1..25...6.",
  "..9...4...7.3...2.8...6...71..8....6....1..7.....56...3....5..1.4.....9...2...7..",
  "....9..5..1.....3...23..7....45...7.8.....2.......64...9..1.....8..6......54....7",
  "4...3.......6..8..........1....5..9..8....6...7.2........1.27..5.3....4.9........",
  "7.8...3.....2.1...5.........4.....263...8.......1...9..9.6....4....7.5...........",
  "3.7.4...........918........4.....7.....16.......25..........38..9....5...2.6.....",
  "........8..3...4...9..2..6.....79.......612...6.5.2.7...8...5...1.....2.4.5.....3",
  ".......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6...",
  ".......12....35......6...7.7.....3.....4..8..1...........12.....8.....4..5....6..",
  "1.......2.9.4...5...6...7...5.3.4.......6........58.4...2...6...3...9.8.7.......1",
  ".....1.2.3...4.5.....6....7..2.....1.8..9..3.4.....8..5....2....9..3.4....67....."
]

mr, mc = sd_genmat

n = 200
if ARGV.length > 0
  n = ARGV[0].to_i
end

i = 0
while i < n
  hard20.each do |line|
    sd_solve(mr, mc, line)
    puts ""
  end
  i += 1
end
