Once you complete this kata, there is a [15x15 Version](http://www.codewars.com/kata/15x15-nonogram-solver) that you can try.
And once you complete that, you can do the [Multisize Version](https://www.codewars.com/kata/5a5519858803853691000069) which goes up to 50x50.

# Description

For this kata, you will be making a Nonogram solver. :)

If you don't know what Nonograms are, you can [look at some instructions](https://www.puzzle-nonograms.com/faq.php) and also [try out some Nonograms here.](https://www.puzzle-nonograms.com/)

For this kata, you will only have to solve 5x5 Nonograms. :)

# Instructions

You need to complete the Nonogram class and the solve method:
```python
class Nonogram:

    def __init__(self, clues):
        pass

    def solve(self):
        pass
```

You will be given the clues and you should return the solved puzzle. All the puzzles will be solveable so you will not need to worry about that.

```if:python
The clues will be a tuple of the horizontal clues, then the vertical clues, which will contain the individual clues. For example, for the Nonogram:
```

```if:java
The clues will be a three dimensional array of the horizontal clues, then the vertical clues, which will contain the individual clues. For example, for the Nonogram:
```

```
    |   |   | 1 |   |   |
    | 1 |   | 1 |   |   |
    | 1 | 4 | 1 | 3 | 1 |
-------------------------
  1 |   |   |   |   |   |
-------------------------
  2 |   |   |   |   |   |
-------------------------
  3 |   |   |   |   |   |
-------------------------
2 1 |   |   |   |   |   |
-------------------------
  4 |   |   |   |   |   |
-------------------------
```
The clues are on the top and the left of the puzzle, so in this case:
```if:python
The horizontal clues are: `((1, 1), (4,), (1, 1, 1), (3,), (1,))`, and the vertical clues are: `((1,), (2,), (3,), (2, 1), (4,))`. The horizontal clues are given from left to right. If there is more than one clue for the same column, the upper clue is given first. The vertical clues are given from top to bottom. If there is more than one clue for the same row, the leftmost clue is given first.

Therefore, the clue given to the `__init__` method would be `(((1, 1), (4,), (1, 1, 1), (3,), (1,)), ((1,), (2,), (3,), (2, 1), (4,)))`. You are given the horizontal clues first then the vertical clues second.

```

```if:java
The horizontal clues are: `{{1, 1}, {4}, {1, 1, 1}, {3}, {1}}`, and the vertical clues are: `{{1}, {2}, {3}, {2, 1}, {4}}`. The horizontal clues are given from left to right. If there is more than one clue for the same column, the upper clue is given first. The vertical clues are given from top to bottom. If there is more than one clue for the same row, the leftmost clue is given first.

Therefore, the clue given to the `solve` method would be `{{{1, 1}, {4}, {1, 1, 1}, {3}, {1}},
                    {{1}, {2}, {3}, {2, 1}, {4}}}`. You are given the horizontal clues first then the vertical clues second.

```

```if:python
You should return a tuple of the rows as your answer. In this case, the solved Nonogram looks like:

```
```if:java
You should return a two-dimensional array as your answer. In this case, the solved Nonogram looks like:

```

```
    |   |   | 1 |   |   |
    | 1 |   | 1 |   |   |
    | 1 | 4 | 1 | 3 | 1 |
-------------------------
  1 |   |   | # |   |   |
-------------------------
  2 | # | # |   |   |   |
-------------------------
  3 |   | # | # | # |   |
-------------------------
2 1 | # | # |   | # |   |
-------------------------
  4 |   | # | # | # | # |
-------------------------
```

```if:python
In the tuple, you should use 0 for a unfilled square and 1 for a filled square. Therefore, in this case, you should return:
~~~
((0, 0, 1, 0, 0),
 (1, 1, 0, 0, 0),
 (0, 1, 1, 1, 0),
 (1, 1, 0, 1, 0),
 (0, 1, 1, 1, 1))
~~~

```

```if:java
In the two-dimensional array, you should use 0 for a unfilled square and 1 for a filled square. Therefore, in this case, you should return:
~~~
{{0, 0, 1, 0, 0},
 {1, 1, 0, 0, 0},
 {0, 1, 1, 1, 0},
 {1, 1, 0, 1, 0},
 {0, 1, 1, 1, 1}}
~~~

```
Good Luck!!

If there is anything that is unclear or confusing, just let me know :)

Source: codewars | Difficulty: MEDIUM
Tags: Game theory

Starter code: def __init__(self, clues):
	

Solutions:
import itertools

class Nonogram:
	poss = {(1, 1, 1): set([(1, 0, 1, 0, 1)]), (1, 1): set([(0, 0, 1, 0, 1), (0, 1, 0, 1, 0), (1, 0, 1, 0, 0), (0, 1, 0, 0, 1), (1, 0, 0, 1, 0), (1, 0, 0, 0, 1)]), (1, 2): set([(1, 0, 1, 1, 0), (1, 0, 0, 1, 1), (0, 1, 0, 1, 1)]), (1, 3): set([(1, 0, 1, 1, 1)]), (2, 1): set([(1, 1, 0, 1, 0), (1, 1, 0, 0, 1), (0, 1, 1, 0, 1)]), (2, 2): set([(1, 1, 0, 1, 1)]), (3, 1): set([(1, 1, 1, 0, 1)]), (1,): set([(0, 0, 0, 0, 1), (0, 0, 0, 1, 0), (0, 0, 1, 0, 0), (0, 1, 0, 0, 0), (1, 0, 0, 0, 0)]), (2,): set([(0, 0, 0, 1, 1), (0, 0, 1, 1, 0), (0, 1, 1, 0, 0), (1, 1, 0, 0, 0)]), (3,): set([(0, 0, 1, 1, 1), (0, 1, 1, 1, 0), (1, 1, 1, 0, 0)]), (4,): set([(0, 1, 1, 1, 1), (1, 1, 1, 1, 0)]), (5,): set([(1, 1, 1, 1, 1)])}

	def __init__(self, clues):
		(self.h, self.w) = (tuple((Nonogram.poss[clue] for clue in side)) for side in clues)

	def solve(self):
		for r in itertools.product(*self.w):
			if all((c in self.h[i] for (i, c) in enumerate(zip(*r)))):
				return r


from copy import deepcopy

