Knight's tour: Difference between revisions
m (→{{header|Python}}: Decided not to use that board structure.) |
(→{{header|Python}}: Simplify.) |
||
Line 9: | Line 9: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]] |
Knights tour using [[wp:Knight's_tour#Warnsdorff.27s_algorithm|Warnsdorffs algorithm]] |
||
<lang python>import |
<lang python>import copy |
||
boardsize=6 |
boardsize=6 |
||
_position = re.compile(r'^(?:(?P<uc>[A-Z])|(?P<lc>[a-z]))(?P<dig>\d+)$') |
|||
_kmoves = ((2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1)) |
_kmoves = ((2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1)) |
||
def chess2index(chess, boardsize=boardsize): |
def chess2index(chess, boardsize=boardsize): |
||
'Convert Algebraic chess notation to internal index format' |
'Convert Algebraic chess notation to internal index format' |
||
chess = chess.strip().lower() |
|||
x = ord(chess[0]) - ord('a') |
|||
⚫ | |||
uc, lc, num = match.groups() # split chess position |
|||
if lc: |
|||
x = ord(lc) - ord('a') |
|||
else: |
|||
x = ord(uc) - ord('A') |
|||
⚫ | |||
assert 0 <= x < boardsize and 0 <= y < boardsize, ("index '%s' out of range 0..%i" |
|||
% (chess, boardsize -1)) |
|||
return (x, y) |
return (x, y) |
||
Line 57: | Line 48: | ||
access.append( (len(knightmoves(brd, pos, boardsize=boardsize)), pos) ) |
access.append( (len(knightmoves(brd, pos, boardsize=boardsize)), pos) ) |
||
brd[pos] = 0 |
brd[pos] = 0 |
||
return access |
return access |
||
def knights_tour(start, boardsize=boardsize, _debug=False): |
def knights_tour(start, boardsize=boardsize, _debug=False): |
||
Line 76: | Line 65: | ||
print(boardstring(board, boardsize=boardsize)) |
print(boardstring(board, boardsize=boardsize)) |
||
input('\n%2i next: ' % move) |
input('\n%2i next: ' % move) |
||
return board |
return board |
||
Revision as of 15:00, 28 May 2011
Problem: you have a standard 8x8 chessboard, empty but for a single knight on some square. Your task is to emit a series of legal knight moves that result in the knight visiting every square on the chessboard exactly once.
Input and output may be textual or graphical, according to the conventions of the programming environment. If textual, squares should be indicated in Algebraic Notation. The output should indicate the order in which the knight visits the squares, starting with the initial position. The form of the output may be a diagram of the board with the squares numbered ordering to visitation sequence, or a textual list of algebraic coordinates in order, or even an actual animation of the knight moving around the chessboard.
Input: starting square Output: move sequence
Python
Knights tour using Warnsdorffs algorithm <lang python>import copy
boardsize=6 _kmoves = ((2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1))
def chess2index(chess, boardsize=boardsize):
'Convert Algebraic chess notation to internal index format' chess = chess.strip().lower() x = ord(chess[0]) - ord('a') y = boardsize - int(chess[1:]) return (x, y)
def boardstring(board, boardsize=boardsize):
r = range(boardsize) lines = for y in r: lines += '\n' + ','.join('%2i' % board[(x,y)] if board[(x,y)] else ' ' for x in r) return lines
def knightmoves(board, P, boardsize=boardsize):
Px, Py = P kmoves = set((Px+x, Py+y) for x,y in _kmoves) kmoves = set( (x,y) for x,y in kmoves if 0 <= x < boardsize and 0 <= y < boardsize and not board[(x,y)] ) return kmoves
def accessibility(board, P, boardsize=boardsize):
knightmoves(board, P, boardsize=boardsize) access = [] brd = copy.deepcopy(board) for pos in knightmoves(board, P, boardsize=boardsize): brd[pos] = -1 access.append( (len(knightmoves(brd, pos, boardsize=boardsize)), pos) ) brd[pos] = 0 return access
def knights_tour(start, boardsize=boardsize, _debug=False):
board = {(x,y):0 for x in range(boardsize) for y in range(boardsize)} move = 1 P = chess2index(start, boardsize) board[P] = move move += 1 if _debug: print(boardstring(board, boardsize=boardsize)) while move <= len(board): P = min(accessibility(board, P, boardsize))[1] board[P] = move move += 1 if _debug: print(boardstring(board, boardsize=boardsize)) input('\n%2i next: ' % move) return board
if __name__ == '__main__':
while 1: boardsize = int(input('\nboardsize: ')) if boardsize < 5: continue start = input('Start position: ') board = knights_tour(start, boardsize) print(boardstring(board, boardsize=boardsize))</lang>
- Sample runs
boardsize: 5 Start position: c3 19,12,17, 6,21 2, 7,20,11,16 13,18, 1,22, 5 8, 3,24,15,10 25,14, 9, 4,23 boardsize: 8 Start position: h8 38,41,18, 3,22,27,16, 1 19, 4,39,42,17, 2,23,26 40,37,54,21,52,25,28,15 5,20,43,56,59,30,51,24 36,55,58,53,44,63,14,29 9, 6,45,62,57,60,31,50 46,35, 8,11,48,33,64,13 7,10,47,34,61,12,49,32 boardsize: 10 Start position: e6 29, 4,57,24,73, 6,95,10,75, 8 58,23,28, 5,94,25,74, 7,100,11 3,30,65,56,27,72,99,96, 9,76 22,59, 2,63,68,93,26,81,12,97 31,64,55,66, 1,82,71,98,77,80 54,21,60,69,62,67,92,79,88,13 49,32,53,46,83,70,87,42,91,78 20,35,48,61,52,45,84,89,14,41 33,50,37,18,47,86,39,16,43,90 36,19,34,51,38,17,44,85,40,15