Solucionador - BackTracking Recursivo.ipynb

{"cells":[{"metadata":{"trusted":true},"cell_type":"code","source":"grid_nao_eficiente = [\n    [0, 0, 0, 0, 0, 0, 0, 0, 0],\n    [0, 0, 0, 0, 0, 3, 0, 8, 5],\n    [0, 0, 1, 0, 2, 0, 0, 0, 0],\n    [0, 0, 0, 5, 0, 7, 0, 0, 0],\n    [0, 0, 4, 0, 0, 0, 1, 0, 0],\n    [0, 9, 0, 0, 0, 0, 0, 0, 0],\n    [5, 0, 0, 0, 0, 0, 0, 7, 3],\n    [0, 0, 2, 0, 1, 0, 0, 0, 0],\n    [0, 0, 0, 0, 4, 0, 0, 0, 9]]\n\ngrid_eficiente = [\n    [5, 3, 0, 0, 7, 0, 0, 0, 0],\n    [6, 0, 0, 1, 9, 5, 0, 0, 0],\n    [0, 9, 8, 0, 0, 0, 0, 6, 0],\n    [8, 0, 0, 0, 6, 0, 0, 0, 3],\n    [4, 0, 0, 8, 0, 3, 0, 0, 1],\n    [7, 0, 0, 0, 2, 0, 0, 0, 6],\n    [0, 6, 0, 0, 0, 0, 2, 8, 0],\n    [0, 0, 0, 4, 1, 9, 0, 0, 5],\n    [0, 0, 0, 0, 8, 0, 0, 0, 0]]\n\ngrid = grid_eficiente\ndecisao = 1\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def possivel(y, x, n):\n    global grid\n    for i in range(0, 9):\n        if grid[y][i] == n:\n            return False\n    for i in range(0, 9):\n        if grid[i][x] == n:\n            return False\n    x0 = (x // 3) * 3\n    y0 = (y // 3) * 3\n    for i in range(0, 3):\n        for j in range(0, 3):\n            if grid[y0 + i][x0 + j] == n:\n                return False\n    return True","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def exibe_grid(grid):\n    for linha in grid:\n        print(linha)\n    print(\"---------------------------\")\n\n    ","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def exibe_console(grid):\n    global decisao\n    exibe_grid(grid)\n    decisao = int(input(\"Digite 1 para próximo passo e 2 para solucionar por completo: \"))\n    return","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def soluciona():\n    global grid\n    global decisao\n    for y in range(9):\n        for x in range(9):\n            # Procura quadradinhos vazios\n            if grid[y][x] == 0:\n                for n in range(1, 10):\n                    # Se for possivel colocar algum valor no quadradinho vazio\n                    if possivel(y, x, n):\n                        if (decisao == 1):\n                            exibe_console(grid)\n                        # Preenche com o vaklor\n                        grid[y][x] = n\n                        # Aqui nós reduzimos o problema, então é uma boa chamada para recursao\n                        soluciona()\n                        # Se ele nao consegui completar a solucao, é porque foi uma escolha ruim\n                        # Entao a gente remove o valor, da um passo pra tras (backtracking)\n                        grid[y][x] = 0\n                # Se ele tentou todos os valores possiveis para um vazio\n                # e não deu certo, então ele retorna sem solucão\n                return\n    print(\"---------Solucao Final---------\")\n    exibe_grid(grid)\n    input(\"Mais solucao? \")\n    decisao = 1\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"soluciona()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"","execution_count":null,"outputs":[]}],"metadata":{"celltoolbar":"Attachments","kernelspec":{"name":"python3","display_name":"Python 3","language":"python"},"language_info":{"name":"python","version":"3.7.8","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"}},"nbformat":4,"nbformat_minor":4}