import itertools


def inversion(ls):
    length = len(ls)
    counter = 0
    for i in range(0, length-1):
        for j in range(i+1, length):
            counter = counter + (ls[i] > ls[j])
    return counter


def even(num):
    return num % 2 == 0


def odd(num):
    return num % 2 != 0


def valid(game):
    size = len(game)
    zeroless = [item for sublist in game for item in sublist]
    empty_pos = zeroless.index(0)
    empty_pos_row = empty_pos // size
    del zeroless[empty_pos]
    inversions = inversion(zeroless)
    return (odd(size) and even(inversions)) or \
           (even(size) and (even(empty_pos_row) != even(inversions)))


def solvable_tiles(size=3):
    for game in filter(valid,
                       map(lambda x: tuple(zip(*[iter(x)]*size)),
                           itertools.permutations(range(0, size ** 2)))):
        yield game

import math
import random


def number_of_inversions(row):
    sum = 0
    for i in range(0, len(row) - 1):
        for j in range(i + 1, len(row)):
            if row[i] > row[j] and row[j]:
                sum += 1
    return sum


def tuple_of_tuples(row):
    size = int(math.sqrt(len(row)))
    return tuple([tuple([row[j] for j in range(i, i+size)])
                 for i in range(0, len(row), size)])


def blank_on_even_row(row):
    size = int(math.sqrt(len(row)))
    tiles = tuple_of_tuples(row)
    for line in range(size - 2, -1, 2):
        if 0 in tiles[line]:
            return True
    return False


def legal(row):
    size = int(math.sqrt(len(row)))
    if size % 2 != 0 and number_of_inversions(row) % 2 == 0:
        return True
    elif size % 2 == 0 and blank_on_even_row(row) and\
            number_of_inversions(row) % 2 != 0:
        return True
    elif size % 2 == 0 and not blank_on_even_row(row) and\
            number_of_inversions(row) % 2 == 0:
        return True
    else:
        return False


def solvable_tiles(size=3):
    row = random.sample(range(size ** 2), size ** 2)
    solutions = []
    count = 0
    while count < math.factorial(size ** 2)/2:
        if legal(row) and row not in solutions:
            yield tuple_of_tuples(row)
            count += 1
            solutions.append(row)
        else:
            row = random.sample(range(size ** 2), size ** 2)
    raise StopIteration

import random
import math
from itertools import accumulate


def Merge(A, B):
    count = 0
    M = []
    while A and B:
        if A[0] <= B[0]:
            M.append(A.pop(0))
        else:
            count += len(A)
            M.append(B.pop(0))
    M += A + B
    return M, count


def count_inversions(A):
    l = len(A)
    if l > 1:
        n = l // 2
        C = A[:n]
        D = A[n:]
        C, c = count_inversions(A[:n])
        D, d = count_inversions(A[n:])
        B, b = Merge(C, D)
        return B, b + c + d
    else:
        return A, 0


def solvable(sample, size):
    odd = size % 2
    inversions = count_inversions(sample)[1] % 2
    zero = sample.index(0)
    state1 = (odd and inversions != 1)
    state2 = (not odd)
    state3 = (size - math.ceil(zero % size) + 1) % 2 == inversions
    solvable = state1 or (state2 and state3)
    return solvable


def solvable_tiles(size):
    cells = size * size
    factorial = list(accumulate(range(1, cells + 1), lambda a, b: a * b))[-1]
    past = set()
    while True:
        sample = random.sample(range(0, cells), cells)
        iterations = 0
        while tuple(sample) in past or not solvable(sample, size):
            sample = random.sample(range(0, cells), cells)
            iterations += 1
            if iterations > factorial:
                raise StopIteration
        past.add(tuple(sample))
        result = tuple([tuple(sample[(x * size):((x + 1) * size)])
                        for x in range(size)])
        yield result

from itertools import permutations


def inversions(tile, tiles):
    return [
        tile > following_tile and following_tile != 0
        for following_tile in tiles[tiles.index(tile)+1:]
    ].count(True)


def is_solvable(tiles, size):
    inversions_count = sum(inversions(x, tiles) for x in tiles)
    blank_tile_row = tiles.index(0) // size
    if size % 2 == 1 and inversions_count % 2 == 0:
        return True
    if size % 2 == 0 and inversions_count % 2 != blank_tile_row % 2:
        return True
    return False


