Já jogou algum desses apps para smartphone e ficou com vontade de criar um pequeno programa pra resolvê-lo? Pode ser que não, 😂 afinal de contas o objetivo dos jogos é realmente passar o tempo resolvendo. Mas se como eu, você já ficou curioso ou teve essa vontade, dê uma conferida neste artigo.
Nonogram
Eu já tinha jogado o Nonogram antes, mas em algum momento enjoei (como acontece com a maioria desses puzzles) e exclui o app. Quando me deparei com ele de novo em um anúncio eu logo baixei e percebi que resolvia todos os tabuleiros sempre da mesma maneira, como se já tivesse um algoritmo na minha cabeça!
Se você não conhece ou não lembra das regras, elas são bem simples. As linhas e colunas possuem números indicando quantos quadrados devem estar preenchidos. Se quiser você pode baixar o jogo e ver o tutorial do início.
Criando um jogo
Para poder fazer alguns testes de como resolver um tabuleiro, primeiro precisamos simular um jogo em nosso programa. Vamos criar um tabuleiro (que chamei de grid) com quadrados preenchidos aleatoriamente e contar as quantidades dos que estão preenchidas.
Apesar de gostar muito de programar utilizando orientação a objetos, optei por utilizar a programação funcional neste projeto apenas para praticar mesmo.
Nosso grid é nada mais que uma matriz em que os valores podem ser:
1se estiver preenchido;0se não estiver; eNonepara um valor não definido.
Vamos então criar uma matriz nxn e preencher com os números 0e 1 aleatoriamente:
import random
def create_grid(n, chances=1):
grid = []
for i in range(n):
line = []
for j in range(n):
rand = random.randint(0, 1)
line.append(rand)
grid.append(line)
return gridPara facilitar nosso trabalho, vamos criar uma função para imprimir um grid e economizar algumas linhas de código:
def print_grid(grid):
for line in grid:
print(line)A princípio temos uma função que cria nosso grid, porém o problema nos impõe uma restrição: linhas e colunas tem que ter pelo menos um quadrado preenchido, ou seja, não podemos ter linhas ou colunas só com 0.
Vamos criar uma função então que valida um tabuleiro criado seguindo os passos:
- uma matriz vazia não é válida;
- checar todas as linhas de
grid; - transpor a matriz
grid; e - checar todas as linhas da nova matriz transposta (as colunas da matriz original).
Caso você não saiba ou não lembre o que é uma matriz transposta, ela é a matriz em que transformamos linhas em colunas e colunas em linhas. Você pode ler mais aqui.
def valid_grid(grid):
if grid == []:
return False
for line in grid:
if sum(line) == 0:
return False
tgrid = transpose_grid(grid)
for line in tgrid:
if sum(line) == 0:
return False
return TruePara transpor o nosso grid, basta um loop pelos índices das linhas, transformando colunas em linhas.
def transpose_grid(grid):
return [[row[i] for row in grid] for i in range(len(grid))]Finalmente, podemos criar nosso grid até que seja criado um tabuleiro válido:
if __name__ == '__main__':
n = 5
grid = []
while not valid_grid(grid):
grid = create_grid(n)
print_grid(grid)Imprimindo uma matriz como essa:
[1, 0, 1, 1, 0]
[1, 0, 1, 0, 1]
[0, 0, 1, 1, 1]
[1, 0, 0, 0, 1]
[0, 1, 1, 1, 0]Agora que temos a matriz, podemos criar os números que aparecem nas colunas e nas linhas apenas contando o número de 1 que aparecem em cada linha e coluna do grid.
A função deve percorrer cada linha, item a item. Caso seja um 1, incrementa um contador. Caso seja um 0 e o contador não seja, adiciona o contador à linha e zera o mesmo.
Podemos aproveitar nossa função que transpõe a matriz para calcular as somas das colunas da mesma maneira que calculamos para as linhas, só que com a matriz transposta.
Não podemos esquecer de ao final verificar se o contador tem algum valor (acontece quando a linha termina em 1 e não temos nenhum 0 para verificar o valor do contador).
def get_counts(grid):
lines = []
n = len(grid)
for i in range(n):
line = []
count = 0
for j in range(n):
if grid[i][j] == 1:
count += 1
elif grid[i][j] == 0:
if count != 0:
line.append(count)
count = 0
if count != 0:
line.append(count)
count = 0
lines.append(line)
return linesAgora basta utilizar para nosso grid logo depois de criá-lo:
if __name__ == '__main__':
n = 5
grid = []
while not valid_grid(grid):
grid = create_grid(n)
print_grid(grid)
lines = get_counts(grid)
cols = get_counts(transpose_grid(grid))
print('lines', lines)
print('cols', cols)E temos o seguinte resultado:
[1, 0, 1, 1, 0]
[1, 0, 1, 0, 1]
[0, 0, 1, 1, 1]
[1, 0, 0, 0, 1]
[0, 1, 1, 1, 0]
lines [[1, 2], [1, 1, 1], [3], [1, 1], [3]]
cols [[2, 1], [1], [3, 1], [1, 1, 1], [3]]Resolvendo o problema
Vamos resolver o problema de maneira bem “simples” para nós, mas que pode ser custosa demais para o computador caso não tomemos alguns cuidados.
A solução é começar por todas as possibilidades possíveis para cada linha e depois para cada coluna.
Vamos pegar as linhas do tabuleiro anterior como exemplo. Na primeira linha temos [1, 2], o que nos da as possibilidades:
[1, 0, 1, 1, 0][1, 0, 0, 1, 1][0, 1, 0, 1, 1]
Permutações
Mas como chegar nessas possibilidades para qualquer linha?
Como sabemos que temos um 1 e depois dois 1 (as regras do jogo ditam que deve ser nessa ordem), podemos escrever a linha na forma abaixo, sendo os ___ uma quantidade ainda não determinada de 0:
[ ___ [1] ___ [1, 1] ___ ]Porém não podemos ter o bloco [1] colado ao [1, 1] então precisamos de pelo menos um 0 entre eles. Podemos reescrever o padrão como:
[ ___ [1] ___ [0] ___ [1, 1] ___ ]A quantidade de blocos [0] será sempre a quantidade de blocos com 1 menos 1, e a quantidade de 0 adicionais será o tamanho do tabuleiro menos a soma dos tamanhos dos blocos (no exemplo, 5 – 4 = 1).
Então o problema agora seria achar 4 números que somados resultam em 1.
a + b + c + d = 1Por exemplo se a = 0, b = 1, c = 0, d = 0 temos a permutação [1, 0, 1, 1, 0].
Então vamos primeiro criar uma função que a partir de um número de blocos m e sua soma nos retorna todos os fatores a, b, c, ... possíveis.
Para resolver o problema acima, vamos pensar de maneira recursiva numa função somas(m, soma) e aplicar em nosso exemplo.
Para calcular somas(4, 1) podemos fixar o primeiro valor e calcular todas as somas possíveis para os outros. No exemplo, a pode valer de 0 até m.
Vamos ver alguns exemplos:
somas(4, 1) = 0 + somas(4 - 1, 1 - 0)
+ 1 + somas(4 - 1, 1 - 1)
somas(5, 3) = 0 + somas(5 - 1, 3 - 0)
+ 1 + somas(5 - 1, 3 - 1)
+ 2 + somas(5 - 1, 3 - 2)
+ 3 + somas(5 - 1, 3 - 3)As condições de parada seriam quando soma = 0 ou m = 1.
def somas(m, soma):
if m < 0 or soma < 0: return []
if soma == 0: return [m*[0]]
if m == 1: return [[soma]]
return_somas = []
for i in range(soma+1):
for s in somas(m-1, soma-i):
return_somas.append([i] + s)
return return_somasVamos ver algumas somas de exemplo:
somas(4, 1) = [
[0, 0, 0, 1], # a = 0, b = 0, c = 0, d = 1
[0, 0, 1, 0], # a = 0, b = 0, c = 1, d = 0
[0, 1, 0, 0], # a = 0, b = 1, c = 0, d = 0
[1, 0, 0, 0] # a = 1, b = 0, c = 0, d = 0
]
somas(5, 2) = [
[0, 0, 0, 0, 2], [0, 0, 0, 1, 1], [0, 0, 0, 2, 0],
[0, 0, 1, 0, 1], [0, 0, 1, 1, 0], [0, 0, 2, 0, 0],
[0, 1, 0, 0, 1], [0, 1, 0, 1, 0], [0, 1, 1, 0, 0],
[0, 2, 0, 0, 0], [1, 0, 0, 0, 1], [1, 0, 0, 1, 0],
[1, 0, 1, 0, 0], [1, 1, 0, 0, 0], [2, 0, 0, 0, 0]
]Agora que sabemos como calcular todas as somas, precisamos transformar essas somas em permutações. Para o exemplo acima, as permutações seriam:
[0, 0, 0, 1] => [___ [1] ___ [0] ___ [1, 1] _0_] => [1, 0, 1, 1, 0]
[0, 0, 1, 0] => [___ [1] ___ [0] _0_ [1, 1] ___] => [1, 0, 0, 1, 1]
[0, 1, 0, 0] => [___ [1] _0_ [0] ___ [1, 1] ___] => [1, 0, 0, 1, 1]
[1, 0, 0, 0] => [_0_ [1] ___ [0] ___ [1, 1] ___] => [0, 1, 0, 1, 1]Perceba que tivemos duas permutações iguais, mas vamos ver mais para frente o motivo disso não importar.
Para realmente criar as permutações vamos primeiro criar uma lista de tamanho len(counts) * 2 - 1 apenas com [0] e depois substituir os elementos de índice ímpar pelos blocos de 1.
def create_perms(n, counts):
blocks = [[0]] * (len(counts) * 2 - 1)
blocks[0::2] = [[1]*c for c in counts] Com isso já temos nossos blocos, agora basta preenchermos com os valores calculados em somas().
Para isso, vamos criar uma lista com o tamanho total (porém dessa vez com todos os valores None), preencher os índices pares com os valores das somas() e os índices ímpares com os valores dos blocos:
def create_perms(n, counts):
blocks = [[0]] * (len(counts) * 2 - 1)
blocks[0::2] = [[1]*c for c in counts]
zeros = n - sum([len(b) for b in blocks])
perms = []
for abc_list in somas(len(blocks) + 1, zeros):
perm = [None] * (len(blocks) + len(abc_list))
perm[0::2] = [abc*[0] for abc in abc_list]
perm[1::2] = blocks
perms.append(perm)Por enquanto, nossas permutações são listas como as abaixo:
[[], [1], [], [0], [], [1, 1], [0]]
[[], [1], [], [0], [0], [1, 1], []]
[[], [1], [0], [0], [], [1, 1], []]
[[0], [1], [], [0], [], [1, 1], []]Queremos então remover as sub-listas vazias e transformar nossas listas de listas em apenas listas flat. Para isso vamos criar a função abaixo:
def flatten_perm(perm):
flat_perm = []
for item in perm:
if type(item) is list:
flat_perm += item
else:
flat_perm.append(item)
return flat_permAgora podemos chamá-la antes de adicionar a permutação à nossa lista de permutações:
def create_perms(n, counts):
blocks = [[0]] * (len(counts) * 2 - 1)
blocks[0::2] = [[1]*c for c in counts]
zeros = n - sum([len(b) for b in blocks])
perms = []
for abc_list in somas(len(blocks) + 1, zeros):
perm = [None] * (len(blocks) + len(abc_list))
perm[0::2] = [abc*[0] for abc in abc_list]
perm[1::2] = blocks
perms.append(flatten_perm(perm))
return permsPronto! Temos uma função que cria todas as permutações para uma dada linha ou coluna.
Filtros
Para facilitar, vamos criar uma maneira de representar todas as permutações em uma só lista que vamos chamar de filtro.
Olhando nossas permutações do exemplo podemos ver que alguns valores são os mesmos em todas elas, como o elemento de índice 3 que é sempre 1.
[1, 0, 1, 1, 0]
[1, 0, 0, 1, 1]
[1, 0, 0, 1, 1]
[0, 1, 0, 1, 1]Então queremos um filtro do tipo [None, None, None, 1, None] em que temos None para valores não definidos e1 ou 0 para os que já estão definidos como preenchidos ou não.
Criar o filtro é bem simples e vamos olhar para cada índice de todas as permutações.
- Se a soma é
0, todos os valores são0; - Se a soma é
n, todos os valores são1; e - Caso contrário, mantemos
None.
def create_line_filter(perms):
if len(perms) < 1: return None
n = len(perms[0])
filter_ = n*[None]
for i in range(n):
sum_ = 0
for perm in perms:
sum_ += perm[i]
if sum_ == len(perms):
filter_[i] = 1
elif sum_ == 0:
filter_[i] = 0
return filter_ Com os filtros, já sabemos quais valores estão determinados em nosso grid.
Preenchendo o tabuleiro
Para começar a realmente resolver o problema e preencher o grid, vamos começar com os seguintes valores por padrão:
def solve_grid(n, lines, cols, partial_grid=None):
grid = n*[n*[None]]
possible_lines = n*[[]]
filter_lines = n*[[]]
possible_cols = n*[[]]
filter_cols = n*[[]]Nossa solução será iterativa, sempre olhando as linhas e colunas sucessivamente pois uma vez que olhamos para linhas, temos novos filtros que podem restringir as permutações possíveis nas colunas; e vice-versa.
A primeira iteração apenas utiliza as funções que já criamos para popular as possíveis linhas, colunas e seus filtros:
def solve_grid(n, lines, cols, partial_grid=None):
grid = n*[n*[None]]
perm_lines = n*[[]]
filter_lines = n*[[]]
perm_cols = n*[[]]
filter_cols = n*[[]]
for i in range(n):
perm_lines[i] = create_perms(n, lines[i])
filter_lines[i] = create_line_filter(perm_lines[i])
perm_cols[i] = create_perms(n, cols[i])
filter_cols[i] = create_line_filter(perm_cols[i])Repare que
filter_linesefilter_colssão os filtros de todas as linhas/colunas.
Agora que temos os filtros, podemos atualizar nosso grid utilizando os valores do filtro que estão definidos:
def update_grid(grid, filter_):
return_grid = []
n = len(grid)
for i in range(n):
temp_line = []
for j in range(n):
if filter_[i][j] != None:
temp_line.append(filter_[i][j])
else:
temp_line.append(grid[i][j])
return_grid.append(temp_line)
return return_gridPara atualizar o grid basta chamar a função para as linhas e colunas:
grid = update_grid(grid, filter_lines)
grid = update_grid(grid, transpose_grid(filter_cols))Nesse momento, já temos uma matriz como abaixo em que alguns valores já estão definidos:
[None, None, 1, 1, None]
[1, 0, 1, 0, 1]
[None, None, 1, 1, 1]
[None, None, 0, 0, None]
[None, None, 1, 1, None]Antes de partir para as próximas iterações, precisamos de uma função que receba as permutações atuais de uma linha e um filtro, e consiga remover as permutações impossíveis.
Uma maneira bem simples é definir uma função interna que diz se uma única permutação é valida para um dado filtro.
Depois só retornamos todas as permutações que são válidas de acordo com a função interna:
def filter_perms(perms, filter_):
def _validate_perm_with_filter(perm, filter_):
for perm_item, filter_item in zip(perm, filter_):
if filter_item != None and perm_item != filter_item:
return False
return True
return [perm for perm in perms if _validate_perm_with_filter(perm, filter_)] Falta apenas uma função para que possamos criar nosso loop principal para as demais iterações.
Essa função determina se um grid é valido ou não, ou seja, se nosso problema já foi resolvido ou não.
Para isso basta checar se ainda existe algum None em nosso grid.
def is_done(grid):
for line in grid:
for item in line:
if item == None:
return False
return TrueAgora sim podemos criar nosso loop principal que irá executar as demais iterações.
Em cada uma, precisamos executar os seguintes passos:
- atualizar o
gridcom os filtros de linhas e colunas; - atualizar as permutações possíveis com o novo
grid; e - atualizar os filtros com as novas permutações (mais restritas).
Lembrando que precisamos realizar as operações para as linhas e para as colunas.
Para simplificar, realizamos as operações em grid para as linhas e na transposta de grid para as colunas.
def solve_grid(n, lines, cols, partial_grid=None):
grid = n*[n*[None]]
perm_lines = n*[[]]
filter_lines = n*[[]]
perm_cols = n*[[]]
filter_cols = n*[[]]
for i in range(n):
perm_lines[i] = create_perms(n, lines[i])
filter_lines[i] = create_line_filter(perm_lines[i])
perm_cols[i] = create_perms(n, cols[i])
filter_cols[i] = create_line_filter(perm_cols[i])
count = 0
while not is_done(grid):
print('----')
count += 1
grid = update_grid(grid, filter_lines)
grid = update_grid(grid, transpose_grid(filter_cols))
trasposed_grid = transpose_grid(grid)
for i in range(n):
perm_lines[i] = filter_perms(perm_lines[i], grid[i])
filter_lines[i] = create_line_filter(perm_lines[i])
perm_cols[i] = filter_perms(perm_cols[i], trasposed_grid[i])
filter_cols[i] = create_line_filter(perm_cols[i])
return countResultados e Desempenho
A princípio, com o código abaixo, nosso problema estaria resolvido, mas temos algumas ressalvas a fazer.
if __name__ == '__main__':
n = 5
grid = []
while not valid_grid(grid):
grid = create_grid(n)
lines = get_counts(grid)
cols = get_counts(transpose_grid(grid))
grid, count = solve_grid(n, lines, cols)
print_grid(grid)
print('Tabela convergiu em {} iterações!'.format(count))Quando o número de 1 no tabuleiro é muito baixo, temos valores de lines e cols que serviriam para mais de um tabuleiro, resultando em um loop infinito em nosso código.
Poderíamos contornar este problema aumentando a probabilidade de valores 1 em relação aos 0 em nosso grid.
def create_easy_grid(n, chances):
grid = []
for i in range(n):
line = []
for j in range(n):
rand = random.randint(0, chances)
num = 0 if rand == 0 else 1
line.append(num)
grid.append(line)
return gridConforme aumentamos a probabilidade, nosso desempenho melhora. Para isso realizamos um teste com 100 iterações para cada tamanho de tabuleiro, obtendo o seguinte resultado:
| chances | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Tamanho 5 | 79% | 92% | 97% | 99% |
| Tamanho 10 | 50% | 94% | 97% | 100% |
| Tamanho 15 | 23% | 94% | 99% | 100% |
| Tamanho 20 | 15% | 90% | 98% | 97% |
No jogo, o problema já nos dá valores de lines e cols de um tabuleiro criado previamente. Quando o tabuleiro é criado para ser resolvido e não aleatoriamente, a chance da solução convergir e termos apenas um tabuleiro possível aumenta consideravelmente.
Testes
Agora que fizemos as considerações necessárias quanto a tabuleiros aleatórios ou de tamanho muito grande, vamos realizar alguns testes com tabuleiros reais do próprio jogo.
Para um tabuleiro de 10×10:
lines = [ [6], [3, 1], [1, 2], [2, 3], [6], [4], [5], [2, 4], [2, 4, 1], [3, 6] ]
cols = [ [1], [1, 3, 3], [2, 7], [2, 3], [2, 7], [1, 8], [5, 4], [3], [1], [2] ]
n = len(lines)
grid, count = solve_grid(n, lines, cols)
print_grid(grid)
print('Tabela convergiu em {} iterações!'.format(count))[0, 1, 1, 1, 1, 1, 1, 0, 0, 0]
[0, 0, 1, 1, 1, 0, 1, 0, 0, 0]
[0, 1, 0, 0, 0, 1, 1, 0, 0, 0]
[0, 1, 1, 0, 1, 1, 1, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 1, 0, 0, 0]
[0, 1, 1, 0, 1, 1, 1, 1, 0, 0]
[0, 1, 1, 0, 1, 1, 1, 1, 0, 1]
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1]
Tabela convergiu em 3 iterações!Para um tabuleiro de 15×15:
lines = [ [7], [9], [2, 4, 2], [2, 2], [2, 1, 1, 2], [3, 2], [2, 2], [3, 3, 1], [9, 1], [9, 1], [11, 2], [15], [14], [2, 3, 2], [1, 1, 1, 1, 1, 1, 1] ]
cols = [ [4], [6, 4], [12, 1], [2, 1, 6], [2, 5, 1], [3, 1, 6], [3, 7], [3, 6], [3, 1, 5, 1], [2, 6], [12, 1], [6, 4], [4], [3], [5] ]
n = len(lines)
grid, count = solve_grid(n, lines, cols)
print_grid(grid)
print('Tabela convergiu em {} iterações!'.format(count))[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0]
[0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0]
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0]
[0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0]
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
[1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0]
Tabela convergiu em 5 iterações!Para um tabuleiro de 20×20:
lines = [ [5], [4], [3, 3], [7, 2], [8, 2], [2, 3, 5], [10], [9, 5], [11, 3], [3, 3, 3, 3], [2, 5, 3, 2], [2, 2, 5, 1], [1, 2, 2, 3], [2, 3, 3], [3, 2, 2], [2, 2, 2], [2, 1], [3], [3], [3] ]
cols = [ [1], [3], [2, 3], [3, 5], [3, 3, 3], [1, 3, 2, 6], [1, 2, 2, 8], [2, 3, 2, 5], [2, 8], [3, 6, 1], [4, 5, 3], [7, 5], [5, 3], [2, 4], [3, 5, 2], [3, 6], [3, 3], [4], [5], [2] ]
n = len(lines)
grid, count = solve_grid(n, lines, cols)
print_grid(grid)
print('Tabela convergiu em {} iterações!'.format(count))[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0]
[0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0]
[0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1]
[0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1]
[0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Tabela convergiu em 11 iterações!Confira o exemplo 20×20 no aplicativo enquanto eu apenas preencho os valores acima:
Conclusão
Esse jogo é um bom exemplo de como um programa pode parecer simples mas ter vários detalhes a serem considerados em sua implementação.
A abordagem de encontrar todas as permutações possíveis talvez seja a mais imediata para qualquer um tentando resolver esse problema.
Vimos que para um tabuleiro totalmente aleatório as chances de resolver o problema podem ser bem baixas, mas ao mesmo tempo em problemas que foram criado para serem resolvidos, o algoritmo performa muito bem.
Resolver esse problema foi bem mais pesado matematicamente do que parecia, mas um bom programador deve ser capaz de resolver qualquer tipo de problema.
No final das contas, utilizar um framework pronto pode ser bem mais simples e a capacidade de resolver problemas complexos será o seu diferencial.
Código
O código completo deste artigo está disponível no github
nonogram (this link opens in a new window) by umcodigo (this link opens in a new window)
Python project to solve nonogram game
Referências
- Site oficial do Nonogram.
- Artigo da Wikipedia sobre Matriz transposta.
