+---+---+---+
|4..|...|8.5|
|.3.|...|...|
|...|7..|...|
+---+---+---+
|.2.|...|.6.|
|...|.8.|4..|
|...|.1.|...|
+---+---+---+
|...|6.3|.7.|
|5..|2..|...|
|1.4|...|...|
+---+---+---+

>>> from sudoku import Sudoku

.....2.......7...17..3...9.8..7......2.89.6...13..6....9..5.824.....891..........

$ python sudoku.py test.txt
+---+---+---+
|...|..2|...|
|...|.7.|..1|
|7..|3..|.9.|
+---+---+---+
|8..|7..|...|
|.2.|89.|6..|
|.13|..6|...|
+---+---+---+
|.9.|.5.|824|
|...|..8|91.|
|...|...|...|
+---+---+---+
Solved with  1004  moves
+---+---+---+
|659|412|378|
|238|679|451|
|741|385|296|
+---+---+---+
|865|723|149|
|427|891|635|
|913|546|782|
+---+---+---+
|396|157|824|
|574|268|913|
|182|934|567|
+---+---+---+
@@@@@@@@@@@@@
$

$ cat test.txt | python sudoku.py
+---+---+---+
|...|..2|...|
|...|.7.|..1|
|7..|3..|.9.|
+---+---+---+
|8..|7..|...|
|.2.|89.|6..|
|.13|..6|...|
+---+---+---+
|.9.|.5.|824|
|...|..8|91.|
|...|...|...|
+---+---+---+
Solved with  1004  moves
+---+---+---+
|659|412|378|
|238|679|451|
|741|385|296|
+---+---+---+
|865|723|149|
|427|891|635|
|913|546|782|
+---+---+---+
|396|157|824|
|574|268|913|
|182|934|567|
+---+---+---+
@@@@@@@@@@@@@
$

__moves = [[2,5],[4,3],[9,8]]

__rindexes[2] = [18, 19, 20, 21, 22, 23, 24, 25, 26]

__cindexes[0] = [0, 9, 18, 27, 36, 45, 54, 63, 72]

__gindexes[2] = [6, 7, 8, 15, 16, 17, 24, 25, 26]

__adjacents[0] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 18, 19, 20, 27, 36, 45, 54, 63, 72]

# In yek code vaghee nist!
>>> b = entry2RCG(80)
>>> print(b)
{'c' : 8, 'r': 8, 'g': 8}

>>> from sudoku import Sudoku
>>> s = Sudoku()
>>> s.setTable(".32.....58..3.....9.428...1...4...39...6...5.....1.....2...67.8.....4....95....6.")
>>> s.printTable()
+---+---+---+
|.32|...|..5|
|8..|3..|...|
|9.4|28.|..1|
+---+---+---+
|...|4..|.39|
|...|6..|.5.|
|...|.1.|...|
+---+---+---+
|.2.|..6|7.8|
|...|..4|...|
|.95|...|.6.|
+---+---+---+

>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
>>> s.printTable()
+---+---+---+
|4..|...|8.5|
|.3.|...|...|
|...|7..|...|
+---+---+---+
|.2.|...|.6.|
|...|.8.|4..|
|...|.1.|...|
+---+---+---+
|...|6.3|.7.|
|5..|2..|...|
|1.4|...|...|
+---+---+---+

>>> from sudoku import Sudoku
>>> s = Sudoku()
>>> s.setTable(".32.....58..3.....9.428...1...4...39...6...5.....1.....2...67.8.....4....95....6.")
>>> s.printPossibleTable()
+---------------------------+---------------------------+---------------------------+
|   167*      3        2    |   197*    9467*     197*  |  8946*    8947*      5    |
|    8      1567*     167*  |    3      45679*   1597*  |  9246*    9247*    2467*  |
|    9       567*      4    |    2        8       57*   |   36*       7*       1    |
+---------------------------+---------------------------+---------------------------+
|  12567*   15678*   8167*  |    4       257*    8257*  |  8126*      3        9    |
|  12347*   8147*    13789* |    6      9237*    23789* |  8124*      5       247*  |
| 234567*   45678*   36789* |  8957*      1     235789* |  8246*    8247*    2467*  |
+---------------------------+---------------------------+---------------------------+
|   134*      2       13*   |   159*     935*      6    |    7       149*      8    |
|  1367*    8167*    13678* |  15789*   23579*     4    |  12359*    129*     23*   |
|  1347*      9        5    |   817*     237*    12378* |  1234*      6       234*  |
+---------------------------+---------------------------+---------------------------+
>>> s.findNextMove(0)
[0, 1]
>>> s.findNextMove(3)
[3, 1]
>>> s.findNextMove()
[25, 7]

