Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>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.<br> 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".</p> <p>First, things I have learned: </p> <ol> <li><p>Thanks to <a href="https://stackoverflow.com/questions/767912/riddle-the-square-puzzle/767984#767984">Dave Webb's answer</a> and <a href="https://stackoverflow.com/questions/767912/riddle-the-square-puzzle/767991#767991">ammoQ's answer</a>. 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 <a href="http://en.wikipedia.org/wiki/Knight%27s_tour" rel="nofollow noreferrer">Knight's Tour</a> 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.</p></li> <li><p>Thanks to <a href="https://stackoverflow.com/questions/767912/riddle-the-square-puzzle/769302#769302">Joe's answer</a>. 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.</p></li> </ol> <p>Upon exhaustive brute-force search, here are key points I have developed on the code:</p> <ul> <li><p><a href="http://en.wikipedia.org/wiki/Knight%27s_tour#Warnsdorff.27s_algorithm" rel="nofollow noreferrer">Warnsdorff's algorithm</a>: 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.</p> <p>Below is the pseudocode (from Wikipedia):</p></li> </ul> <hr> <p>Some definitions:</p> <ul> <li>A position Q is accessible from a position P if P can move to Q by a single knight's move, and Q has not yet been visited.</li> <li>The accessibility of a position P is the number of positions accessible from P.</li> </ul> <p>Algorithm:</p> <blockquote> <p>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.</p> </blockquote> <hr> <ul> <li><a href="https://stackoverflow.com/questions/767912/riddle-the-square-puzzle/768497#768497">Checking for islands</a>: A nice exploit of domain knowledge here proved to be handy. If a move (unless it is the last one) would cause <em>any</em> of its neighbors to become an island, i.e. not accessible by any other, then that branch is no longer investigated. Saves considerable amount of time (very roughly 25%) combined with Warnsdorff's algorithm.</li> </ul> <p>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).</p> <pre><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&lt;=posx&lt;self.base and 0&lt;=posy&lt;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 =&gt; bottom left # (base-1) =&gt; bottom right # base*(base-1) =&gt; top left # base**2 -1 =&gt; 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...') </code></pre> <p>Thanks to all everybody sharing their knowledge and ideas.</p>
    singulars
    1. This table or related slice is empty.
    1. PORiddle: The Square Puzzle
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USrpr
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PORiddle: The Square Puzzle
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload