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 :)

Difficulty: interview

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 "█"


# TODO it should take List[Clue] as argument
# TODO boeard should be List[List[Box]]


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]):
        # print("comparing: ", initial, [i.value for i in constrains] )

        def tmp(element: int, constrain: Box):
            if constrain.value is None:
                # print("constrain is None")
                return True

            return constrain.value == element

        ddd =  all((tmp(data, req) for data, req in zip(initial, constrains)))
        # print("comparing: ", initial, [i.value for i in constrains], ddd )
        return ddd;

    # TODO: collect always to the same list

    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):
        # b is a list of lists here
        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)


# TODO: Finish this!
def solve(clues, width: int, height: int) -> List[List[int]]:
    """
    :param height:
    :type width: object
    """
    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])