class Nonogram:
	POS = {(2, 2): ((1, 1, 0, 1, 1),), (5,): ((1, 1, 1, 1, 1),), (1, 1, 1): ((1, 0, 1, 0, 1),), (1, 3): ((1, 0, 1, 1, 1),), (3, 1): ((1, 1, 1, 0, 1),), (4,): ((1, 1, 1, 1, 0), (0, 1, 1, 1, 1)), (1, 2): ((1, 0, 0, 1, 1), (1, 0, 1, 1, 0), (0, 1, 0, 1, 1)), (2, 1): ((1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (0, 1, 1, 0, 1)), (3,): ((1, 1, 1, 0, 0), (0, 1, 1, 1, 0), (0, 0, 1, 1, 1)), (2,): ((1, 1, 0, 0, 0), (0, 1, 1, 0, 0), (0, 0, 1, 1, 0), (0, 0, 0, 1, 1)), (1,): ((1, 0, 0, 0, 0), (0, 1, 0, 0, 0), (0, 0, 1, 0, 0), (0, 0, 0, 1, 0), (0, 0, 0, 0, 1)), (1, 1): ((1, 0, 1, 0, 0), (1, 0, 0, 1, 0), (1, 0, 0, 0, 1), (0, 1, 0, 1, 0), (0, 1, 0, 0, 1), (0, 0, 1, 0, 1))}

	def __init__(self, clues):
		self.clues = {'V': clues[0], 'H': clues[1]}

	def solve(self):
		grid = {(d, z): list(self.POS[self.clues[d][z]]) for d in 'VH' for z in range(5)}
		changed = True
		while changed:
			changed = False
			for x in range(5):
				for y in range(5):
					(tupH, iH, tupV, iV) = (('H', x), y, ('V', y), x)
					if len(grid[tupH]) == 1 and len(grid[tupV]) == 1:
						continue
					vH = {v[iH] for v in grid[tupH]}
					vV = {v[iV] for v in grid[tupV]}
					target = vH & vV
					if len(vH) == 2 and len(target) == 1:
						changed = True
						grid[tupH] = [t for t in grid[tupH] if t[iH] in target]
					if len(vV) == 2 and len(target) == 1:
						changed = True
						grid[tupV] = [t for t in grid[tupV] if t[iV] in target]
		return tuple((grid['H', n][0] for n in range(5)))


import re
import numpy as np

class Nonogram:

	def __init__(self, clues):
		self.clues = clues
		(self.possible_rows, self.possible_cols) = [[self.possible_cells(len(clues[i]), c) for c in clues[1 - i]] for i in range(2)]

	def possible_cells(self, n, clues):
		if clues == () or clues == (0,):
			return ['0' * n]
		min_width = sum(clues) + len(clues) - 1
		assert min_width <= n
		if len(clues) == 1:
			return [('0' * i + '1' * clues[0]).ljust(n, '0') for i in range(n - clues[0] + 1)]
		res = []
		for i in range(0, n - min_width + 1):
			start = '0' * i + '1' * clues[0] + '0'
			res += [start + p for p in self.possible_cells(n - len(start), clues[1:])]
		return res

	def solve(self):
		(w, h) = (len(self.possible_cols), len(self.possible_rows))
		(old_grid, grid) = (None, '\n'.join(['.' * w] * h))
		while old_grid != grid and grid.find('.') != -1:
			old_grid = grid
			grid = ''.join((self.update_cells(row, p) for (row, p) in zip(grid.split('\n'), self.possible_rows)))
			grid = ''.join((self.update_cells(col, p) for (col, p) in zip((grid[i::w] for i in range(w)), self.possible_cols)))
			grid = '\n'.join((grid[row::h] for row in range(h)))
		return tuple((tuple((-1 if c == '.' else int(c) for c in r)) for r in grid.split('\n')))

	@staticmethod
	def update_cells(cells, possibilities):
		if cells.find('.') == -1:
			return cells
		not_matches = [i for (i, answer) in enumerate(possibilities) if not re.match(cells, answer)]
		for i in not_matches[::-1]:
			possibilities.pop(i)
		assert len(possibilities) != 0
		if len(possibilities) == 1:
			return possibilities[0]
		(n, stack) = (len(cells), ''.join(possibilities))
		vote = (set(stack[i::n]) for i in range(0, n))
		return ''.join((s.pop() if len(s) == 1 else '.' for s in vote))


from itertools import groupby, product

class Nonogram:

	def __init__(self, clues):
		self.clues = clues

	def solve(self):
		for p in product(*[[p for p in product(range(2), repeat=5) if sum(p) == sum(t) and tuple((len(list(g)) for (k, g) in groupby(p) if k)) == t] for t in self.clues[1]]):
			if all((tuple((len(list(g)) for (k, g) in groupby(p) if k)) == t for (p, t) in zip([v for v in zip(*p)], self.clues[0]))):
				return p


from itertools import product

class Nonogram:
	POS = {(2, 2): ((1, 1, 0, 1, 1),), (5,): ((1, 1, 1, 1, 1),), (1, 1, 1): ((1, 0, 1, 0, 1),), (1, 3): ((1, 0, 1, 1, 1),), (3, 1): ((1, 1, 1, 0, 1),), (4,): ((1, 1, 1, 1, 0), (0, 1, 1, 1, 1)), (1, 2): ((1, 0, 0, 1, 1), (1, 0, 1, 1, 0), (0, 1, 0, 1, 1)), (2, 1): ((1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (0, 1, 1, 0, 1)), (3,): ((1, 1, 1, 0, 0), (0, 1, 1, 1, 0), (0, 0, 1, 1, 1)), (2,): ((1, 1, 0, 0, 0), (0, 1, 1, 0, 0), (0, 0, 1, 1, 0), (0, 0, 0, 1, 1)), (1,): ((1, 0, 0, 0, 0), (0, 1, 0, 0, 0), (0, 0, 1, 0, 0), (0, 0, 0, 1, 0), (0, 0, 0, 0, 1)), (1, 1): ((1, 0, 1, 0, 0), (1, 0, 0, 1, 0), (1, 0, 0, 0, 1), (0, 1, 0, 1, 0), (0, 1, 0, 0, 1), (0, 0, 1, 0, 1))}

	def __init__(self, clues):
		self.clues = clues

	def solve(self):
		for p in product(*(self.POS[c] for c in self.clues[0])):
			board = list(zip(*p))
			for z in range(5):
				if board[z] not in self.POS[self.clues[1][z]]:
					break
			else:
				return tuple((tuple(l) for l in board))


from itertools import permutations

def count_blacks(list):
	count = 0
	chain = False
	blacks = []
	for i in list:
		if i == 1:
			if chain == False:
				chain = True
				count += 1
			else:
				count += 1
		if i != 1:
			if chain == False:
				continue
			else:
				blacks.append(count)
				count = 0
				chain = False
	if chain == True:
		blacks.append(count)
	return tuple(blacks)

class Row:

	def __init__(self, nrow, length, blacks):
		self.nrow = nrow
		self.length = length
		self.blacks = blacks
		self.combs = []
		if len(self.blacks) == 1 and self.blacks[0] > 0:
			for i in range(self.length - self.blacks[0] + 1):
				self.combs.append([0 for i in range(i)] + [1 for j in range(self.blacks[0])] + [0 for k in range(self.length - (i + self.blacks[0]))])
		elif len(self.blacks) > 1:
			self.totalblacks = 0
			for i in self.blacks:
				self.totalblacks += i
			self.blanks = self.length - self.totalblacks
			self.items = []
			for i in range(self.blanks):
				self.items.append(0)
			for i in range(self.totalblacks):
				self.items.append(1)
			for p in permutations(self.items):
				if p not in self.combs and count_blacks(p) == self.blacks:
					self.combs.append(p)

	def __str__(self):
		return str(self.nrow) + ',' + str(self.length) + ',' + str(self.blacks)

class Col:

	def __init__(self, ncol, length, blacks):
		self.ncol = ncol
		self.length = length
		self.blacks = blacks
		self.combs = []
		if len(self.blacks) == 1 and self.blacks[0] > 0:
			for i in range(self.length - self.blacks[0] + 1):
				self.combs.append([0 for i in range(i)] + [1 for j in range(self.blacks[0])] + [0 for k in range(self.length - (i + self.blacks[0]))])
		elif len(self.blacks) > 1:
			self.totalblacks = 0
			for i in self.blacks:
				self.totalblacks += i
			self.blanks = self.length - self.totalblacks
			self.items = []
			for i in range(self.blanks):
				self.items.append(0)
			for i in range(self.totalblacks):
				self.items.append(1)
			for p in permutations(self.items):
				if p not in self.combs and count_blacks(p) == self.blacks:
					self.combs.append(p)

	def __str__(self):
		return str(self.ncol) + ',' + str(self.length) + ',' + str(self.blacks)

class Nonogram:

	def __init__(self, clues):
		self.nrows = len(clues[1])
		self.ncols = len(clues[0])
		self.board = [[0 for i in range(self.ncols)] for j in range(self.nrows)]
		self.rclues = clues[1]
		self.cclues = clues[0]
		self.rows = []
		self.cols = []
		for i in range(self.nrows):
			self.rows.append(Row(i, self.ncols, self.rclues[i]))
		for j in range(self.ncols):
			self.cols.append(Col(j, self.nrows, self.cclues[j]))

	def solve(self):
		self.solved = False
		while self.solved == False:
			for row in self.rows:
				if len(row.combs) > 0:
					for c in range(row.length):
						self.check = []
						for r in row.combs:
							self.check.append(r[c] == 1)
						if all(self.check):
							self.board[row.nrow][c] = 1
							self.crosscheck = []
							for i in self.cols[c].combs:
								if i[row.nrow] != 1:
									self.crosscheck.append(i)
							for d in self.crosscheck:
								self.cols[c].combs.remove(d)
			for row in self.rows:
				if len(row.combs) > 0:
					for c in range(row.length):
						self.check = []
						for r in row.combs:
							self.check.append(r[c] == 0)
						if all(self.check):
							self.crosscheck = []
							for i in self.cols[c].combs:
								if i[row.nrow] != 0:
									self.crosscheck.append(i)
							for d in self.crosscheck:
								self.cols[c].combs.remove(d)
			for col in self.cols:
				if len(col.combs) > 0:
					for c in range(col.length):
						self.check = []
						for r in col.combs:
							self.check.append(r[c] == 1)
						if all(self.check):
							self.board[c][col.ncol] = 1
							self.crosscheck = []
							for i in self.rows[c].combs:
								if i[col.ncol] != 1:
									self.crosscheck.append(i)
							for d in self.crosscheck:
								self.rows[c].combs.remove(d)
			for col in self.cols:
				if len(col.combs) > 0:
					for c in range(col.length):
						self.check = []
						for r in col.combs:
							self.check.append(r[c] == 0)
						if all(self.check):
							self.crosscheck = []
							for i in self.rows[c].combs:
								if i[col.ncol] != 0:
									self.crosscheck.append(i)
							for d in self.crosscheck:
								self.rows[c].combs.remove(d)
			self.checksolutions = []
			for r in range(self.nrows):
				self.checksolutions.append(count_blacks(self.board[r]) == self.rclues[r])
			for c in range(self.ncols):
				self.transposedboard = [[self.board[j][i] for j in range(self.ncols)] for i in range(self.nrows)]
				self.checksolutions.append(count_blacks(self.transposedboard[c]) == self.cclues[c])
			if all(self.checksolutions):
				self.solved = True
				self.solution = []
		for r in self.board:
			self.solution.append(tuple(r))
		return tuple(self.solution)


from functools import reduce
from typing import Tuple, List, Optional, Sequence

class Box:

	def __init__(self, x: int, y: int, value: Optional[int]):
		self.value = value
		self.x = x
		self.y = y

	def to_int(self):
		return self.value if self.value else 0

	def mapper(self) -> str:
		if self.value is None:
			return 'S'
		elif self.value == 0:
			return '#'
		else:
			return '█'

class Clue:

	def __init__(self, index: int, clue: Sequence[int], elements: List[Box]):
		self.index: int = index
		self.clue: Sequence[int] = clue
		self.elements: List[Box] = elements

	@staticmethod
	def match_constrains(initial: Sequence[int], constrains: List[Box]):

		def tmp(element: int, constrain: Box):
			if constrain.value is None:
				return True
			return constrain.value == element
		ddd = all((tmp(data, req) for (data, req) in zip(initial, constrains)))
		return ddd

	def generate_combinations(self, initial: Sequence[int]=(), to_be_marked: int=-1) -> List[Sequence[int]]:
		if to_be_marked == -1:
			to_be_marked = sum(self.clue)
		if not Clue.match_constrains(initial, self.elements):
			return []
		elif len(initial) > len(self.elements):
			return []
		elif len(initial) == len(self.elements):
			arr = [it for it in initial if it == 1]
			if to_be_marked != len(arr):
				return []
			return [initial]
		elif len(self.clue) == 0:
			ret: List[int] = [i for i in initial]
			for i in range(0, len(self.elements) - len(initial)):
				ret.append(0)
			if Clue.match_constrains(ret, self.elements):
				return [ret]
			return []
		new_initial: List[int] = [i for i in initial]
		new_initial.append(0)
		zero: List[Sequence[int]] = self.generate_combinations(new_initial, to_be_marked)
		if self.clue:
			new_clue: Clue = Clue(self.index, self.clue[1:], self.elements)
			tab: List[int] = [i for i in initial]
			tab.extend([1 for __ in range(0, self.clue[0])])
			if len(tab) < len(self.elements):
				tab.append(0)
			one = new_clue.generate_combinations(tab, to_be_marked)
			zero.extend(one)
		return zero

	@staticmethod
	def get_marked_size(clue: Sequence[int]):
		return reduce(lambda x, y: x + y, clue, 0)

	@staticmethod
	def get_minimal_size(clue: Sequence[int]):
		return len(clue) + Clue.get_marked_size(clue) - 1

	def contains_all(self, stripe):
		return len([1 for element in stripe if element == 1]) == self.get_marked_size(self.clue)

	@staticmethod
	def get_commons(possible_solutions):

		def check_all_the_same(lst):
			if lst.count(lst[0]) == len(lst):
				return lst[0]
			return None
		return [check_all_the_same(lst) for lst in zip(*possible_solutions)]

def get_v_stripe(board, index):
	return [element[index] for element in board]

def get_h_stripe(board, index):
	return board[index]

class Nonogram:

	def __init__(self, clues: Tuple[Sequence[Sequence[int]], Sequence[Sequence[int]]]):
		(h_clues, v_clues) = clues
		self.width: int = len(h_clues)
		self.height: int = len(v_clues)
		self.board: List[List[Box]] = [[Box(x, y, None) for y in range(0, self.width)] for x in range(0, self.height)]
		self.v_clues = [Clue(index, clue, [line[index] for line in self.board]) for (index, clue) in enumerate(clues[0])]
		self.h_clues = [Clue(index, clue, self.board[index]) for (index, clue) in enumerate(clues[1])]

	def solve(self) -> List[List[int]]:
		missing = [(self.width - clue.get_minimal_size(clue.clue), clue) for clue in self.v_clues]
		missing.sort(key=lambda x: x[0])
		for i in range(0, 10):
			self.print_board()
			print(('loop ', i))
			for clue in self.v_clues:
				comb = clue.generate_combinations()
				print('v: %s : %s ' % (clue.clue, Clue.get_commons(comb)))
				for (index, value) in enumerate(Clue.get_commons(comb)):
					if value is not None:
						self.board[index][clue.index].value = value
			for clue in self.h_clues:
				comb = clue.generate_combinations()
				print('h: %s : %s ' % (clue.clue, Clue.get_commons(comb)))
				for (index, value) in enumerate(Clue.get_commons(comb)):
					if value is not None:
						self.board[clue.index][index].value = value
		self.print_board()
		return tuple([tuple([box.to_int() for box in line]) for line in self.board])

	def print_board(self) -> None:
		max_size: int = max((len(clue.clue) for clue in self.v_clues))
		max_width: int = max((len(clue.clue) for clue in self.h_clues))
		prefix: str = ' ' * (2 * max_width + 3)

		def expand_empty_header(clues: Sequence[int], size: int, ending: str) -> List[str]:
			empty_header = [' ' for __ in range(0, size)]
			empty_header.extend(list(map(str, clues)))
			empty_header.append(ending)
			return empty_header
		headers = [expand_empty_header(clue.clue, max_size, '-')[-max_size - 1:] for clue in self.v_clues]
		for index in range(0, max_size):
			print(prefix + ' '.join([str(e[index]) for e in headers]))
		borders = [expand_empty_header(clue.clue, max_width, '|')[-max_size - 1:] for clue in self.h_clues]
		for (border, line) in zip(borders, self.board):
			d = ' '.join([str(d) for d in border]) + ' '.join([d.mapper() for d in line])
			print(d)

def solve(clues, width: int, height: int) -> List[List[int]]:
	return Nonogram(clues).solve()


from itertools import permutations

class Nonogram:

	def __init__(self, clues):
		self.cols = clues[0]
		self.rows = clues[1]
		self.dim = len(self.cols)
		self.field = [[' ' for j in range(self.dim)] for i in range(self.dim)]
		self.rows_p = [None] * self.dim
		self.cols_p = [None] * self.dim

	def __str__(self):
		max_hint_length = (self.dim + 1) // 2
		rows = []
		for i in range(max_hint_length):
			row = [' ' if len(self.cols[d]) + i < max_hint_length else str(self.cols[d][len(self.cols[d]) - max_hint_length + i]) for d in range(self.dim)]
			rows.append(' ' * max_hint_length + '|' + ''.join(row))
		rows.append('-' * max_hint_length + '+' + '-' * self.dim)
		for i in range(self.dim):
			row = [' ' if len(self.rows[i]) + j < max_hint_length else str(self.rows[i][len(self.rows[i]) - max_hint_length + j]) for j in range(max_hint_length)]
			row_field = [str(self.field[i][d]) for d in range(self.dim)]
			rows.append(''.join(row) + '|' + ''.join(row_field))
		return '\n'.join(rows)

	def possibilities(self, clues, sure=None):
		poss = [''.join(pp) for pp in set(permutations('0' * len(clues) + '.' * (self.dim - sum(clues)))) if '00' not in ''.join(pp)]
		for x in range(len(poss)):
			for num in clues:
				poss[x] = poss[x].replace('0', 'X' * num, 1)
		if sure is not None:
			poss = list([p for p in poss if all([sure[d] == ' ' or sure[d] == p[d] for d in range(self.dim)])])
		return poss

	def sure(self, poss):
		return ''.join(['X' if all([p[d] == 'X' for p in poss]) else '.' if all([p[d] == '.' for p in poss]) else ' ' for d in range(self.dim)])

	def update_rows_p(self, i, j, s):
		if self.rows_p[i] is not None:
			self.rows_p[i] = list([poss for poss in self.rows_p[i] if poss[j] == s])
			sure = self.sure(self.rows_p[i])
			if not sure.isspace():
				self.update_field(sure, i=i)

	def update_cols_p(self, i, j, s):
		if self.cols_p[j] is not None:
			self.cols_p[j] = list([poss for poss in self.cols_p[j] if poss[i] == s])
			sure = self.sure(self.cols_p[j])
			if not sure.isspace():
				self.update_field(sure, j=j)

	def update_field(self, sure, i=None, j=None):
		if i is not None:
			for j in range(self.dim):
				if sure[j] in ('X', '.') and self.field[i][j] == ' ':
					self.field[i][j] = sure[j]
					self.update_cols_p(i, j, sure[j])
		elif j is not None:
			for i in range(self.dim):
				if sure[i] in ('X', '.') and self.field[i][j] == ' ':
					self.field[i][j] = sure[i]
					self.update_rows_p(i, j, sure[i])

	def solve(self):
		for i in range(self.dim):
			poss = self.possibilities(clues=self.rows[i])
			self.rows_p[i] = poss
			sure = self.sure(poss=poss)
			if not sure.isspace():
				self.update_field(sure, i=i)
		for j in range(self.dim):
			poss = self.possibilities(clues=self.cols[j], sure=[self.field[i][j] for i in range(self.dim)])
			self.cols_p[j] = poss
			sure = self.sure(poss=poss)
			if not sure.isspace():
				self.update_field(sure, j=j)
		return tuple((tuple((0 if c == '.' else 1 for c in r)) for r in self.field))


class Nonogram:

	def __init__(self, clues):
		(self.size, self.colclues, self.rowclues) = (5, clues[0], clues[1])
		self.answer = [[None] * self.size for _ in range(self.size)]

	def possibilities(self):
		from itertools import combinations
		colposs = []
		for clue in self.colclues:
			a = self.size - sum(clue) + 1
			b = len(clue)
			c = list(combinations(range(a), b))
			d = []
			for block in clue[:-1]:
				d.append([1] * block + [0])
			d.append([1] * clue[-1])
			colcombs = []
			for thing in c:
				combblock = []
				e = d[:]
				for i in range(a):
					if i in thing:
						combblock.append(e.pop(0))
					else:
						combblock.append([0])
				comb = tuple([j for sublist in combblock for j in sublist])
				colcombs.append(comb)
			colposs.append(colcombs)
		rowposs = []
		for clue in self.rowclues:
			a = self.size - sum(clue) + 1
			b = len(clue)
			c = list(combinations(range(a), b))
			d = []
			for block in clue[:-1]:
				d.append([1] * block + [0])
			d.append([1] * clue[-1])
			rowcombs = []
			for thing in c:
				combblock = []
				e = d[:]
				for i in range(a):
					if i in thing:
						combblock.append(e.pop(0))
					else:
						combblock.append([0])
				comb = tuple([j for sublist in combblock for j in sublist])
				rowcombs.append(comb)
			rowposs.append(rowcombs)
		return [colposs, rowposs]

	def colfill(self):
		for i in range(self.size):
			for j in range(self.size):
				allOne = True
				allZero = True
				for poss in self.colposs[i]:
					if poss[j] == 1:
						allZero = False
					else:
						allOne = False
				if allOne:
					self.answer[j][i] = 1
				elif allZero:
					self.answer[j][i] = 0

	def rowfill(self):
		for i in range(self.size):
			for j in range(self.size):
				allOne = True
				allZero = True
				for poss in self.rowposs[i]:
					if poss[j] == 1:
						allZero = False
					else:
						allOne = False
				if allOne:
					self.answer[i][j] = 1
				elif allZero:
					self.answer[i][j] = 0

	def colelim(self):
		for i in range(self.size):
			for poss in reversed(self.colposs[i]):
				for j in range(self.size):
					if not self.answer[j][i] is None and self.answer[j][i] != poss[j]:
						self.colposs[i].remove(poss)
						break

	def rowelim(self):
		for i in range(self.size):
			for poss in reversed(self.rowposs[i]):
				for j in range(self.size):
					if not self.answer[i][j] is None and self.answer[i][j] != poss[j]:
						self.rowposs[i].remove(poss)
						break

	def isSolved(self):
		for i in range(self.size):
			for j in range(self.size):
				if self.answer[i][j] is None:
					return False
		return True

	def solve(self):
		from itertools import chain
		poss = self.possibilities()
		(self.colposs, self.rowposs) = (poss[0], poss[1])
		while not self.isSolved():
			self.colfill()
			self.rowelim()
			self.rowfill()
			self.colelim()
		return tuple([tuple(row) for row in self.answer])


class Nonogram:

	def __init__(self, clues):
		(self.size, self.colclues, self.rowclues) = (5, clues[0], clues[1])
		self.answer = [[None] * self.size for _ in range(self.size)]

	def possibilities(self):
		from itertools import product

		def check(clue, comb):
			count = []
			for i in range(self.size):
				if comb[i] == 1:
					if i == 0 or comb[i - 1] == 0:
						count.append(1)
					else:
						count[-1] += 1
			return tuple(count) == clue
		colposs = [[comb for comb in product([1, 0], repeat=self.size) if check(clue, comb)] for clue in self.colclues]
		rowposs = [[comb for comb in product([1, 0], repeat=self.size) if check(clue, comb)] for clue in self.rowclues]
		return [colposs, rowposs]

	def colfill(self):
		for i in range(self.size):
			for j in range(self.size):
				allOne = True
				allZero = True
				for poss in self.colposs[i]:
					if poss[j] == 1:
						allZero = False
					else:
						allOne = False
				if allOne:
					self.answer[j][i] = 1
				elif allZero:
					self.answer[j][i] = 0

	def rowfill(self):
		for i in range(self.size):
			for j in range(self.size):
				allOne = True
				allZero = True
				for poss in self.rowposs[i]:
					if poss[j] == 1:
						allZero = False
					else:
						allOne = False
				if allOne:
					self.answer[i][j] = 1
				elif allZero:
					self.answer[i][j] = 0

	def colelim(self):
		for i in range(self.size):
			for poss in reversed(self.colposs[i]):
				for j in range(self.size):
					if not self.answer[j][i] is None and self.answer[j][i] != poss[j]:
						self.colposs[i].remove(poss)
						break

	def rowelim(self):
		for i in range(self.size):
			for poss in reversed(self.rowposs[i]):
				for j in range(self.size):
					if not self.answer[i][j] is None and self.answer[i][j] != poss[j]:
						self.rowposs[i].remove(poss)
						break

	def isSolved(self):
		for i in range(self.size):
			for j in range(self.size):
				if self.answer[i][j] is None:
					return False
		return True

	def solve(self):
		from itertools import chain
		poss = self.possibilities()
		(self.colposs, self.rowposs) = (poss[0], poss[1])
		while not self.isSolved():
			self.colfill()
			self.rowelim()
			self.rowfill()
			self.colelim()
		return tuple([tuple(row) for row in self.answer])