>>> from sudoku import Sudoku
>>> s.setTable('.5..9....1.....6.....3.8.....8.4...9514.......3....2..........4.8...6..77..15..6.')
>>> s.printTable()
+---+---+---+
|.5.|.9.|...|
|1..|...|6..|
|...|3.8|...|
+---+---+---+
|..8|.4.|..9|
|514|...|...|
|.3.|...|2..|
+---+---+---+
|...|...|..4|
|.8.|..6|..7|
|7..|15.|.6.|
+---+---+---+
>>> s.solve()
>>> s.printTable()
+---+---+---+
|856|491|372|
|143|572|698|
|927|368|451|
+---+---+---+
|278|645|139|
|514|923|786|
|639|817|245|
+---+---+---+
|361|789|524|
|485|236|917|
|792|154|863|
+---+---+---+

>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
>>> s.printPossibleTable()
+---------------------------+---------------------------+---------------------------+
|    4      1967*    12679* |   139*    9236*    1269*  |    8      1239*      5    |
|  26789*     3     1256789*|  14589*   24569*  1245689*|  12679*   1249*   124679* |
|  8926*    15689*  125689* |    7     234569*  1245689*|  12369*   12349*  123469* |
+---------------------------+---------------------------+---------------------------+
|  8937*      2     135789* |  9345*    34579*   9457*  |  13579*     6      13789* |
|  9367*    15679*  135679* |   935*      8      25679* |    4      12359*   12379* |
|  36789*  456789*  356789* |  9345*      1     245679* |  23579*   23589*   23789* |
+---------------------------+---------------------------+---------------------------+
|   892*     89*      892*  |    6       945*      3    |  1259*      7      12489* |
|    5      8967*    36789* |    2       947*    14789* |  1369*    13489*  134689* |
|    1      8967*      4    |   895*     957*    8957*  |  23569*   23589*   23689* |
+---------------------------+---------------------------+---------------------------+

>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
>>> s.printTable()
+---+---+---+
|4..|...|8.5|
|.3.|...|...|
|...|7..|...|
+---+---+---+
|.2.|...|.6.|
|...|.8.|4..|
|...|.1.|...|
+---+---+---+
|...|6.3|.7.|
|5..|2..|...|
|1.4|...|...|
+---+---+---+
>>> s.move(1, 5)
>>> s.move(2, 6)
>>> s.getMoves()
[[1, 5], [2, 6]]

>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
>>> s.markEntries(s.getAdjacents(0))
+---+---+---+
|xxx|xxx|xxx|
|xxx|   |   |
|xxx|   |   |
+---+---+---+
|x  |   |   |
|x  |   |   |
|x  |   |   |
+---+---+---+
|x  |   |   |
|x  |   |   |
|x  |   |   |
+---+---+---+

>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
>>> s.getRIndexes(8)
[72, 73, 74, 75, 76, 77, 78, 79, 80]

>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
>>> s.getCIndexes(0)
[0, 9, 18, 27, 36, 45, 54, 63, 72]

>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
>>> s.getGIndexes(1)
[3, 4, 5, 12, 13, 14, 21, 22, 23]

>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
>>> t = s.getAdjacents(80)
>>> t
[8, 17, 26, 35, 44, 53, 60, 61, 62, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80]
>>> s.markEntries(t)
+---+---+---+
|   |   |  x|
|   |   |  x|
|   |   |  x|
+---+---+---+
|   |   |  x|
|   |   |  x|
|   |   |  x|
+---+---+---+
|   |   |xxx|
|   |   |xxx|
|xxx|xxx|xxx|
+---+---+---+

>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......")
Sudoku is not valid
Try something like:  52...6.........7.13...........4..8..6......5...........418.........3..2...87.....

