import itertools | |
def count_inversions(my_list): | |
iterations = 0 | |
for elem in my_list: | |
if elem != 0: | |
for number in my_list[:my_list.index(elem)]: | |
if number > elem: | |
iterations += 1 | |
return iterations | |
def to_tuple(board, size): | |
new_list = [tuple(board[i:i+size]) for i in range(0, len(board), size)] | |
return tuple(new_list) | |
def solvable(board, size): | |
inversions = count_inversions(board) | |
if size % 2 == 1 and inversions % 2 == 0: | |
return True | |
if size % 2 == 0 and ((blank_elem_index(board, size) % 2 == 0) == (inversions % 2 == 0)): | |
return True | |
return False | |
def blank_elem_index(board, size): | |
my_tuple = to_tuple(board, size) | |
for elem in my_tuple: | |
if 0 in elem: | |
return my_tuple.index(elem) + 1 | |
def solvable_tiles(size=4): | |
board = [number for number in range((size) ** 2)] | |
for perm in itertools.permutations(board): | |
inversions = count_inversions(perm) | |
if solvable(board, size): | |
yield to_tuple(perm, size) | |
else: | |
yield | |
if __name__ == '__main__': | |
my = solvable_tiles(4) | |
print(next(my)) | |
print(next(my)) | |
print(next(my)) | |
print(next(my)) | |
print(next(my)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment