Graphs algorithm to solve Sudoku

Question

Graphs algorithm to solve Sudoku

Navigation

#1 by (1 votes)

1

I am having a doubt, my code when it runs on one of the Sudoku examples, it printa in the end the expected result, the other sudoku example it does not correctly print the expected result. I wonder what's going on, try to understand

import netrkx as nx 
import sys
nodes = [['00', '01', '02', '03', '04', '05', '06', '07', '08'],
         ['10', '11', '12', '13', '14', '15', '16', '17', '18'],
         ['20', '21', '22', '23', '24', '25', '26', '27', '28'],
         ['30', '31', '32', '33', '34', '35', '36', '37', '38'],
         ['40', '41', '42', '43', '44', '45', '46', '47', '48'],
         ['50', '51', '52', '53', '54', '55', '56', '57', '58'],
         ['60', '61', '62', '63', '64', '65', '66', '67', '68'],
         ['70', '71', '72', '73', '74', '75', '76', '77', '78'],
         ['80', '81', '82', '83', '84', '85', '86', '87', '88']]

square = [['00', '01', '02', '10', '11', '12', '20', '21', '22'],
          ['03', '04', '05', '13', '14', '15', '23', '24', '25'],
          ['06', '07', '08', '16', '17', '18', '26', '27', '28'],
          ['30', '31', '32', '40', '41', '42', '50', '51', '52'],
          ['33', '34', '35', '43', '44', '45', '53', '54', '55'],
          ['36', '37', '38', '46', '47', '48', '56', '57', '58'],
          ['60', '61', '62', '70', '71', '72', '80', '81', '82'],
          ['63', '64', '65', '73', '74', '75', '83', '84', '85'],
          ['66', '67', '68', '76', '77', '78', '86', '87', '88']]

def welshpowell(g):
for node in g.node:
    if not g.node[node]['status']:
        for e in g.neighbors(node):
            if g.node[e]['status']:
                try:
                    g.node[node]['color'].remove(g.node[e]['color'])
                except:
                    pass

def update(g):
for node in g.node:
    if not g.node[node]['status'] and len(g.node[node]['color']) == 1:
        g.node[node]['status'] = True
        g.node[node]['color'] = g.node[node]['color'][0]

def clear(g):
for node in g.node:
    if g.node[node]['status'] and type(g.node[node]['color']) != int:
        g.node[node]['status'] = False

def engage(g):
for i in range(9):
    for j in range(9):
        if not g.node[nodes[i][j]]['status']:
            g.node[nodes[i][j]]['status'] = True
            welshpowell(g)
            update(g)
clear(g)

def main(argv):
try:
    filename = argv[1]
except IndexError:
    print 'Usage: python sudoku.py filename'
    sys.exit(-1)

# create graph
g = nx.Graph()

# open and read file
fp = open(filename, 'r')
data = fp.read().split('\n')
data.remove('')
sudoku = []
for line in data:
    sudoku.append(line.split(' '))

# create node with color and status
for i in range(9):
    for j in range(9):
        if sudoku[i][j] == 'x':
            g.add_node(nodes[i][j], color=[1, 2, 3, 4, 5, 6, 7, 8, 9], status=False)
        else:
            g.add_node(nodes[i][j], color=int(sudoku[i][j]), status=True)


# create edges of rows
for i in range(9):
    for j in range(8):
        for k in range(j, 8):
            g.add_edge(nodes[i][j], nodes[i][k + 1])

# create edges of columns
for i in range(8):
    for j in range(9):
        for k in range(i, 8):
            g.add_edge(nodes[i][j], nodes[k + 1][j])

for i in range(9):
    for j in range(8):
        for k in range(j, 8):
            g.add_edge(square[i][j], square[i][k + 1])

for i in range(9):
    engage(g)
    welshpowell(g)
    update(g)

for i in range(9):
    for j in range(9):
        print g.node[nodes[i][j]]['color'],
    print

if __name__ == '__main__':
main(sys.argv)

Test file 1

5 3 x x 7 x x x x
6 x x 1 9 5 x x x
x 9 8 x x x x 6 x
8 x x x 6 x x x 3
4 x x 8 x 3 x x 1
7 x x x 2 x x x 6
x 6 x x x x 2 8 x
x x x 4 1 9 x x 5
x x x x 8 x x 7 9

Where the result is:

Testfile2