def solvable_tiles(size=3):
    tiles = permutations(range(size * size), size * size)

    return (
        tuple((tile[i * size: i * size + size]) for i in range(size))
        for tile in tiles
        if is_solvable(tile, size)
    )

from itertools import permutations


def solvable_tiles(size=3):
    def valid(data):
        def inversions(data):
            ind, count = 0, 0
            for num1 in data:
                ind += 1
                for num2 in data[ind::]:
                    if(num1 != 0 and num2 != 0 and num1 > num2):
                        count += 1
            return count

        def blank(data):
            return tuple(reversed(data)).index(0) // size + 1

        inv = not inversions(data) % 2
        return size % 2 and inv or not size % 2 and blank(data) % 2 == inv

    def make_board(data):
        result = ()
        for ind in range(size):
            result += (data[ind * size:(ind + 1) * size],)
        return result

    boards = permutations(range(size ** 2))
    for board in boards:
        if(valid(board)):
            yield make_board(board)

from itertools import permutations


def count_inversions(tile):
    inversions = 0
    for index, item in enumerate(tile):
        for j in range(index, len(tile)):
            if item > tile[j]:
                inversions += 1
    return inversions


def is_solvable(tile, size):
    inversions_count = count_inversions(tile)
    blank_row = int(tile[::-1].index(0)/size)
    A, B, C = size % 2, blank_row % 2, inversions_count % 2
    # B==C
    # (even_blank_row(0..size-1) == even_inversions) or
    # (odd_blank_row_number(0..size-1) == odd_inversions)]
    if (A and not(C)) or (not(A) and (B == C)):
        return True
    else:
        return False


def solvable_tiles(size=3):
    all_tiles = permutations(range(size * size))
    for tile in all_tiles:
        if is_solvable(tile, size):
            tile = [tile[x:x+size] for x in range(0, size * size, size)]
            yield tuple(tile)

import itertools


def count_inversions(arr):
    count = 0
    for i in range(len(arr)):
        for n in arr[i + 1:]:
            if n < arr[i] and n != 0:
                count = count + 1
    return count


def check_zero(arr):
    for i in range(len(arr)):
        for j in range(len(arr[0])):
            if arr[i][j] == 0:
                if i % 2 == 0:
                    return True
                else:
                    return False


def to_table(arr, size):
    table = tuple(arr[n:n + size] for n in range(0, len(arr), size))
    return table


def solvable_tiles(size=3):
    tiles_perm = itertools.permutations(range(size**2))
    if size % 2 == 1:
        for elem in tiles_perm:
            if count_inversions(elem) % 2 == 0:
                yield to_table(elem, size)
    elif size % 2 == 0:
        for elem in tiles_perm:
            if check_zero(to_table(elem, size)) and \
                    count_inversions(elem) % 2 == 1:
                yield to_table(elem, size)
            if not check_zero(to_table(elem, size)) and \
                    count_inversions(elem) % 2 == 0:
                yield to_table(elem, size)

from itertools import permutations


def solvable_tiles(size=3):
    perms = permutations(range(size ** 2))
    for perm in perms:
        if is_solvable(perm, size):
            yield to_tile(perm, size)


def is_solvable(x, size):
    even_inversions = count_inversions(x) % 2 == 0

    if(size % 2 != 0 and even_inversions or
       size % 2 == 0 and blank_on_even_row(x, size) is not even_inversions):
        return True
    else:
        return False


def blank_on_even_row(permutation, size):
    row_counter = 1
    for i in range(len(permutation) - size, -1, -size):
        if(0 in permutation[i:i+size]):
            return row_counter % 2 == 0
        else:
            row_counter += 1


def to_tile(permutation, size):
    result = tuple(tuple(permutation[i:i+size])
                   for i in range(0, len(permutation), size))
    return result


def count_inversions(array):
    return merge(array)[1]


def merge(array):
    if (len(array) < 2):
        return array, 0

    middle_index = int(len(array) / 2)

    left = merge(array[:middle_index])
    right = merge(array[middle_index:])
    count = left[1] + right[1]

    return merge_helper(left[0], right[0], count)


def merge_helper(left, right, count):
    left_length = len(left)
    right_length = len(right)

    sorted_array = []
    i, j = 0, 0

    while i < left_length and j < right_length:
        if left[i] == 0:
            i += 1
        elif right[j] == 0:
            j += 1
        elif left[i] <= right[j]:
            sorted_array.append(left[i])
            i += 1
        elif left[i] > right[j]:
            sorted_array.append(right[j])
            count += left_length - i
            j += 1

    sorted_array += left[i:]
    sorted_array += right[j:]

    return sorted_array, count

