Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
recursion solution in Clear category for Nonogram Row by David_Jones
def possible_solutions(row_string, clue_numbers):
n = len(row_string)
if not clue_numbers:
return [] if 'O' in row_string else ['X'*n]
clue_number = clue_numbers.pop()
if clue_number == 0:
return possible_solutions(row_string, clue_numbers)
solutions = []
for i in range(n - clue_number + 1):
if (
(i == 0 or row_string[i-1] != 'O')
and all(row_string[j] != 'X' for j in range(i, i + clue_number))
and all(row_string[j] != 'O' for j in range(i + clue_number, n))
):
new_row_string = (row_string[:i-1] + 'X') if i else ''
for solution in possible_solutions(new_row_string, clue_numbers[:]):
solutions.append(
solution + 'O'*clue_number + 'X'*(n-clue_number-i)
)
return solutions
def nonogram_row(row_string, clue_numbers):
answer = ''
for possible_symbols in zip(*possible_solutions(row_string, clue_numbers)):
if 'X' in possible_symbols:
answer += '?' if 'O' in possible_symbols else 'X'
else:
answer += 'O'
return answer if answer else None
June 13, 2019