def solve_sudoku(filename, filename_out=None):
    """Open a sudoku located in filename and solve it.

    If filename_out is not None, the solved sudoku is saved.

    Arguments:
    filename -- the file name

    Keyword arguments:
    filename_out -- the output file name (default None)

    """
    board = Board(filename=filename)
    draw_board(board)

    print _(u"Solving sudoku..."),
    sys.stdout.flush()

    # Use all the algos
    sudoku = Sudoku(board, difficulty="hard")
    success = False
    if sudoku.solve():
        print _(u"success!")
        success = True
    else:
        print _(u"can't be solved!")

    draw_board(sudoku.to_board())

    if filename_out:
        sudoku.to_board().save(filename_out)

    return success

def csp_sdk(folder, instance):

    fo = open("problems/%d/%d.sd"%(folder,instance), "rw+")
    sys.setrecursionlimit(1000000)
    sudoku = Sudoku()

    for line in fo:
        l = line.split()
        tmp = []
        for i in l:
            tmp.append(int(i))
        if l:
            sudoku.add_row(tmp)

    fo.close()

    starter = sudoku.rst_cst_var()
    csp = Solver(sudoku, starter)
    result = csp.game()

    for l in result.sudoku:
        print l

    del sudoku

    print("\n")
    return csp.steps

def test_recursive_solve():
    rec_sudoku = " ,  ,  ,  , 5, 3,  ,  ,  ;\n" + \
                 "1,  ,  , 6,  ,  ,  ,  , 8;\n" + \
                 " , 5,  ,  ,  , 1,  , 4,  ;\n" + \
                 "4,  ,  ,  , 9,  , 5, 3,  ;\n" + \
                 " ,  , 9, 7,  , 6, 8,  ,  ;\n" + \
                 " , 2, 7,  , 3,  ,  ,  , 6;\n" + \
                 " , 4,  , 1,  ,  ,  , 8,  ;\n" + \
                 "2,  ,  ,  ,  , 7,  ,  , 1;\n" + \
                 " ,  ,  , 3, 2,  ,  ,  ,  ;\n"

    solution = "6, 8, 4, 2, 5, 3, 1, 7, 9;\n" + \
               "1, 9, 3, 6, 7, 4, 2, 5, 8;\n" + \
               "7, 5, 2, 9, 8, 1, 6, 4, 3;\n" + \
               "4, 1, 6, 8, 9, 2, 5, 3, 7;\n" + \
               "5, 3, 9, 7, 1, 6, 8, 2, 4;\n" + \
               "8, 2, 7, 4, 3, 5, 9, 1, 6;\n" + \
               "3, 4, 5, 1, 6, 9, 7, 8, 2;\n" + \
               "2, 6, 8, 5, 4, 7, 3, 9, 1;\n" + \
               "9, 7, 1, 3, 2, 8, 4, 6, 5;\n"

    sudoku = Sudoku()
    sudoku.read_string(rec_sudoku)
    sudoku.recursive_solve()
    assert_equal(str(sudoku), solution)

 def onPbjugarClicked(self):
     """Despliega la ventana con el tablero para empezar el juego
         *Crea una instancia de la clase Sudoku y la muestra.
         *Verificara que se halla escogido un solo nivel de dificultad.
         *Verificara que halla escogido al menos una opcion de alerta."""
     facil=self.ui.rBFacil.isChecked()
     medio=self.ui.rBMedio.isChecked()
     dificil=self.ui.rBDificil.isChecked()
     experto=self.ui.rBExperto.isChecked()
     invalida=self.ui.cbInvalidas.isChecked()
     incorrecta=self.ui.cbIncorrectas.isChecked()
     ayuda=self.ui.cbhelp.isChecked()
     if facil==False and medio==False and dificil==False and experto==False:
         self.MessageBox(None,"Seleccione Un Nivel De Dificultad..!","ERROR",self.MB_ICONERROR)
     elif invalida==False and incorrecta==False:
         self.MessageBox(None,"Seleccione al menos una opcion de alertas..!","ERROR",self.MB_ICONERROR)
     elif facil:
         self.n= Sudoku(1,invalida,incorrecta,ayuda,"")
         self.n.setVisible(True)
         self.close()
     elif medio:
         self.n= Sudoku(2,invalida,incorrecta,ayuda,"")
         self.n.setVisible(True)
         self.close()
     elif dificil:
         self.n= Sudoku(3,invalida,incorrecta,ayuda,"")
         self.n.setVisible(True)
         self.close()
     elif experto:
         self.n= Sudoku(4,invalida,incorrecta,ayuda,"")
         self.n.setVisible(True)
         self.close()

def main():
    with open('sudokus_3x3.txt', 'r') as myfile:
        content = myfile.readlines()

    # for each sudoku
    content = [content[0]] # for testing
    solved = 0
    for i in range(len(content)):
        line = content[i].strip()
        sudoku = Sudoku(line)
        sudoku.solve()
        if sudoku.is_solved:
            if ''.join(sudoku.sudoku) == borcic.sudoku99(line):
                solved += 1
            else:
                print 'My solution:', ''.join(sudoku.sudoku)
                print 'Expected:   ', borcic.sudoku99(line)
                raise RuntimeError('Got wrong solution!')
        else:
            print 'Couldnt finish Sudoku:\n', sudoku.to_string(), '\n'
            print 'Candidates are:\n', '\n'.join(['\t|'.join(line) for line in sudoku.candidates])
        print 'Solving sudoku', i, ':', sudoku.is_solved


    print 'Solved', solved, 'from a total of', len(content), 'sudokus (' + str(round((solved*100.0)/len(content), 2)) + '%)'

def _check_intersect(s, h1, h2):
    # When two houses intersect,
    # some numbers cannot at the same time be outside of the intersection
    # Thus they must be inside the intersection
    changed = 0
    log.append("In House {0} & {1}:", h1, h2)
    h1u = util.difference(h1, h2)  # h1 unique tiles
    h2u = util.difference(h2, h1)  # h2 unique tiles
    h1un = s.get_numbers(h1u)  # h1 unique numbers
    h2un = s.get_numbers(h2u)  # h2 unique numbers
    h1i = Sudoku.other(h1un)  # h1 intersect-only numbers
    h2i = Sudoku.other(h2un)  # h2 intersect-only numbers
    hi = util.union(h1i, h2i)  # intersect-only numbers
    if len(hi) > 0:
        @log.rollback
        def rem():
            log.indent()
            log.append("Intersection contains {0}", hi)
            log.indent()
            result = max(section_remove(s, h2u, h1i), section_remove(s, h1u, h2i))
            log.dedent(2)
            return result

        changed = rem()
    return changed

    def test_solve(self):
        # Setup
        sudoku = Sudoku(puzzle=PUZZLE)

        # Run
        sudoku.solve()

        # Verify
        self.assertEqual(sudoku.puzzle, PUZZLE)
        self.assertEqual(sudoku.solution, SOLUTION)

def test_read_string():
    str1 = " , 9,  ,  ,  ,  , 2,  , 5;\n" + \
           "2,  ,  , 3,  ,  , 8, 9,  ;\n" + \
           " ,  ,  ,  , 2, 5,  , 7,  ;\n" + \
           " ,  , 1,  , 6,  ,  ,  , 2;\n" + \
           " , 3,  ,  , 9,  ,  , 5,  ;\n" + \
           "9,  ,  ,  , 1,  , 4,  ,  ;\n" + \
           " , 5,  , 7, 4,  ,  ,  ,  ;\n" + \
           " , 6, 3,  ,  , 8,  ,  , 9;\n" + \
           "7,  , 4,  ,  ,  ,  , 6,  ;\n"
    sudoku = Sudoku()
    sudoku.read_string(str1)
    assert_equal(str(sudoku), str1)

def test_incorrect_sudoku():
    incorrect = "1, 2, 3,  ,  ,  ,  ,  ,  ;\n" + \
                "4, 5, 6,  ,  ,  ,  ,  ,  ;\n" + \
                "7, 8,  , 9,  ,  ,  ,  ,  ;\n" + \
                " ,  ,  ,  ,  ,  ,  ,  ,  ;\n" + \
                " ,  ,  ,  ,  ,  ,  ,  ,  ;\n" + \
                " ,  ,  ,  ,  ,  ,  ,  ,  ;\n" + \
                " ,  ,  ,  ,  ,  ,  ,  ,  ;\n" + \
                " ,  ,  ,  ,  ,  ,  ,  ,  ;\n" + \
                " ,  ,  ,  ,  ,  ,  ,  ,  ;\n"
    sudoku = Sudoku()
    sudoku.read_string(incorrect)
    sudoku.recursive_solve()

def solve(s: Sudoku):
    pos = s.getFirstFreePosition()
    if pos is None:
        return s
    x, y = pos
    for v in range(1, 10):
        if s.isMoveCorrect(x, y, v):
            newS = s.clone()
            newS.setAtPosition(x, y, v)
            solved = solve(newS)
            if solved is not None:
                return solved
    return None

class Test(unittest.TestCase):

    def setUp(self):
        str_sudoku = """003020600
                        900305001
                        001806400
                        008102900
                        700000008
                        006708200
                        002609500
                        800203009
                        005010300"""

        int_sudoku = []
        for line in str_sudoku.split("\n"):
            int_sudoku.append([int(i) for i in list(line.strip())])
        self.s = Sudoku(int_sudoku)

    def testGetRowCells(self):
        print "-------------"
        for i in range(9):
            result = self.s.get_row_cells(i)
            for cell in result:
                print cell.value,
            print ""

    def testGetColCells(self):
        print "-------------"
        for j in range(9):
            result = self.s.get_col_cells(j)
            for cell in result:
                print cell.value,
            print ""

    def testGetColCells(self):
        print "-------------"
        for i in range(0, 9, 3):
            for j in range(0, 9, 3):
                result = self.s.get_sect_cells(i, j)
                for cell in result:
                    print cell.value,
                print ""

    def testGetCellPositionInSect(self):
        print "-------------"
        print "testGetCellPositionInSect"
        for i in range(0, 9, 3):
            for j in range(0, 9, 3):
                for cell_place in range(9):
                    print "i, j, cell_place --> result: %s, %s, %s, %s" % (i, j, cell_place, self.s.get_cell_position_in_sect(i, j, cell_place))
        print "-------------"

def gen_test(file_name):
    """Функция генерирует тест-case из файла
    """
    in_file = open(file_name)
    size = int(in_file.readline())
    in_file.close()
    sudoku = Sudoku(size, False)
    gb = sudoku.load_gb_from_file(file_name)

    def test_func(self):
        self.assertTrue(sudoku.get_solution(gb))
        self.assertTrue(sudoku.is_solution(gb))

    return test_func

 def solve(self):
     # Read values from the grid
     values = [[self.get_value(row, col) for col in range(9)] for row in range(9)]
     # Try to solve the Sudoku
     solver = Sudoku(values)
     if solver.solve():
         for row in range(9):
             for col in range(9):
                 self.text_inputs[9 * row + col].text = str(solver.get_value(row, col))
     else:
         error_message = ErrorMessage()
         self.error_messages.append(error_message)
         self.add_widget(error_message)
         Clock.schedule_once(self.remove_error_message, 2)

def main():
    sudoku = Sudoku(3)
    print(sudoku)
#    sudoku.feed([1,2,4,3,3,None,None,None,2,1,3,None,None,3,2,1])
    # test
    #sudoku.feed([None,7,5,None,9,None,None,None,6,None,2,3,None,8,None,None,4,None,8,None,None,None,None,3,None,None,1,5,None,None,7,None,2,None,None,None,None,4,None,8,None,6,None,2,None,None,None,None,9,None,1,None,None,3,9,None,None,4,None,None,None,None,7,None,6,None,None,7,None,5,8,None,7,None,None,None,1,None,3,9,None])
    # rem
    #sudoku.feed([None,5,None,None,None,None,2,8,None,None,None,None,None,7,6,None,None,None,None,None,2,1,None,None,None,None,None,9,4,None,None,1,None,None,None,None,None,None,1,5,None,4,None,None,None,None,None,6,None,None,3,9,None,None,6,None,None,3,None,None,None,None,None,None,2,None,7,None,1,6,4,None,None,None,None,None,None,None,5,None,3])
    sudoku.feed([5,4,8,None,6,None,None,None,None,None,None,None,5,None,None,None,None,2,None,None,None,3,None,4,None,7,None,7,None,1,None,None,None,None,None,None,2,9,None,None,None,None,1,5,4,None,3,5,None,None,None,None,9,None,6,2,None,None,None,None,None,1,None,None,None,None,None,None,None,None,6,None,9,None,None,None,None,3,4,None,None])
    print(sudoku)
    solver = Solver(sudoku)
    solved = solver.solve()
    if solved: print("SOLVED !!")
    print(sudoku)
    sudoku.printIncertitudes()

 def test_solved_puzzle_is_solved(self):
     """example taken from http://www.sudokugame.com/rules.php"""
     tmp = Sudoku()
     tmp[0] = [2,4,8,3,9,5,7,1,6]
     tmp[1] = [5,7,1,6,2,8,3,4,9]
     tmp[2] = [9,3,6,7,4,1,5,8,2]
     tmp[3] = [6,8,2,5,3,9,1,7,4]
     tmp[4] = [3,5,9,1,7,4,6,2,8]
     tmp[5] = [7,1,4,8,6,2,9,5,3]
     tmp[6] = [8,6,3,4,1,7,2,9,5]
     tmp[7] = [1,9,5,2,8,6,4,3,7]
     tmp[8] = [4,2,7,9,5,3,8,6,1]
     self.assertTrue(tmp.solved())
     self.assertFalse(tmp.has_zero())
     self.assertTrue(tmp.consistent())