4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
52...6.........7.13...........4..8..6......5...........418.........3..2...87.....
6.....8.3.4.7.................5.4.7.3..2.....1.6.......2.....5.....8.6......1....
48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5....
....14....3....2...7..........9...3.6.1.............8.2.....1.4....5.6.....7.8...
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
6.2.5.........3.4..........43...8....1....2........7..5..27...........81...6.....
.524.........7.1..............8.2...3.....6...9.5.....1.6.3...........897........
6.2.5.........4.3..........43...8....1....2........7..5..27...........81...6.....
.923.........8.1...........1.7.4...........658.........6.5.2...4.....7.....9.....
6..3.2....5.....1..........7.26............543.........8.15........4.2........7..
.6.5.1.9.1...9..539....7....4.8...7.......5.8.817.5.3.....5.2............76..8...
..5...987.4..5...1..7......2...48....9.1.....6..2.....3..6..2.......9.7.......5..
3.6.7...........518.........1.4.5...7.....6.....2......2.....4.....8.3.....5.....
1.....3.8.7.4..............2.3.1...........958.........5.6...7.....8.2...4.......
6..3.2....4.....1..........7.26............543.........8.15........4.2........7..
....3..9....2....1.5.9..............1.2.8.4.6.8.5...2..75......4.1..6..3.....4.6.
45.....3....8.1....9...........5..9.2..7.....8.........1..4..........7.2...6..8..
.237....68...6.59.9.....7......4.97.3.7.96..2.........5..47.........2....8.......
..84...3....3.....9....157479...8........7..514.....2...9.6...2.5....4......9..56
.98.1....2......6.............3.2.5..84.........6.........4.8.93..5...........1..
..247..58..............1.4.....2...9528.9.4....9...1.........3.3....75..685..2...
4.....8.5.3..........7......2.....6.....5.4......1.......6.3.7.5..2.....1.9......
.2.3......63.....58.......15....9.3....7........1....8.879..26......6.7...6..7..4
1.....7.9.4...72..8.........7..1..6.3.......5.6..4..2.........8..53...7.7.2....46
4.....3.....8.2......7........1...8734.......6........5...6........1.4...82......
.......71.2.8........4.3...7...6..5....2..3..9........6...7.....8....4......5....
6..3.2....4.....8..........7.26............543.........8.15........8.2........7..
.47.8...1............6..7..6....357......5....1..6....28..4.....9.1...4.....2.69.
......8.17..2........5.6......7...5..1....3...8.......5......2..4..8....6...3....
38.6.......9.......2..3.51......5....3..1..6....4......17.5..8.......9.......7.32
...5...........5.697.....2...48.2...25.1...3..8..3.........4.7..13.5..9..2...31..
.2.......3.5.62..9.68...3...5..........64.8.2..47..9....3.....1.....6...17.43....
.8..4....3......1........2...5...4.69..1..8..2...........3.9....6....5.....2.....
..8.9.1...6.5...2......6....3.1.7.5.........9..4...3...5....2...7...3.8.2..7....4
4.....5.8.3..........7......2.....6.....5.8......1.......6.3.7.5..2.....1.8......
1.....3.8.6.4..............2.3.1...........958.........5.6...7.....8.2...4.......
1....6.8..64..........4...7....9.6...7.4..5..5...7.1...5....32.3....8...4........
249.6...3.3....2..8.......5.....6......2......1..4.82..9.5..7....4.....1.7...3...
...8....9.873...4.6..7.......85..97...........43..75.......3....3...145.4....2..1
...5.1....9....8...6.......4.1..........7..9........3.8.....1.5...2..4.....36....
......8.16..2........7.5......6...2..1....3...8.......2......7..3..8....5...4....
.476...5.8.3.....2.....9......8.5..6...1.....6.24......78...51...6....4..9...4..7
.....7.95.....1...86..2.....2..73..85......6...3..49..3.5...41724................
.4.5.....8...9..3..76.2.....146..........9..7.....36....1..4.5..6......3..71..2..
.834.........7..5...........4.1.8..........27...3.....2.6.5....5.....8........1..
..9.....3.....9...7.....5.6..65..4.....3......28......3..75.6..6...........12.3.8
.26.39......6....19.....7.......4..9.5....2....85.....3..2..9..4....762.........4
2.3.8....8..7...........1...6.5.7...4......3....1............82.5....6...1.......
6..3.2....1.....5..........7.26............843.........8.15........8.2........7..
1.....9...64..1.7..7..4.......3.....3.89..5....7....2.....6.7.9.....4.1....129.3.
.........9......84.623...5....6...453...1...6...9...7....1.....4.5..2....3.8....9
.2....5938..5..46.94..6...8..2.3.....6..8.73.7..2.........4.38..7....6..........5
9.4..5...25.6..1..31......8.7...9...4..26......147....7.......2...3..8.6.4.....9.
...52.....9...3..4......7...1.....4..8..453..6...1...87.2........8....32.4..8..1.
53..2.9...24.3..5...9..........1.827...7.........981.............64....91.2.5.43.
1....786...7..8.1.8..2....9........24...1......9..5...6.8..........5.9.......93.4
....5...11......7..6.....8......4.....9.1.3.....596.2..8..62..7..7......3.5.7.2..
.47.2....8....1....3....9.2.....5...6..81..5.....4.....7....3.4...9...1.4..27.8..
......94.....9...53....5.7..8.4..1..463...........7.8.8..7.....7......28.5.26....
.2......6....41.....78....1......7....37.....6..412....1..74..5..8.5..7......39..
1.....3.8.6.4..............2.3.1...........758.........7.5...6.....8.2...4.......
2....1.9..1..3.7..9..8...2.......85..6.4.........7...3.2.3...6....5.....1.9...2.5
..7..8.....6.2.3...3......9.1..5..6.....1.....7.9....2........4.83..4...26....51.
...36....85.......9.4..8........68.........17..9..45...1.5...6.4....9..2.....3...
34.6.......7.......2..8.57......5....7..1..2....4......36.2..1.......9.......7.82
......4.18..2........6.7......8...6..4....3...1.......6......2..5..1....7...3....
.4..5..67...1...4....2.....1..8..3........2...6...........4..5.3.....8..2........
.......4...2..4..1.7..5..9...3..7....4..6....6..1..8...2....1..85.9...6.....8...3
8..7....4.5....6............3.97...8....43..5....2.9....6......2...6...7.71..83.2
.8...4.5....7..3............1..85...6.....2......4....3.26............417........
....7..8...6...5...2...3.61.1...7..2..8..534.2..9.......2......58...6.3.4...1....
......8.16..2........7.5......6...2..1....3...8.......2......7..4..8....5...3....
.2..........6....3.74.8.........3..2.8..4..1.6..5.........1.78.5....9..........4.
.52..68.......7.2.......6....48..9..2..41......1.....8..61..38.....9...63..6..1.9
....1.78.5....9..........4..2..........6....3.74.8.........3..2.8..4..1.6..5.....
1.......3.6.3..7...7...5..121.7...9...7........8.1..2....8.64....9.2..6....4.....
4...7.1....19.46.5.....1......7....2..2.3....847..6....14...8.6.2....3..6...9....
......8.17..2........5.6......7...5..1....3...8.......5......2..3..8....6...4....
963......1....8......2.5....4.8......1....7......3..257......3...9.2.4.7......9..
15.3......7..4.2....4.72.....8.........9..1.8.1..8.79......38...........6....7423
..........5724...98....947...9..3...5..9..12...3.1.9...6....25....56.....7......6
....75....1..2.....4...3...5.....3.2...8...1.......6.....1..48.2........7........
6.....7.3.4.8.................5.4.8.7..2.....1.3.......2.....5.....7.9......1....
....6...4..6.3....1..4..5.77.....8.5...8.....6.8....9...2.9....4....32....97..1..
.32.....58..3.....9.428...1...4...39...6...5.....1.....2...67.8.....4....95....6.
...5.3.......6.7..5.8....1636..2.......4.1.......3...567....2.8..4.7.......2..5..
.5.3.7.4.1.........3.......5.8.3.61....8..5.9.6..1........4...6...6927....2...9..
..5..8..18......9.......78....4.....64....9......53..2.6.........138..5....9.714.
..........72.6.1....51...82.8...13..4.........37.9..1.....238..5.4..9.........79.
...658.....4......12............96.7...3..5....2.8...3..19..8..3.6.....4....473..
.2.3.......6..8.9.83.5........2...8.7.9..5........6..4.......1...1...4.22..7..8.9
.5..9....1.....6.....3.8.....8.4...9514.......3....2..........4.8...6..77..15..6.
.....2.......7...17..3...9.8..7......2.89.6...13..6....9..5.824.....891..........
3...8.......7....51..............36...2..4....7...........6.13..452...........8..