import itertools
import math


def solvable_tiles(size=3):
    all_tile_permutations = itertools.permutations(range(size * size))
    return (create_board(permutation) for permutation in all_tile_permutations
            if is_tile_solution(permutation))


def inversions(perm):
    inversion_number = 0
    for i in range(len(perm) - 1, -1, -1):
        for j in range(len(perm) - 1, i, -1):
            if 0 not in [perm[i], perm[j]] and perm[i] > perm[j]:
                inversion_number += 1

    return inversion_number


def is_tile_solution(permutation):
    grid_width = math.sqrt(len(permutation))
    inversion_number_even = inversions(permutation) % 2 == 0
    grid_width_even = grid_width % 2 == 0
    row_with_blank = grid_width - permutation.index(0) // grid_width
    blank_on_even_row_from_bottom = row_with_blank % 2 == 0

    first_condition = not grid_width_even and inversion_number_even
    second_condition = blank_on_even_row_from_bottom == inversion_number_even

    return first_condition or (grid_width_even and second_condition)


def create_board(flattened_board):
    board = []
    board_width = int(math.sqrt(len(flattened_board)))
    row = []
    for index, element in enumerate(flattened_board):
        row.append(element)
        if index % board_width == board_width - 1:
            board.append(tuple(row))
            row = []

    return tuple(board)

from itertools import permutations
from math import sqrt


def even(num):
    return num % 2 == 0


def countRows(grid):
    count = 0
    for i in range(len(grid)):
        if grid[i] == 0:
            count = i
    return len(grid) - count/sqrt(len(grid))


def countInversions(grid):
    count = 0
    for i in range(1, len(grid)):
        for j in range(i):
            if(grid[j] > grid[i]):
                count += 1
    return count


def slice(grid):
    l = int(sqrt(len(grid)))
    new = []
    for i in range(l):
        new.append(tuple(grid[i*l:(i+1)*l]))
    return tuple(new)


def solvable(grid):
    if even(len(grid)):
        return even(countInversions(grid)) != even(countRows(grid))
    else:
        return even(countInversions(grid))


def solvable_tiles(size=3):
    if(size <= 0):
        raise ValueError
    return map(slice, filter(solvable, permutations(range(size*size))))

from itertools import permutations
import random


def count_inversions(a):
    length = len(a)
    if length > 1:
        mid = length // 2
        left, left_inversions = count_inversions(a[:mid])
        right, right_inversions = count_inversions(a[mid:])
        merge, inversions = merge_count(left, right)
        return merge, left_inversions + right_inversions + inversions
    else:
        return a, 0


def merge_count(a, b):
    count = 0
    merge = []
    while a and b:
        if a[0] <= b[0]:
            merge.append(a.pop(0))
        else:
            count += len(a)
            merge.append(b.pop(0))
    merge.extend(a + b)
    return merge, count


def get_blank_row(grid):
    for index, row in enumerate(reversed(grid)):
        if 0 in row:
            return index + 1


def is_grid_solvable(grid, grid_width):
    elements = [elem for row in grid for elem in row]
    elements.remove(0)
    inversions_count = count_inversions(elements)[1]
    blank_row = get_blank_row(grid)
    if grid_width % 2 == 0 and blank_row % 2 == 0:
        return inversions_count % 2 == 1
    else:
        return inversions_count % 2 == 0


def solvable_tiles(size=3):
    count = size * size
    numbers = list(range(0, count))
    random.shuffle(numbers)
    numbers = permutations(numbers)
    for current in numbers:
        grid = tuple([tuple(current[x:x+size]) for x in range(0, count, size)])
        if is_grid_solvable(grid, size):
            yield grid

from math import factorial
from itertools import permutations


def is_even(num):
    return num % 2 == 0


def get_inversions(arr, left, right):
    left_index = 0
    right_index = 0
    arr_next_index = 0
    inversions_count = 0
    left_len = len(left)
    right_len = len(right)
    while left_index < left_len or right_index < right_len:
        arr_next_index = left_index+right_index
        if left_index == left_len:
            arr[arr_next_index] = right[right_index]
            right_index += 1
        elif right_index == right_len:
            arr[arr_next_index] = left[left_index]
            left_index += 1
        elif left[left_index] <= right[right_index]:
            arr[arr_next_index] = left[left_index]
            left_index += 1
        else:
            arr[arr_next_index] = right[right_index]
            if not right[right_index] == 0:
                inversions_count += left_len - left_index
            right_index += 1
    return inversions_count