class TestDLX(unittest.TestCase):

    def setUp(self):
        self.sudoku = Sudoku(validate=True, pretty=False)

    def read_line_by_line(self, filename, callback):
        lines = open(filename)
        for line in lines:
            self.assertEqual(len(line), 82)
            self.assertEqual(line[81], '\n')
            callback(line[:81])

    def assert_exception(self, line):
        self.assertRaises(SudokuError, self.sudoku.solve, line)

    def assert_valid(self, line):
        grids = self.sudoku.solve(line)
        self.assertEqual(len(grids), 1)

    def test_bad_solutions(self):
        filename = 'tests/data/collections/bad'
        self.read_line_by_line(filename, self.assert_exception)

    def test_valid_solutions(self):
        filename = 'tests/data/collections/hardest'
        self.read_line_by_line(filename, self.assert_valid)

 def onCargajuegoClicked(self):
     """Nos permite Cargar un juego anteriormente guardado"""
     (nombre,ok) = QInputDialog.getText(self, self.tr("Sudoku"), self.tr("Nombre:"),QLineEdit.Normal, self.tr(""))
     if ok==True:
         while str(nombre)=="" and ok==True:
             self.MessageBox(None,"Ingrese Un Nombre..!","ERROR",self.MB_ICONERROR)
             (nombre,ok) = QInputDialog.getText(self, self.tr("Sudoku"), self.tr("Nombre:"),QLineEdit.Normal, self.tr(""))
         if ok==True:
             archivo=open("Partidas.txt","r")
             linea=archivo.readline()
             Existe=0
             while linea!="":
                 partida=linea.split(",")
                 nombreG=partida[0]
                 if str(nombre)==nombreG:
                     Existe=1
                     break
                 linea=archivo.readline()
             if Existe==1:
                 invalida=partida[3]
                 incorrecta=partida[4]
                 ayuda=partida[5]
                 self.n= Sudoku(5,invalida,incorrecta,ayuda,partida)
                 self.n.setVisible(True)
                 self.close()
             else:
                 self.MessageBox(None,"No Se Encontro El Archivo..!","ERROR",self.MB_ICONERROR)
             archivo.close()

    def __init__(self, size=3):
        Gtk.Window.__init__(self, title="Sudoku Example")

        self.size = size

        # This is an instance of a Sudoku solver
        self.sudoku = Sudoku(size)

        # Draw the window
        self.table = [[Gtk.Entry() for _ in xrange(size**2)]
                                   for _ in xrange(size**2)]
        vbox = Gtk.Box(orientation=Gtk.Orientation.VERTICAL)
        self.add(vbox)

        grid = Gtk.Grid()
        vbox.add(grid)

        for row,lst in enumerate(self.table):
            for col,entry in enumerate(lst):
                entry.set_max_length(3)
                entry.set_hexpand(True)
                entry.set_vexpand(True)
                entry.set_width_chars(2)
                grid.attach(entry, col, row, 1, 1)

        self.solve_button = Gtk.Button(label="Solve")
        self.solve_button.set_hexpand(True)
        vbox.add(self.solve_button)
        self.solve_button.connect("clicked", self.solve)

        self.clear_button = Gtk.Button(label="Clear")
        self.clear_button.set_hexpand(True)
        vbox.add(self.clear_button)
        self.clear_button.connect("clicked", self.clear)

def _colouring(s, poss, doubles, verbose=0):
    changes = 0
    group_a = []
    group_b = []
    for [d1, d2] in doubles:
        if d1 in group_a:
            group_b.append(d1)
            group_a.append(d2)
        elif d1 in group_b:
            group_a.append(d1)
            group_b.append(d2)
    # for loc in set(group_a) & set(group_b):
    #     if poss in s.fields[loc]:
    #         changes += 1
    #         s.fields[loc].remove(poss)
    # if changes:
    #     return changes
    for group in (group_a, group_b):
        rows = []
        cols = []
        for loc in group:
            r, c = Sudoku.i2rc(loc)
            if r in rows or c in cols:
                changes += _eliminate_group(s, poss, group, verbose)
                break
            rows.append(r)
            cols.append(c)
    return changes

    def test_puzzlefy_l33t(self):
        # Setup
        sudoku = Sudoku(solution=SOLUTION, level="l33t")

        # Run
        sudoku.puzzlefy()

        # Verify
        empty_cells = sudoku.puzzle.count("0")
        self.assertLessEqual(empty_cells, MAX_EMPTY_CELLS_L33T)
        self.assertEqual(sudoku.solution, SOLUTION)

        # Run
        sudoku.solve()

        # Verify
        self.assertEqual(sudoku.solution, SOLUTION)