Here is a working example in Python 2 that uses a timer to go through the board and illustrates the solution. I find the node closest to the edge of the board for tie breakers, and if both are same, I just return the first. This seemed a natural choice since cells closer to the edge should have less possible moves if the board is empty. Seems to be working well, but as Panos mentions, there is a 1% fail rate with Arnd Roth's proposition. This code can be easily modified to use Ira Pohl's Proposition. Visit node can be modified to run possible_unvisited_moves again against the nodes that both had the minimum moves. In case of ties, using the first should work.
class GNode(object):
""" Used to represent a node in the graph """
def __init__(self, value, row=None, col=None):
self.row = row # allows node to know its loc. in array
self.col = col
self.value = value
def setup_graph(n):
""" Create x by x grid (graph inside an array). """
graph = []
for row in range(n):
graph.append([])
for col in range(n):
graph[row].append(GNode(None,row=row, col=col))
return graph
def possible_moves(graph_node, total):
""" Find out all possible moves for the current node position. """
moves = []
move_patterns = [[-1,-2], [-1, 2], [-2, 1], [-2, -1], [1, -2], [1, 2], [2, 1], [2, -1]]
for row, col in move_patterns:
move_row = graph_node.row + row; move_col = graph_node.col + col
if move_row >= 0 and move_col >= 0 and move_row < total and move_col < total:
moves.append([move_row, move_col])
return moves
def possible_unvisited_moves(graph_node, grid):
"""Get all possible moves and weed out the ones that are already visited.
visited means they have a value.
"""
moves = possible_moves(graph_node, len(grid))
unvisited = []
for move in moves:
if grid[move[0]][move[1]].value is None:
unvisited.append(move)
return unvisited
def closest_to_edge(pos1, pos2, total):
""" Find out which position is closest to the edge of board, and return it.
pos are 2 arrays [x,y], total is the board size (length)
"""
total -= 1
pos1_min = min(total - pos1[0], pos1[0], pos1[1], total-pos1[1])
pos2_min = min(total - pos2[0], pos2[0], pos2[1], total-pos2[1])
if pos2_min < pos1_min: return pos2
return pos1 # default
def visit_node(graph_node, graph):
""" Check possible unvisited moves from the pos & find next move to make """
graph_node.value = "{}{}".format(graph_node.row, graph_node.col) # visited
p_moves = possible_unvisited_moves(graph_node, graph)
next_move = None
min_no_moves = 9 # highest can be 8 for knights move pattern
for move in p_moves:
next_moves = possible_unvisited_moves(graph[move[0]][move[1]], graph)
if len(next_moves) < min_no_moves:
next_move = move
min_no_moves = len(next_moves)
elif len(next_moves) == min_no_moves:
min_move = closest_to_edge(next_move, move, len(graph))
if min_move != next_move:
next_move = min_move
min_no_moves = len(next_moves)
if next_move:
os.system(clear_screen)
print "This Move: [",graph_node.row, ",", graph_node.col, "]. Next Move: ", next_move, "Min Moves from next: ", min_no_moves
display_graph(graph)
import time
time.sleep(.5)
return visit_node(graph[next_move[0]][next_move[1]], graph)
else:
os.system(clear_screen)
display_graph(graph)
return "Done"
def display_graph(graph):
print ""
for row in graph:
row_vals = []
for cell in row:
row_vals.append(cell.value)
print row_vals
import os
clear_screen = 'cls' if os.name == 'nt' else 'clear'
graph = setup_graph(8)
print visit_node(graph[4][4], graph)
Have fun playing with it. :)
