package main

import (
	fmt "fmt"
	"time"
)

func main() {
	boards := [][][]byte{
		{
			{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
			{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
			{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
			{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
			{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
			{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
			{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
			{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
			{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
		},
		{
			{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
			{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
			{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
			{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
			{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
			{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
			{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
			{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
			{'.', '.', '.', '.', '8', '.', '.', '7', '9'},
		},
		{
			{'.', '.', '9', '7', '4', '8', '.', '.', '.'},
			{'7', '.', '.', '.', '.', '.', '.', '.', '.'},
			{'.', '2', '.', '1', '.', '9', '.', '.', '.'},
			{'.', '.', '7', '.', '.', '.', '2', '4', '.'},
			{'.', '6', '4', '.', '1', '.', '5', '9', '.'},
			{'.', '9', '8', '.', '.', '.', '3', '.', '.'},
			{'.', '.', '.', '8', '.', '3', '.', '2', '.'},
			{'.', '.', '.', '.', '.', '.', '.', '.', '6'},
			{'.', '.', '.', '2', '7', '5', '9', '.', '.'},
		},
	}

	board := boards[1]

	dump(board)
	createMap(board)
	solveSudoku(board)

	move(pos(9, 0))
	fmt.Println(sudokuSolved(board))
}

var m = map[string]int{}
var sleep = time.Millisecond * 0

func sudokuSolved(board [][]byte) bool {
	m = make(map[string]int)
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			n := board[i][j]
			if n == '.' {
				return false
			}
			if !put(board, i, j, n) {
				return false
			}
		}
	}
	return true
}

func solveSudoku(board [][]byte) {
	solveSudokuHelper(board, 0, 0)
}

func solveSudokuHelper(board [][]byte, i, j int) bool {
	if i >= 9 {
		return sudokuSolved(board)
	}
	if j >= 9 {
		return solveSudokuHelper(board, i+1, 0)
	}
	if board[i][j] != '.' {
		return solveSudokuHelper(board, i, j+1)
	}
	if sleep > 0 {
		time.Sleep(sleep)
	}
	for n := byte('1'); n <= '9'; n++ {
		if put(board, i, j, n) {
			color(i, j, n)
			if solveSudokuHelper(board, i, j+1) {
				return true
			}
			remove(board, i, j, n)
			dot(i, j)
		}
	}
	return false
}

func createMap(board [][]byte) {
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if b := board[i][j]; b != '.' {
				if !put(board, i, j, b) {
					panic(`invalid soduku`)
				}
			}
		}
	}
}

func fmtRow(i int, n byte) string {
	return fmt.Sprintf(`%c in row %d`, n, i)
}
func fmtCol(j int, n byte) string {
	return fmt.Sprintf(`%c in col %d`, n, j)
}
func fmtBox(i, j int, n byte) string {
	return fmt.Sprintf(`%c in box <%d,%d>`, n, i/3, j/3)
}

func put(board [][]byte, i, j int, n byte) bool {
	if _, ok := m[fmtRow(i, n)]; ok {
		return false
	}
	if _, ok := m[fmtCol(j, n)]; ok {
		return false
	}
	if _, ok := m[fmtBox(i, j, n)]; ok {
		return false
	}

	m[fmtRow(i, n)] = 1
	m[fmtCol(j, n)] = 1
	m[fmtBox(i, j, n)] = 1

	board[i][j] = n

	return true
}

// remove restores board at (i,j) to dot.
func remove(board [][]byte, i, j int, n byte) {
	delete(m, fmtRow(i, n))
	delete(m, fmtCol(j, n))
	delete(m, fmtBox(i, j, n))
	board[i][j] = '.'
}

// below are for output.

// move moves cursor to (i,j).
// https://en.wikipedia.org/wiki/ANSI_escape_code
func move(i, j int) {
	fmt.Printf("\x1b[%d;%dH", i+1, j+1)
}

// clear clears screen.
func clear() {
	fmt.Printf("\x1b[2J")
}

// color prints n at (i,j) with color.
func color(i, j int, n byte) {
	move(pos(i, j))
	fmt.Printf("\x1b[32m%c\x1b[0m", n)
}

// dot prints a dot at (i,j).
func dot(i, j int) {
	move(pos(i, j))
	fmt.Print(" ")
}

func char(i, j int, n byte) {
	move(pos(i, j))
	fmt.Printf(`%c`, n)
}

// pos (i,j) at box on screen.
func pos(i, j int) (int, int) {
	return i*2 + 1, j*4 + 2
}

// dump dumps the board.
func dump(board [][]byte) {
	clear()
	move(0, 0)
	// https://codegolf.stackexchange.com/q/126930
	fmt.Println(`
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
║   │   │   ║   │   │   ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │   ║   │   │   ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │   ║   │   │   ║   │   │   ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║   │   │   ║   │   │   ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │   ║   │   │   ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │   ║   │   │   ║   │   │   ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║   │   │   ║   │   │   ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │   ║   │   │   ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │   ║   │   │   ║   │   │   ║
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝ `[1:])
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			n := board[i][j]
			if n == '.' {
				n = ' '
			}
			char(i, j, n)
		}
		fmt.Println()
	}
	move(pos(9, 0))
}