Last couple of days, I have refrained myself from master's studies and have been focusing on this (seemingly simple) puzzle:
There is this 10*10 grid which constitutes a square of 100 available places to go. The aim is to start from a corner and traverse through all the places with respect to some simple "traverse rules" and reach number 100 (or 99 if you're a programmer and start with 0 instead :)
The rules for traversing are:
1. Two spaces hop along the vertical and horizontal axis
2. One space hop along the diagonals
3. You can visit each square only once
To visualise better, here is a valid example traverse (up to the 8th step):
Example Traverse http://img525.imageshack.us/img525/280/squarepuzzle.png
Manually, I have been working on this puzzle out of boredom. For years, I have tried to solve it by hand from time to time, but I have never gone beyond 96. Sounds easy? Try yourself and see for yourself :)
Thus, in order to solve the problem, I have developed a short (around 100 lines of code) program in Python. I am a beginner in this language I wanted to see what I can do.
The program simply applies exhaustive try & error solving technique. In other words: brute force depth first search.
My question arises from here on: The program, unfortunately cannot solve the problem because the state space is so big that search never ends withouh ever finding a solution. It can go up to number 98 (and prints that) without much difficulty, nonetheless not a complete solution.
The program also prints out the length of the search tree it has covered so far. In a couple of minutes, the traverse list from, say, 65th element is covered till the end, for just one single path. This number decreases in exponentially increasing time periods. I have run the code for quite some time and could not get beyond 50 barrier and now I am convinced.
It seems that this simple approach will not be enough unless I run it for ever. So, how can I improve my code to be faster and more efficient so that it comes up with solutions?
Basically, I am looking forward to see ideas on how to:
Apply programming techniques/tricks to overcome exhaustion
..and finally realize into a substantial solution.
Thanks in advance.
Revision
Thanks to Dave Webb for relating the problem to domain it belongs:
This is very similar to the Knight's Tour problem which relates moving a knight around a chess board without revisiting the same square. Basically it's the same problem but with different "Traverse Rules".
Eventually, I have come up with the modified Python code to overcome the problem. I've tun the code for a couple of hours and it has already found half a million solutions in a couple of hours.
The full set of solutions still require a total exhaustive search, i.e. to let the program run until it finishes with all combinations. However, reaching "a" legitimate solution can be reduced to "linear time".
First, things I have learned:
Thanks to Dave Webb's answer and ammoQ's answer. The problem is indeed an extension of Hamiltonian Path problem as it is NP-Hard. There is no "easy" solution to begin with. There is a famous riddle of Knight's Tour which is simply the same problem with a different size of board/grid and different traverse-rules. There are many things said and done to elaborate the problem and methodologies and algorithms have been devised.
Thanks to Joe's answer. The problem can be approached in a bottom-up sense and can be sliced down to solvable sub-problems. Solved sub-problems can be connected in an entry-exit point notion (one's exit point can be connected to one other's entry point) so that the main problem could be solved as a constitution of smaller scale problems. This approach is sound and practical but not complete, though. It can not guarantee to find an answer if it exists.
Upon exhaustive brute-force search, here are key points I have developed on the code:
Warnsdorff's algorithm: This algorithm is the key point to reach to a handy number of solutions in a quick way. It simply states that, you should pick your next move to the "least accessible" place and populate your "to go" list with ascending order or accesibility. Least accessible place means the place with least number of possible following moves.
Below is the pseudocode (from Wikipedia):
Some definitions:
Algorithm:
set P to be a random initial position on the board mark the board at P with the move number "1" for each move number from 2 to the number of squares on the board, let S be the set of positions accessible from the input position set P to be the position in S with minimum accessibility mark the board at P with the current move number return the marked board -- each square will be marked with the move number on which it is visited.
And here is my code in Python which solves the riddle (to an acceptable degree considering that the problem is NP-Hard). The code is easy to understand as I consider myself at beginner level in Python. The comments are straightforward in explaining the implementation. Solutions can be displayed on a simple grid by a basic GUI (guidelines in the code).
# Solve square puzzle
import operator
class Node:
# Here is how the squares are defined
def __init__(self, ID, base):
self.posx = ID % base
self.posy = ID / base
self.base = base
def isValidNode(self, posx, posy):
return (0<=posx<self.base and 0<=posy<self.base)
def getNeighbors(self):
neighbors = []
if self.isValidNode(self.posx + 3, self.posy): neighbors.append(self.posx + 3 + self.posy*self.base)
if self.isValidNode(self.posx + 2, self.posy + 2): neighbors.append(self.posx + 2 + (self.posy+2)*self.base)
if self.isValidNode(self.posx, self.posy + 3): neighbors.append(self.posx + (self.posy+3)*self.base)
if self.isValidNode(self.posx - 2, self.posy + 2): neighbors.append(self.posx - 2 + (self.posy+2)*self.base)
if self.isValidNode(self.posx - 3, self.posy): neighbors.append(self.posx - 3 + self.posy*self.base)
if self.isValidNode(self.posx - 2, self.posy - 2): neighbors.append(self.posx - 2 + (self.posy-2)*self.base)
if self.isValidNode(self.posx, self.posy - 3): neighbors.append(self.posx + (self.posy-3)*self.base)
if self.isValidNode(self.posx + 2, self.posy - 2): neighbors.append(self.posx + 2 + (self.posy-2)*self.base)
return neighbors
# the nodes go like this:
# 0 => bottom left
# (base-1) => bottom right
# base*(base-1) => top left
# base**2 -1 => top right
def solve(start_nodeID, base):
all_nodes = []
#Traverse list is the list to keep track of which moves are made (the id numbers of nodes in a list)
traverse_list = [start_nodeID]
for i in range(0, base**2): all_nodes.append(Node(i, base))
togo = dict()
#Togo is a dictionary with (nodeID:[list of neighbors]) tuples
togo[start_nodeID] = all_nodes[start_nodeID].getNeighbors()
solution_count = 0
while(True):
# The search is exhausted
if not traverse_list:
print "Somehow, the search tree is exhausted and you have reached the divine salvation."
print "Number of solutions:" + str(solution_count)
break
# Get the next node to hop
try:
current_node_ID = togo[traverse_list[-1]].pop(0)
except IndexError:
del togo[traverse_list.pop()]
continue
# end condition check
traverse_list.append(current_node_ID)
if(len(traverse_list) == base**2):
#OMG, a solution is found
#print traverse_list
solution_count += 1
#Print solution count at a steady rate
if(solution_count%100 == 0):
print solution_count
# The solution list can be returned (to visualize the solution in a simple GUI)
#return traverse_list
# get valid neighbors
valid_neighbor_IDs = []
candidate_neighbor_IDs = all_nodes[current_node_ID].getNeighbors()
valid_neighbor_IDs = filter(lambda id: not id in traverse_list, candidate_neighbor_IDs)
# if no valid neighbors, take a step back
if not valid_neighbor_IDs:
traverse_list.pop()
continue
# if there exists a neighbor which is accessible only through the current node (island)
# and it is not the last one to go, the situation is not promising; so just eliminate that
stuck_check = True
if len(traverse_list) != base**2-1 and any(not filter(lambda id: not id in traverse_list, all_nodes[n].getNeighbors()) for n in valid_neighbor_IDs): stuck_check = False
# if stuck
if not stuck_check:
traverse_list.pop()
continue
# sort the neighbors according to accessibility (the least accessible first)
neighbors_ncount = []
for neighbor in valid_neighbor_IDs:
candidate_nn = all_nodes[neighbor].getNeighbors()
valid_nn = [id for id in candidate_nn if not id in traverse_list]
neighbors_ncount.append(len(valid_nn))
n_dic = dict(zip(valid_neighbor_IDs, neighbors_ncount))
sorted_ndic = sorted(n_dic.items(), key=operator.itemgetter(1))
sorted_valid_neighbor_IDs = []
for (node, ncount) in sorted_ndic: sorted_valid_neighbor_IDs.append(node)
# if current node does have valid neighbors, add them to the front of togo list
# in a sorted way
togo[current_node_ID] = sorted_valid_neighbor_IDs
# To display a solution simply
def drawGUI(size, solution):
# GUI Code (If you can call it a GUI, though)
import Tkinter
root = Tkinter.Tk()
canvas = Tkinter.Canvas(root, width=size*20, height=size*20)
#canvas.create_rectangle(0, 0, size*20, size*20)
canvas.pack()
for x in range(0, size*20, 20):
canvas.create_line(x, 0, x, size*20)
canvas.create_line(0, x, size*20, x)
cnt = 1
for el in solution:
canvas.create_text((el % size)*20 + 4,(el / size)*20 + 4,text=str(cnt), anchor=Tkinter.NW)
cnt += 1
root.mainloop()
print('Start of run')
# it is the moment
solve(0, 10)
#Optional, to draw a returned solution
#drawGUI(10, solve(0, 10))
raw_input('End of Run...')
Thanks to all everybody sharing their knowledge and ideas.