Algorithm Graphs to solve Sudoku

Asked

Viewed 471 times

1

I’m having a doubt, my code when it runs in one of the examples of Sudoku, it prints at the end the expected result, the other example of sudoku it does not print correctly the expected result. I’d like to know 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: Resultado

Test file 2

8 x 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

And as a result: inserir a descrição da imagem aqui

I’d like to understand why it’s not coming out the same as the results, where I’m going wrong. The code should work for any Generic sudoku.

python graph

1 answer

1


It’s because in the second case, the information in the file is insufficient for resolution... By fixing a further number the solution becomes possible (I added the 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

Upshot:

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 sixes in the right column, so it is insoluble!!!

In this python3 code 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)

There running for the case you informed the result 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

  • And for this case, what are the missing ones? 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 Apologies cannot properly format this new sudoku

  • I edited the answer @Danielrosendodesouza! The good thing is to adjust the algorithm for it KICK all possibilities when there is no resolution by logic.

  • Thank you very much for the help <3

  • You can do one more step that in case of no resolution makes a systematic kick until it is solvable!!!

Browser other questions tagged python graph

You are not signed in. Login or sign up in order to post.