def inversions_count(arr):
    arr_len = len(arr)
    if arr_len < 2:
        return 0

    middle = (arr_len + 1) // 2
    left = arr[:middle]
    right = arr[middle:arr_len]
    return (inversions_count(left) +
            inversions_count(right) +
            get_inversions(arr, left, right))


def is_solvable(game_board, board_width):
    blank_tile_row = game_board.index(0) // board_width
    board_inversions = inversions_count(game_board)
    board_width_even = is_even(board_width)
    board_inversions_even = is_even(board_inversions)
    blank_tile_on_odd_row = not is_even(blank_tile_row % board_width)
    return ((not board_width_even and board_inversions_even) or
            (board_width_even and
                (blank_tile_on_odd_row == board_inversions_even)))


def solvable_tiles(size=3):
    if size <= 0:
        raise ValueError("Game board size cannot be less than 1")
    board_size = size * size
    numbers = list(range(board_size))
    max_number_of_boards = factorial(board_size)
    used_boards = []
    for permutation in permutations(numbers):
        if is_solvable(list(permutation), size):
            yield tuple(
                [permutation[i:i+size] for i in range(0, board_size, size)]
            )
    raise StopIteration

from functools import reduce
from math import sqrt
from itertools import permutations


def inv_count(arr):
    return reduce(lambda x, y: x + y,
                  [1 for i in range(len(arr)-1)
                   for j in range(i+1, len(arr)) if arr[i] > arr[j]], 0)


def even(n):
    return n % 2 == 0


def odd(n):
    return n % 2 == 1


