package main

import (
	"fmt"
)

type sdaux_t struct {
	r [324][9]uint16
	c [729][4]uint16
}

func sd_genmat() *sdaux_t {
	a := new(sdaux_t)
	nr := make([]int8, 324)
	r := 0
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			for k := 0; k < 9; k++ {
				a.c[r][0] = uint16(9*i + j)
				a.c[r][1] = uint16((i/3*3+j/3)*9 + k + 81)
				a.c[r][2] = uint16(9*i + k + 162)
				a.c[r][3] = uint16(9*j + k + 243)
				r++
			}
		}
	}
	for c := 0; c < 324; c++ {
		nr[c] = 0
	}
	for r := 0; r < 729; r++ {
		for c2 := 0; c2 < 4; c2++ {
			k := a.c[r][c2]
			a.r[k][nr[k]] = uint16(r)
			nr[k]++
		}
	}
	return a
}

func sd_update_forward(aux *sdaux_t, sr []int8, sc []uint8, r uint16) int {
	min, min_c := uint8(10), uint16(0)
	rows := &aux.c[r]
	for _, c := range rows {
		sc[c] |= 0x80
	}
	for _, c := range rows {
		for _, rr := range &aux.r[c] {
			sr[rr]++
			if sr[rr] != 1 {
				continue
			}
			for _, cc := range &aux.c[rr] {
				v := sc[cc] - 1
				sc[cc] = v
				if v < min {
					min, min_c = v, cc
				}
			}
		}
	}
	return int(min)<<16 | int(min_c)
}

func sd_update_revert(aux *sdaux_t, sr []int8, sc []uint8, r uint16) {
	rows := &aux.c[r]
	for _, c := range rows {
		sc[c] &= 0x7f
	}
	for _, c := range rows {
		for _, rr := range &aux.r[c] {
			sr[rr]--
			if sr[rr] != 0 {
				continue
			}
			for _, cc := range &aux.c[rr] {
				sc[cc]++
			} // unroll this loop makes no difference
		}
	}
}

func sd_solve(aux *sdaux_t, _s []byte) int {
	sr := make([]int8, 729)
	cr := make([]int8, 81)
	sc := make([]uint8, 324)
	cc := make([]int16, 81)
	out := make([]byte, 81)
	n, hints := 0, 0
	for c := 0; c < 324; c++ {
		sc[c] = 9
	}
	for i := 0; i < 81; i++ {
		a := -1
		if _s[i] >= '1' && _s[i] <= '9' {
			a = int(_s[i] - '1')
		}
		if a >= 0 {
			sd_update_forward(aux, sr, sc, uint16(i*9+a))
			hints++
		}
		cr[i], cc[i], out[i] = -1, -1, _s[i]
	}
	i, dir, cand := 0, 1, 10<<16
	for {
		for i >= 0 && i < 81-hints {
			if dir == 1 {
				min := uint8(cand >> 16)
				cc[i] = int16(cand & 0xffff)
				if min > 1 {
					for c, scc := range sc {
						if scc < min {
							min, cc[i] = scc, int16(c)
							if min <= 1 {
								break
							}
						}
					}
				}
				if min == 0 || min == 10 {
					cr[i], dir = -1, -1
					i--
				}
			}
			c := cc[i]
			if dir == -1 && cr[i] >= 0 {
				sd_update_revert(aux, sr, sc, aux.r[c][cr[i]])
			}
			r2_ := 9
			for r2 := cr[i] + 1; r2 < 9; r2++ {
				if sr[aux.r[c][r2]] == 0 {
					r2_ = int(r2)
					break
				}
			}
			if r2_ < 9 {
				cand = sd_update_forward(aux, sr, sc, aux.r[c][r2_])
				cr[i], dir = int8(r2_), 1
				i++
			} else {
				cr[i], dir = -1, -1
				i--
			}
		}
		if i < 0 {
			break
		}
		for j := 0; j < i; j++ {
			r := aux.r[cc[j]][cr[j]]
			out[r/9] = byte(r%9) + '1'
		}
		fmt.Println(string(out))
		n++
		i--
		dir = -1
	}
	return n
}

func main() {
	hard20 := []string{
		"..............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.....",
	};
	a := sd_genmat()
	n := 200
	for i := 0; i < n; i++ {
		for _, l := range hard20 {
			if len(l) >= 81 {
				sd_solve(a, []byte(l))
				fmt.Println("")
			}
		}
	}
}
