fork download
copy 
  1. import random
  2.  
  3.  
  4. class Solver:
  5.     def __init__(self, n: int, possibleMoves: list):
  6.         self.__n = n
  7.         self.__nSquared = n * n
  8.         self.__possibleMoves = possibleMoves
  9.         self.__orderTable = None
  10.  
  11.     def Solve(self, startPosition: tuple = (-1, -1), pickMoveCandidatesInRandomOrder: bool = True) -> bool:
  12.         self.__orderTable = [[0 for x in range(self.__n)] for y in range(self.__n)]
  13.  
  14.         x, y = startPosition
  15.         if x == y == -1:
  16.             x, y = random.randrange(self.__n), random.randrange(self.__n)
  17.         self.__orderTable[y][x] = 1
  18.  
  19.         for alreadyOrdered in range(1, self.__nSquared):
  20.             nx, ny = self.__NextFrom(x, y, pickMoveCandidatesInRandomOrder)
  21.             if nx == ny == -1:
  22.                 return False
  23.             self.__orderTable[ny][nx] = alreadyOrdered + 1
  24.             x, y = nx, ny
  25.         return True
  26.  
  27.     def PrintSolution(self):
  28.         maxDigits = len(str(self.__nSquared))
  29.         for row in self.__orderTable:
  30.             print(' '.join((f'{value:{maxDigits}}' for value in row)))
  31.  
  32.     def __NextFrom(self, x, y, pickMoveCandidatesInRandomOrder: bool):
  33.         nx, ny = -1, -1
  34.         minDegree = len(self.__possibleMoves) + 1
  35.  
  36.         validDestinations = self.__ValidDestinationsFrom(x, y)
  37.         if pickMoveCandidatesInRandomOrder:
  38.             validDestinations = self.__ValidDestinationsInRandomOrderFrom(x, y)
  39.  
  40.         for dstX, dstY in validDestinations:
  41.             dstDegree = self.__CalculateDegreeOf(dstX, dstY)
  42.             if dstDegree < minDegree:
  43.                 minDegree = dstDegree
  44.                 nx, ny = dstX, dstY
  45.         return nx, ny
  46.  
  47.     def __InBounds(self, x, y):
  48.         return 0 <= x < self.__n and 0 <= y < self.__n
  49.  
  50.     def __ValidDestinationsFrom(self, x, y):
  51.         for dx, dy in self.__possibleMoves:
  52.             nx, ny = x + dx, y + dy
  53.             if self.__InBounds(nx, ny) and self.__orderTable[ny][nx] == 0:
  54.                 yield nx, ny
  55.  
  56.     def __ValidDestinationsInRandomOrderFrom(self, x, y):
  57.         validDestinations = list(self.__ValidDestinationsFrom(x, y))
  58.         random.shuffle(validDestinations)
  59.         return validDestinations
  60.  
  61.     def __CalculateDegreeOf(self, x, y):
  62.         return sum(1 for dst in self.__ValidDestinationsFrom(x, y))
  63.  
  64.  
  65. if __name__ == '__main__':
  66.     n = 10
  67.     moves = [(3, 0), (2, 2), (0, 3), (-2, 2), (-3, 0), (-2, -2), (0, -3), (2, -2)]
  68.     # moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
  69.     solver = Solver(n, moves)
  70.  
  71.     while True:
  72.         if solver.Solve(startPosition=(0, 0), pickMoveCandidatesInRandomOrder=False):
  73.             solver.PrintSolution()
  74.             break
  75.  
  76.     iterationsCount = 1000
  77.     successCount = sum(int(solver.Solve(pickMoveCandidatesInRandomOrder=False)) for i in range(iterationsCount))
  78.     print(f'Success in {successCount} of {iterationsCount} iterations without random candidates ordering.')
  79.     successCount = sum(int(solver.Solve(pickMoveCandidatesInRandomOrder=True)) for i in range(iterationsCount))
  80.     print(f'Success in {successCount} of {iterationsCount} iterations with random candidates ordering.')
  81.  
Success #stdin #stdout 3.24s 11704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
  1  75  68   2 100  81  23  99  82  22
 66  18  15  77  19  14  92  20  13  91
 69   3  60  74  71  61  97  72  24  98
 16  76  67  17  93  80  28  94  83  21
 65  45  70  78  63  73  89  62  12  90
 38   4  59  43  29  50  96  30  25  95
 47  35  64  46  88  79  27  87  84   8
 56  44  39  55  58  42  54  51  11  31
 37   5  48  36   6  49  85   7  26  86
 40  34  57  41  33  52  10  32  53   9
Success in 889 of 1000 iterations without random candidates ordering.
Success in 800 of 1000 iterations with random candidates ordering.
https://ideone.com/vlqBwa
language:
Python 3 (python  3.9.5)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!