#!/usr/bin/env python3
#
# RNG based brute force sudoku solver
# Kinda slow sometimes but gets the job done
# Usage: sdk.py [SUDOKU_STRING]
# SUDOKU_STRING is a 81 character string of all rows in grid.
# Empty squares are marked as 0
# If grid is solved, will test if solution is legit

import random
import sys

TO_TEST = """
080020560000100007000000000050090408007800003030010050204000800060085000000200100
004970235530000000000000098060025000400000001000640050670000000000000019192054800
100070030830600000002900608600004907090000050307500004203009100000002043040080009
200010050305042000018009002032100800001020300009003260100700980000260507060080003
"""

def test(solution):
    d = [int(i) for i in solution]
    if sum(d) == 45 * 9:
        for i in range(0, 9):
            if sum([int(c) for c in d[i * 9 : i * 9 + 9]]) != 45:
                print("KO")
                return
        print("OK")
        return
    print("KO")

def solve(input):
    def valid(i, val):
        def get(i):
            return dict(
                x=i // 9,
                y=i % 9,
                z=(i // 3) % 3 + (i // 27) * 3
            )
        tmp = [(get(j), c) for j, c in enumerate(data)]
        cur = get(i)
        for c in 'xyz':
            if str(val) in [d[1] for d in tmp if d[0][c] == cur[c]]:
                return False
        return True

    data = list(input)
    metrics = dict(asrt=0, flush=0)

    print("> INPUT")
    for i in range(0, 9):
        print(data[i * 9 : i * 9 + 9])

    uc = []
    while '0' in data:
        for i, c in enumerate(data):
            if c == "0":
                pos = [val for val in range(1, 10) if valid(i, val)]
                if len(pos) == 1:
                    data[i] = str(pos[0])
                    uc.append(i)
                    break
                if len(pos) == 0:
                    for u in uc:
                        data[u] = "0"
                    metrics['flush'] += 1
                    uc = []
                    break
        else:
            factor = 2
            while factor:
                for i, c in enumerate(data):
                    if c == "0":
                        pos = [val for val in range(1, 10) if valid(i, val)]
                        if len(pos) == factor:
                            data[i] = str(random.choice(pos))
                            uc.append(i)
                            metrics['asrt'] += 1
                            factor = 0
                            break
                else:
                    factor += 1
    print("> SOLUTION")
    for i in range(0, 9):
        print(data[i * 9 : i * 9 + 9])
    print("> METRICS")
    print(metrics)
    print("> STR: %s" % "".join(data))

if __name__ == "__main__":
    if len(sys.argv) == 2:
        if len(sys.argv[1]) == 81:
            if "0" in sys.argv[1]:
                solve(sys.argv[1])
            else:
                test(sys.argv[1])
            sys.exit(0)
    print("INVALID INPUT")