8xx4x6xx7xxxxxx4xxx1xxxx65x5x9x3x78xxxxx7xxxxx48x2x1x3x52xxxx9xxx1xxxxxx3xx9x2xx5

Andasaresult:

I would like to understand why the results are not coming out exactly where I am wrong. Since the code should work for any generic sudoku.

python grafo

asked by anonymous 28.03.2018 / 23:23

1 answer

Select MySQL with 3 arrays How to use Bootstrap 'shortcuts' in VSCode in .blade files?

score 1 · Accepted Answer

It is because in the second case, the information in the file is insufficient for the resolution ... By fixing another number the solution becomes possible (I added 3 in the second position of the 1st line:

8 3 x 4 x 6 x x 7
x x x x x x 4 x x
x 1 x x x x 6 5 x
5 x 9 x 3 x 7 8 x
x x x x 7 x x x x
x 4 8 x 2 x 1 x 3
x 5 2 x x x x 9 x
x x 1 x x x x x x
3 x x 9 x 2 x x 5

Result:

8  3  5  4  1  6  9  2  7  
2  9  6  8  5  7  4  3  1  
4  1  7  2  9  3  6  5  8  
5  6  9  1  3  4  7  8  2  
1  2  3  6  7  8  5  4  9  
7  4  8  5  2  9  1  6  3  
6  5  2  7  8  1  3  9  4  
9  8  1  3  4  5  2  7  6  
3  7  4  9  6  2  8  1  5

For this case:

 x 2 x 5 x 1 x 9 x
 8 x x 2 x 3 x x 6
 x 3 x x 6 x x 7 x
 x x 1 x x x 6 x x
 5 4 x x x x x 1 9
 x x x x 2 x x x 6
 x 6 x x x x 2 8 x
 x x x 4 1 9 x x 5
 x x x x 8 x x 7 9

In this case, there are two six in the right column, so it's insoluble !!!

In this code for python3 I added a function to validate if sudoku is not invalid:

import networkx as nx
import sys
nodes = [['00', '01', '02', '03', '04', '05', '06', '07', '08'],
         ['10', '11', '12', '13', '14', '15', '16', '17', '18'],
         ['20', '21', '22', '23', '24', '25', '26', '27', '28'],
         ['30', '31', '32', '33', '34', '35', '36', '37', '38'],
         ['40', '41', '42', '43', '44', '45', '46', '47', '48'],
         ['50', '51', '52', '53', '54', '55', '56', '57', '58'],
         ['60', '61', '62', '63', '64', '65', '66', '67', '68'],
         ['70', '71', '72', '73', '74', '75', '76', '77', '78'],
         ['80', '81', '82', '83', '84', '85', '86', '87', '88']]

square = [['00', '01', '02', '10', '11', '12', '20', '21', '22'],
          ['03', '04', '05', '13', '14', '15', '23', '24', '25'],
          ['06', '07', '08', '16', '17', '18', '26', '27', '28'],
          ['30', '31', '32', '40', '41', '42', '50', '51', '52'],
          ['33', '34', '35', '43', '44', '45', '53', '54', '55'],
          ['36', '37', '38', '46', '47', '48', '56', '57', '58'],
          ['60', '61', '62', '70', '71', '72', '80', '81', '82'],
          ['63', '64', '65', '73', '74', '75', '83', '84', '85'],
          ['66', '67', '68', '76', '77', '78', '86', '87', '88']]

# Algoritmo weshpower
def welshpowell(g):
    for node in g.node:
        if not g.node[node]['status']:  # O nó não está fixo
            for e in g.neighbors(node):   # Verifica todas as linhas e colunas do nó
                if g.node[e]['status']:   # Se o vizinho (linha e coluna) está fixo ou seja, existe apenas um ...
                    try:
                        g.node[node]['color'].remove(g.node[e]['color'])  # remove o número do nó
                    except:
                        pass

# Se exitir uma única cor, assume que a cor é esta
def update(g):
    for node in g.node:
        # se existir somente uma cor no NÓ, muda o no para TRUE e assume que a cor do NÓ é esta
        if not g.node[node]['status'] and len(g.node[node]['color']) == 1:
            g.node[node]['status'] = True
            g.node[node]['color'] = g.node[node]['color'][0]


# percorre todos os nós,
# se o estatudo do nó for verdadeiro e o typo do nó não for inteiro,
# ou seja, se existir um array, então o estado do nó pasa para falso
def clear(g):
    for node in g.node:
        if g.node[node]['status'] and type(g.node[node]['color']) != int:
            g.node[node]['status'] = False

def engage(g):
    for i in range(9):
        for j in range(9):
            # Se o estado do nó não é verdadeiro
            if not g.node[nodes[i][j]]['status']:
                # Seta verdadiero
                g.node[nodes[i][j]]['status'] = True
                # Executa o algoritmo (ou seja, executa o algoritmo para cada X)
                welshpowell(g)
                update(g)
    clear(g)

# Coordenada em linha x coluna
def coord(c):
    return "linha: %i Coluna: %i " % ( int(c[0])+1 , int(c[1])+1  )

# Verifica a validade do Sudoku (sem repetições
def checa_validade(g):
    valido=True
    for node in g.node:
        if g.node[node]['status']:
            for e in g.neighbors(node):
                if g.node[node]['status'] and  g.node[e]['status'] and g.node[node]['color'] == g.node[e]['color']:

                    print('Invalido: número %s em %s e número %s em %s' %( g.node[node]['color'], coord(node) , g.node[e]['color'], coord(e)))
                    valido=False
    return valido


def main(argv):
    try:
        filename = argv[1]
    except IndexError:
        print( 'Usage: python sudoku.py filename')
        sys.exit(-1)

    # create graph
    g = nx.Graph()

    # open and read file
    fp = open(filename, 'r')
    data = fp.read().split('\n')
    data.remove("")
    sudoku = []
    for line in data:
        sudoku.append(line.split(' '))

    print("inicio")
    for i in range(9):
        for j in range(9):
            print( sudoku[i][j]," ", end="")

        print("")
    print("")
    # create node with color and status
    for i in range(9):
        for j in range(9):

            if sudoku[i][j] == 'x':
                # Se for x, todas as possibilidades existem
                g.add_node(nodes[i][j], color=[1, 2, 3, 4, 5, 6, 7, 8, 9], status=False)
            else:
                # senão o valor é fixo
                g.add_node(nodes[i][j], color=int(sudoku[i][j]), status=True)


    # create edges of rows
    for i in range(9):
        for j in range(8):
            for k in range(j, 8):
                g.add_edge(nodes[i][j], nodes[i][k + 1])

    # create edges of columns
    for i in range(8):
        for j in range(9):
            for k in range(i, 8):
                g.add_edge(nodes[i][j], nodes[k + 1][j])

    # cria os edges das diagonais
    for i in range(9):
        for j in range(8):
            for k in range(j, 8):
                g.add_edge(square[i][j], square[i][k + 1])


    if( not checa_validade(g)):
        print("Este sudoku é inválido")
        exit(1)

    # Executa 9 vezes
    for i in range(9):
        engage(g)
        welshpowell(g)
        update(g)

    for i in range(9):
        for j in range(9):
            print( g.node[nodes[i][j]]['color']," ",end="")
        print()

if __name__ == '__main__':
    main(sys.argv)

Running there for the case you reported the result to is

inicio
x  2  x  5  x  1  x  9  x  
8  x  x  2  x  3  x  x  6  
x  3  x  x  6  x  x  7  x  
x  x  1  x  x  x  6  x  x  
5  4  x  x  x  x  x  1  9  
x  x  x  x  2  x  x  x  6  
x  6  x  x  x  x  2  8  x  
x  x  x  4  1  9  x  x  5  
x  x  x  x  8  x  x  7  9  

Invalido: número 6 em linha: 2 Coluna: 9  e número 6 em linha: 6 Coluna: 9 
Invalido: número 7 em linha: 3 Coluna: 8  e número 7 em linha: 9 Coluna: 8 
Invalido: número 6 em linha: 4 Coluna: 7  e número 6 em linha: 6 Coluna: 9 
Invalido: número 9 em linha: 5 Coluna: 9  e número 9 em linha: 9 Coluna: 9 
Invalido: número 6 em linha: 6 Coluna: 9  e número 6 em linha: 2 Coluna: 9 
Invalido: número 6 em linha: 6 Coluna: 9  e número 6 em linha: 4 Coluna: 7 
Invalido: número 7 em linha: 9 Coluna: 8  e número 7 em linha: 3 Coluna: 8 
Invalido: número 9 em linha: 9 Coluna: 9  e número 9 em linha: 5 Coluna: 9

This sudoku is invalid