def is_solvable(board):
    board = list(board)
    size = int(sqrt(len(board)))

    zero_index = (board.index(0) // size, board.index(0) % size)
    board.remove(0)

    zero_row = size - zero_index[0]
    inversions = inv_count(board)

    return any([odd(size) and even(inversions),
                (even(size) and
                ((odd(inversions) and even(zero_row)) or
                 (even(inversions) and odd(zero_row))))])


def solvable_tiles(size=3):
    game = list(range(size*size))
    solvables = filter(is_solvable, permutations(game))
    while True:
        current = next(solvables)
        result = [tuple([current[j] for j in range(i*size, size*(i + 1))])
                  for i in range(size)]

        yield tuple(result)

import itertools


def solvable_tiles(size):
    return Board(size)


class Board:
    def __init__(self, size):
        self.__size = size
        self.__max_number = size * size
        self.__permutations = itertools.permutations(
            list(range(0, self.__max_number)))

    def __iter__(self):
        return self

    def __next__(self):
        for permutation in self.__permutations:
            if self.__check_if_solvable(permutation):
                board = self.__convert_to_board(permutation)
                return board
            else:
                continue

        raise StopIteration()

    def __check_if_solvable(self, permutation):
        cnt_inversions = 0
        for i in range(self.__max_number):
            if permutation[i] == 0:
                blank_on_row = i / self.__size

            for j in range(i, self.__max_number):
                if permutation[i] > permutation[j]:
                    cnt_inversions += 1

        if blank_on_row % 2 == 2:
            blank_on_odd = False
        else:
            blank_on_odd = True

        if self.__size % 2 != 0 and cnt_inversions % 2 == 0:
            return True
        elif self.__size % 2 == 0 and \
                not blank_on_odd and \
                cnt_inversions % 2 == 0:
            return True
        elif self.__size % 2 == 0 and blank_on_odd and cnt_inversions % 2 != 0:
            return True

        return False

    def __convert_to_board(self, permutation):
        splitted = [permutation[i:i + self.__size]
                    for i in range(0, self.__max_number, self.__size)]

        return tuple(tuple(row) for row in splitted)

from itertools import chain, repeat
from itertools import permutations


def number_of_inversions(iterable):
    tmp = list(iterable)
    length = len(tmp)
    count = 0
    for i in range(0, length - 1):
        for j in range(i + 1, length):
            if tmp[j] < tmp[i]:
                count += 1
    return count


class ZipExhausted(Exception):
    pass


def izip_longest(*args, **kwds):
    fillvalue = kwds.get('fillvalue')
    counter = [len(args) - 1]

    def sentinel():
        if not counter[0]:
            raise ZipExhausted
        counter[0] -= 1
        yield fillvalue
    fillers = repeat(fillvalue)
    iterators = [chain(it, sentinel(), fillers) for it in args]
    try:
        while iterators:
            yield tuple(map(next, iterators))
    except ZipExhausted:
        pass


def grouper(iterable, n, fillvalue=None):
    args = [iter(iterable)] * n
    return izip_longest(fillvalue=fillvalue, *args)


def zero_position(grid, size):
    tmp = list(grid)
    for i in range(0, size):
        if 0 in set(tmp[i]):
            return i


def solvable_tiles(size=3):
    length = size ** 2
    tmp = permutations(range(0, length))

    for perm in tmp:
        num_inv = number_of_inversions(perm)
        grid = tuple(grouper(perm, size))
        zero_pos = zero_position(grid, size)

        if any([((size % 2 != 0) and (num_inv % 2 == 0)),
                (size % 2 == 0 and num_inv % 2 == 0 and zero_pos % 2 != 0),
                (size % 2 == 0 and num_inv % 2 != 0 and zero_pos % 2 == 0)]):
            yield grid
        else:
            pass

    raise StopIteration

from itertools import permutations


class TilesGame:
    def __init__(self, size):
        self.__size = size
        self.__permutations = permutations(range(self.__size ** 2))

    def __iter__(self):
        return self

    def __find_number_of_inversions(self, perm):
        inversions = 0
        checked_tiles = [0] * (self.__size ** 2 - 1)
        for tile in perm:
            if tile:
                checked_tiles[tile - 1] = 1
                inversions += checked_tiles[:tile].count(0)
        return inversions

    def __is_solvable(self, perm):
        inversions = self.__find_number_of_inversions(perm)
        blank_el_row = self.__size - perm.index(0) // self.__size
        cases = [
            all([self.__size % 2, not inversions % 2]),
            all([not self.__size % 2, not blank_el_row % 2, inversions % 2]),
            all([not self.__size % 2, blank_el_row % 2, not inversions % 2])
        ]
        return any(cases)

    def __next__(self):
        while True:
            perm = next(self.__permutations)
            if self.__is_solvable(perm):
                return tuple(tuple(perm[i:i + self.__size]) for i in range(
                                                    0, len(perm), self.__size))


def solvable_tiles(size=3):
    return TilesGame(size)

from itertools import permutations


def inversion_count(board):
    inversions = 0
    for this in board:
        for other in board:
            if this > other and board.index(this) < board.index(other):
                if other != 0:
                    inversions += 1
    return inversions


def find_empty(board):
    length = len(board) ** (1/2)
    return int(board.index(0) / length)


def solvable(board):
    inversions = inversion_count(board)
    zero_pos = find_empty(board)
    if len(board) % 2 == 1 and inversions % 2 == 0:
        return True
    elif len(board) % 2 == 0 and zero_pos % 2 == 1 and inversions % 2 == 0:
        return True
    elif len(board) % 2 == 0 and zero_pos % 2 == 0 and inversions % 2 == 1:
        return True
    return False


def to_tuple(board, size):
    nested_lst = []
    for row in range(size):
        helper = []
        for col in range(size):
            helper.append(board[row*size+col])
        nested_lst.append(helper)
    nested_tuple_of_tuples = tuple(tuple(l) for l in nested_lst)
    return nested_tuple_of_tuples


def solvable_tiles(size=3):
    chances = permutations(range(size*size))
    while True:
        grid = next(chances)
        if solvable(list(grid)):
            solvable_grid = to_tuple(grid, size)
            yield solvable_grid
    raise StopIteration

import itertools

class BoardGenerator:

    def __init__(self, size):
        self.size = size
        numbers = range(size * size)
        self.boards = itertools.permutations(numbers)
        self.solvable_boards = (board for board in self.boards if self.is_solvable(board))

    def __iter__(self):
        return self

    def __next__(self):
        row = next(self.solvable_boards)
        chunks=[row[x:x + self.size] for x in range(0, len(row), self.size)]
        return tuple(chunks)

    def is_solvable(self, board):
        inversions = len([board[index] for index in range(len(board)) 
            for x in board[index:] if board[index] > x])
        blank_on = round((len(board) - board.index(0)) / self.size)
        if self.size % 2 == 0:
            return (inversions % 2 == 0) == (blank_on % 2 != 0)
        else:
            return inversions % 2 == 0

def solvable_tiles(size=3):
    board_generator = BoardGenerator(size)
    return board_generator

import itertools


def bubble_sort_count(board):
    array = board
    array = list(array)
    swaps_counter = 0
    swap_executed = True
    while swap_executed:
        swap_executed = False
        for i in range(0, len(array) - 1):
            if array[i+1] < array[i]:
                array[i+1], array[i] = array[i], array[i+1]
                swap_executed = True
                if array[i+1] != 0 and array[i] != 0:
                    swaps_counter += 1
    return swaps_counter


def find_line_of_blank(board):
    rev = list(reversed(board))
    length = int(len(rev)**0.5)
    found = False
    index = 0
    i = 0
    while i < length and not found:
        for j in range(0, length):
            if rev[i*length+j] == 0:
                index = i
                found = True
        i += 1
    return index


def solvability(board):
    even_count = bubble_sort_count(board) % 2 == 0
    even_size = (len(board)**0.5) % 2 == 0
    even_blank = (find_line_of_blank(board) + 1) % 2 == 0
    if ((not even_size) and even_count) or \
            (even_size and ((not even_blank) == even_count)):
        return True
    return False


def tupify(tup):
    l = int(len(tup)**0.5)
    return tuple([tup[i:i+l] for i in range(0, len(tup), l)])


class Tiles:
    def __init__(self, generator):
        self.iterator = generator

    def __next__(self):
        return tupify(next(self.iterator))

    def __iter__(self):
        return self


def solvable_tiles(size=3):
    gen = filter(solvability, itertools.permutations(range(0, size*size)))
    return Tiles(gen)

import itertools


def count_inversions_helper(list_help, position):
    x = list_help[position]
    count = 0
    for i in range(position, len(list_help)):
        if x > list_help[i] and list_help[i] != 0:
            count = count + 1
    return count


def count_inversions(list_help):
    count = 0
    for i in range(0, len(list_help)):
        count = count + count_inversions_helper(list_help, i)
    return count


def zero_row_bottom(list_help, size):
    for i in range(len(list_help) - 1, -1, -1):
        if list_help[i] == 0:
            position = i
            break
    return size - int(position/size) - 1


class generator:
    def __init__(self, size):
        self.iterable = itertools.permutations(range(0, size * size))
        self.size = size

    def __iter__(self):
        return self

    def __next__(self):
        l = list(next(self.iterable))
        list_of_lists = []
        k = 0
        for i in range(0, self.size):
            helper = []
            for j in range(0, self.size):
                helper.append(l[k])
                k = k + 1
            list_of_lists.append(helper)
        result = tuple(tuple(x) for x in list_of_lists)
        zero_place = zero_row_bottom(l, self.size)
        count_inv = count_inversions(l)
        condition1 = self.size % 2 == 1 and count_inv % 2 == 0
        condition2 = self.size % 2 == 0 and zero_place % 2 == 1 and \
            count_inv % 2 == 1
        condition3 = self.size % 2 == 0 and zero_place % 2 == 0 and \
            count_inv % 2 == 0
        if condition1 or condition2 or condition3:
            return result
        else:
            return next(self)


def solvable_tiles(size=3):
    return generator(size)

from itertools import permutations


def grid_solvable(flat_grid, width):
    size = len(flat_grid)
    inv = 0
    for i in range(size):
        if flat_grid[i] == 0:
            blank = i
        for j in range(i + 1, size):
            if flat_grid[i] > flat_grid[j] and flat_grid[j] != 0:
                inv += 1

    blank_row_rev = width - blank//width
    return not(inv % 2) if width % 2 else blank_row_rev % 2 == (not(inv % 2))


def split_grid(flat_grid, size):
    return tuple([flat_grid[i:i+size] for i in range(0, len(flat_grid), size)])


def solvable_tiles(size=3):
    perms = permutations(range(size*size))
    return (split_grid(p, size) for p in perms if grid_solvable(p, size))

from itertools import permutations


def even(permutation):
    invertions = 0
    for i in range(0, len(permutation) - 1):
        invertions += sum(x < permutation[i] for x in permutation[i:])
    return invertions % 2 == 0


def solvable(permutation, size):
    odd_row = (size - permutation.index(0) // size) % 2 == 1
    return ((size % 2 == 1 and even(permutation)) or
            (size % 2 == 0 and odd_row == even(permutation)))


def split(tile, size):
    args = [iter(tile)] * size
    return tuple(zip(*args))


def solvable_tiles(size=3):
    for tile in permutations(range(size**2)):
        if solvable(tile, size):
            yield split(tile, size)