$ cat sudoku.py | sed '/^#/d;/^[ \t]*#/d;/^$/d' | wc
    220     818    8024

#
# Sudoku solver with python
# --------------------------------------
# programmer: Mohsen Safari
# email: safari.tafreshi@gmail.com
# website: dokaj.ir
# --------------------------------------
#
# Sorry for my bad english (Lo siento mucho por mi ingles!)
#
import sys
import fileinput

class Sudoku:
    # number of moves for resolving this sudoku
    __count = 0

    # self.__table is a dictionary and contains values or
    # possibilidades of each entry
    __table = {}

    # self.__move keeps track of each move
    #is neccessary for Rollback!
    __moves = []

    # a sample sudoku. no has any role in problem solving!
    __sampleSudoku = "52...6.........7.13...........4..8..6......5...........418.........3..2...87....."

    # define (and after in codes: set)  row indexes, column indexes, grid indexes
    __rindexes = [[], [], [], [], [], [], [], [], []]
    __cindexes = [[], [], [], [], [], [], [], [], []]
    __gindexes = [[], [], [], [], [], [], [], [], []]

    # variable for keep entries adjacents of each entry
    __adjacents = []

    def __init__(self, table = None):
        # create one list for each entry. contents of each list will be adjacents
        # of that entry
        for i in range(81):
            self.__adjacents.append([])

        # set values: row indexes, column indexes, grid indexes, adjacents
        self.__setRIndexes()
        self.__setCIndexes()
        self.__setGIndexes()
        self.__setAdjacents()

        # create sudoku table with information provided in table
        if table is not None:
            try:
                self.setTable(table)
            except SyntaxError:
                print("Sudoku is not valid")
                print("Try something like: ", self.getSampleSudoku())

    # create sudoku table 
    def setTable(self, table):
        self.__count = 0
        self.__moves = []
        self.__table = {}

        if len(str(table)) != 81:
            raise SyntaxError

        # read sudoku table and set in self.table
        for i in range(len(table)):
            # if value is not specified fill its place with
            # empty list. this list will be filled with
            # all numbers possible
            if table[i] == ".":
                self.__table[i] = []
            else :
                self.__table[i] = int(table[i])

        # update possible values for each entry which no has value
        self.__updatePossibleTable(fullUpdate = True)

    # set row indexes for each row. key is row number and values are
    # number of each entry inside that row
    # Example:
    # self.__rindexes[0] = [0,1,2,3,4,5,6,7,8] ,
    # self.__rindexes[1] = [9,10,11,12,13,14,15,16,17]
    def __setRIndexes(self):
        for i in range(9):
            s = i * 9
            for j in range(9):
                self.__rindexes[i].append(s + j)

    # set column indexes for each column. key is column number and values are
    # number of each each entry inside that column
    # example:
    # self.__cindexes[0] = [0,9,18,27,36,45,54,63,72]
    def __setCIndexes(self):
        for i in range(9):
            c = i % 9
            self.__cindexes[i].append(c)
            for j in range(8):
                c = c + 9
                self.__cindexes[i].append(c)

    # set grid indexes for each grid. key is grid number and values are
    # number of each entry inside that grid
    # example:
    # self.__gindexs[0] = [0,1,2,9,10,11,18,19,20]
    def __setGIndexes(self):
        gStartIndexes = [0, 3, 6, 27, 30, 33, 54, 57, 60]

        for i in range(9):
            s = gStartIndexes[i]
            self.__gindexes[i].append(s)
            self.__gindexes[i].append(s + 1)
            self.__gindexes[i].append(s + 2)
            self.__gindexes[i].append(s + 9)
            self.__gindexes[i].append(s + 10)
            self.__gindexes[i].append(s + 11)
            self.__gindexes[i].append(s + 18)
            self.__gindexes[i].append(s + 19)
            self.__gindexes[i].append(s + 20)

    # set all neighbors for each entry. key is number of entry
    # and values are numbers of each entry in this row and this
    # column and this grid
    # example:
    # self.__adjacents[0] = [0,1,2,3,4,5,6,7,8,9,18,27,36,45,54,63,72,10,11,19,20]
    def __setAdjacents(self):
        for i in range(81):
            tmp = self.__entry2RCG(i)
            self.__adjacents[i] = list(set(self.__rindexes[tmp["r"]] + self.__cindexes[tmp["c"]] + self.__gindexes[tmp["g"]]))


    # get i'th row indexes of __rindexes.
    # just is a getter and no has any role in problem solving
    def getRIndexes(self, i):
        return self.__rindexes[int(i)]

    # get i'th column indexes of __cindexes
    # just a getter and no has any role in problem solving
    def getCIndexes(self, i):
        return self.__cindexes[int(i)]

    # get i'th grid indexes of __gindexes
    # just a getter and no has any role in problem solving
    def getGIndexes(self, i):
        return self.__gindexes[int(i)]

    # get all adjacents of one index
    # just a getter and no has any role in problem solving
    def getAdjacents(self, i):
        return self.__adjacents[int(i)]


    # return a sample sudoku.
    # this sample is just forpresentation of input format and no has 
    # and role in problem solving
    def getSampleSudoku(self):
        return self.__sampleSudoku


    # get entry and find its row, its column and its grid
    # example: entry2RCG(11)--->row:1, column:2, grid:0
    # Already only used inside the "setAdjacents" methos
    def __entry2RCG(self, entry):
        r = int(entry / 9)
        c = entry % 9

        if r <= 2 :
            g = 0 if c <= 2 else 1 if c <= 5 else 2
        elif r <= 5:
            g = 3 if c <= 2 else 4 if c <= 5 else 5
        else :
            g = 6 if c <= 2 else 7 if c <= 5 else 8

        return {'c':c, 'r':r, 'g':g}


    # prepare variable self.table for print on screen
    def __prepareForPrint(self, removeList = True, space = 1):
        tmp = {}
        for i in range(len(self.__table)):
            if type(self.__table[i]) == list and removeList:
                tmp[i] = "."
            elif type(self.__table[i]) == list:
                tmp[i] = (''.join(str(x) for x in self.__table[i]) + "*").center(space)
            else:
                tmp[i] = str(self.__table[i]).center(space)

        return tmp


    # print sudoko table. those entries that no have value will be displayed with a "."
    # Example:
    # We have this sudoko:
    # ..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..
    #
    # method "printTable" will have this output:
    # +---+---+---+
    # |..5|3..|...|
    # |8..|...|.2.|
    # |.7.|.1.|5..|
    # +---+---+---+
    # |4..|..5|3..|
    # |.1.|.7.|..6|
    # |..3|2..|.8.|
    # +---+---+---+
    # |.6.|5..|..9|
    # |..4|...|.3.|
    # |...|..9|7..|
    # +---+---+---+
    def printTable(self):
        tmp = self.__prepareForPrint()

        for i in list(map(lambda x: x[0], self.__rindexes)):
            if i % 27 == 0:
                print("+---+---+---+")

            print(
                    "|" + tmp[i+0] + tmp[i+1] + tmp[i+2] + \
                    "|" + tmp[i+3] + tmp[i+4] + tmp[i+5] + \
                    "|" + tmp[i+6] + tmp[i+7] + tmp[i+8] + "|"
            )

        print("+---+---+---+")


    # print possible table
    # for above sudoku output the printPossibleTable will be:
    # +---------------------------+---------------------------+---------------------------+
    # |  1269*     924*      5    |    3      24689*   24678* |  14689*   14679*   8147*  |
    # |    8       934*     169*  |  9467*    9456*     467*  |  1469*      2      1347*  |
    # |  9236*      7       926*  |  8946*      1      8246*  |    5       946*     834*  |
    # +---------------------------+---------------------------+---------------------------+
    # |    4       892*    26789* |  8169*     896*      5    |    3       197*     127*  |
    # |   925*      1       892*  |   894*      7       834*  |   924*     945*      6    |
    # |  9567*     95*       3    |    2       946*     146*  |   149*      8      1457*  |
    # +---------------------------+---------------------------+---------------------------+
    # |  1237*      6      8127*  |    5      8234*   123478* |  8124*     14*       9    |
    # |  12579*   8925*      4    |  8167*     826*    12678* |  8126*      3      8125*  |
    # |  1235*    8235*     812*  |  8146*    23468*     9    |    7      1456*    12458* |
    # +---------------------------+---------------------------+---------------------------+
    def printPossibleTable(self):
        space = 9
        tmp = self.__prepareForPrint(False, space)

        for i in list(map(lambda x: x[0], self.__rindexes)):
            if i % 27 == 0:
                print( ("+" + ("-" * space) * 3) * 3 + "+")

            print(
                    "|" + tmp[i+0] + tmp[i+1] + tmp[i+2] + \
                    "|" + tmp[i+3] + tmp[i+4] + tmp[i+5] + \
                    "|" + tmp[i+6] + tmp[i+7] + tmp[i+8] + "|"
            )

        print( ("+" + ("-" * space) * 3) * 3 + "+")


    # only find next best move. return entry and its finded value.
    # if variable "entry" is set then find best move for that entry
    # when no more move is possible return [-1, -1]
    # this value means that we have to RollBACK!
    # if each entry has its value return [1000, 1000]
    # this value means that sudoku is already solved.
    def findNextMove(self, entry = -1):
        count, minLength = 0, 1000

        if [] in self.__table.values():
            return [-1, -1]

        if entry != -1:
            tmp = sorted(self.__table[entry])
            if not len(tmp):
                return [-1, -1]
            return [entry, tmp[0]]


        for k, v in self.__table.items():
            if type(v) == list :
                count = count + 1
                if len(v) < minLength:
                    minLength = len(v)
                    entry = k


        if count == 0:
            return [1000, 1000]

        tmp = sorted(self.__table[entry])
        value = tmp[0]
        return [entry, value]


    # delete last move and call "updatepossibleTable()"
    def rollback(self):
        move = self.__moves.pop()
        entry, value = move[0], move[1]
        self.move(entry, [], value)
        return entry 

    # a getter for __count variable
    # no has any role in problem solving
    def getCount(self):
        return self.__count

    # get entry and value and set value in that entry
    def move(self, entry, value, onRollBackValueGreaterThan = -1):
        self.__table[entry] = value
        self.__count = self.__count + 1

        if type(value) != list:
            self.__moves.append([entry, value])

        if value == []:
            self.__updatePossibleTable(entry, onRollBackValueGreaterThan, fullUpdate = True)
        else:
            self.__updatePossibleTable(entry, onRollBackValueGreaterThan)


    # get moves variable
    # just a getter. no has any role in problem solving
    def getMoves(self):
        return self.__moves

    # update possible table
    # normally we call this function after each move and each rollback
    def __updatePossibleTable(self, entry = -1, valueGreaterThan = -1, fullUpdate = False):
        values = set()

        if fullUpdate == True:
            check = range(81)
        elif entry != -1:
            check = self.__adjacents[entry]
        else:
            print("Unknown update policy")
            sys.exit(1)

        for i in check:
            if type(self.__table[i]) != list:
                continue

            values.clear()
            for j in self.__adjacents[i]:
                if type(self.__table[j]) == list:
                    continue
                values.add(self.__table[j])

            possibles = list({1,2,3,4,5,6,7,8,9} - values)
            if i == entry:
                possibles = list(filter(lambda x: x > valueGreaterThan, possibles))

            self.__table[i] = possibles

    def markEntries(self, indexes):
        for i in range(9):
            start = i * 9

            if i % 3 == 0:
                print("+---+---+---+")

            for j in range(9):
                if j % 3 == 0:
                    print("|", end="")
                if (start + j) in indexes:
                    print("x", end="")
                else:
                    print(" ", end="")
            print("|")

        print("+---+---+---+")

    # solve sudoku by repeating these steps
    # 1- find best move or roll back last move
    # 2- move
    # go to step 1 
    def solve(self):
        # reset number of tries for resolving this sudoku
        self.__count = 0

        entry = -1
        # while true ...
        while(True):
            # find next move. if entry is set "findNextMove" will find next
            # value for specified entry
            entry, value = self.findNextMove(entry)

            # if we have no more moves and sudoku is solved then break
            if entry == 1000 and value == 1000:
                return  

            # last move is incorrect. Rollback!
            if entry == -1:
                entry = self.rollback()
                continue

            # set finded value in its entry
            self.move(entry, value)
            entry = -1


    def __repr__(self):
        return "another sudoku solver with python!"


if __name__ == "__main__" :
    # create object of sudoku with sudoku of user
    obj = Sudoku()

    # read sudoku from standard input or file
    # format of sudoku has to be similar:
    # ..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..
    for line in fileinput.input():
        string = line.rstrip()

        try:
            obj.setTable(string)
        except SyntaxError:
            print("Sudoku is not valid")
            print("Try something like: ", obj.getSampleSudoku())
            continue

        # print sudoku on screen
        obj.printTable()

        # solve sudoku
        obj.solve()

        # Already sudoku is solved
        print("Solved with ", obj.getCount(), " moves")

        # Display solved sudoku
        obj.printTable()
        print("@@@@@@@@@@@@@")