Created
April 6, 2018 11:15
-
-
Save LeReverandNox/0ed757bb6e588d9a4cff45aaf9ff16ca to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from collections import namedtuple | |
| Point = namedtuple('Point', ['y', 'x']) | |
| class KTSolver(object): | |
| def __init__(self, grid_size): | |
| self._grid_size = grid_size | |
| self._moves = [] | |
| self._grid = [] | |
| self._solutions = [] | |
| self.highest_try = 0 | |
| self.tries_count = 0 | |
| self._init_grid() | |
| self._init_moves() | |
| def _init_grid(self): | |
| self._grid = [[0 for _ in range(self._grid_size)] for _ in range(self._grid_size)] | |
| def _init_moves(self): | |
| self._moves = [ | |
| Point(-2, -1), | |
| Point(-2, 1), | |
| Point(-1, 2), | |
| Point(1, 2), | |
| Point(2, 1), | |
| Point(2, -1), | |
| Point(1, -2), | |
| Point(-1, -2) | |
| ] | |
| def _print_grid(self): | |
| pass | |
| s = [[str(e) for e in row] for row in self._grid] | |
| lens = [max(map(len, col)) for col in zip(*s)] | |
| fmt = ' '.join('{{:{}}}'.format(x) for x in lens) | |
| table = [fmt.format(*row) for row in s] | |
| print('\n'.join(table)) | |
| print('') | |
| def test_moves(self): | |
| for i, move in enumerate(self._moves): | |
| point = Point(4, 4) | |
| next_point = Point(point.y + move.y, point.x + move.x) | |
| if self._can_move(next_point): self._do_move(next_point, i+1) | |
| self._print_grid() | |
| def _can_move(self, point): | |
| if (point.y >= 0 and point.y < self._grid_size) and (point.x >= 0 and point.x < self._grid_size) and self._grid[point.y][point.x] == 0: | |
| return True | |
| return False | |
| def _do_move(self, point, i): | |
| self._grid[point.y][point.x] = i | |
| def _undo_move(self, point): | |
| self._grid[point.y][point.x] = 0 | |
| def solve(self): | |
| for start_point in self._get_grid_generator(): | |
| print('Starting solving at {},{}, for a {}*{} grid'.format(start_point.y, start_point.x, self._grid_size, self._grid_size)) | |
| self._init_grid() | |
| self._do_move(start_point, 1) | |
| if (self._try_move(start_point, 1)): | |
| print('On a trouve une solution') | |
| self._print_grid() | |
| else: | |
| print('Pas de solution') | |
| break | |
| def _get_grid_generator(self): | |
| for y in range(self._grid_size): | |
| for x in range(self._grid_size): | |
| yield Point(y, x) | |
| def _try_move(self, point, move_count): | |
| # print('Move n{} of {}'.format(move_count, self._grid_size ** 2)) | |
| # self.tries_count += 1 | |
| # if move_count >= self.highest_try: | |
| # self.highest_try = move_count | |
| # print(self.highest_try) | |
| # print(self.tries_count, '\n') | |
| # self._print_grid() | |
| if move_count == self._grid_size ** 2: | |
| return True | |
| for move in self._moves: | |
| next_point = Point(point.y + move.y, point.x + move.x) | |
| # print('Trying to move to {}, {}'.format(next_point.y, next_point.x)) | |
| if self._can_move(next_point): | |
| self._do_move(next_point, move_count + 1) | |
| if not self._try_move(next_point, move_count +1): | |
| # print('Undoing move to {}, {}'.format(next_point.y, next_point.x)) | |
| self._undo_move(next_point) | |
| else: | |
| return True | |
| return False | |
| if __name__ == '__main__': | |
| kts = KTSolver(grid_size=6) | |
| # kts.test_moves() | |
| kts.solve() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment