Riddle: The Square Puzzle

Question

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:

1. Capture and exploit domain knowledge specific to this problem

2. 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".

---

Answer 1

You could count the number of solutions exactly with a sweep-line dynamic programming algorithm.

Answer 2

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:

1. 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.

2. 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:

• 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.
• The accessibility of a position P is the number of positions accessible from P.

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.

---

• Checking for islands: A nice exploit of domain knowledge here proved to be handy. If a move (unless it is the last one) would cause any 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.

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.

Answer 3

I wanted to see if I could write a program that would come up with all possible solutions.

#! /usr/bin/env perl
use Modern::Perl;

{
  package Grid;
  use Scalar::Util qw'reftype';

  sub new{
    my($class,$width,$height) = @_;
    $width  ||= 10;
    $height ||= $width;

    my $self = bless [], $class;

    for( my $x = 0; $x < $width; $x++ ){
      for( my $y = 0; $y < $height; $y++ ){
        $self->[$x][$y] = undef;
      }
    }

    for( my $x = 0; $x < $width; $x++ ){
      for( my $y = 0; $y < $height; $y++ ){
        $self->[$x][$y] = Grid::Elem->new($self,$x,$y);;
      }
    }

    return $self;
  }

  sub elem{
    my($self,$x,$y) = @_;
    no warnings 'uninitialized';
    if( @_ == 2 and reftype($x) eq 'ARRAY' ){
      ($x,$y) = (@$x);
    }
    die "Attempted to use undefined var" unless defined $x and defined $y;
    my $return = $self->[$x][$y];
    die unless $return;
    return $return;
  }

  sub done{
    my($self) = @_;
    for my $col (@$self){
      for my $item (@$col){
        return 0 unless $item->visit(undef);
      }
    }
    return 1;
  }

  sub reset{
    my($self) = @_;
    for my $col (@$self){
      for my $item (@$col){
        $item->reset;
      }
    }
  }

  sub width{
    my($self) = @_;
    return scalar @$self;
  }

  sub height{
    my($self) = @_;
    return scalar @{$self->[0]};
  }
}{
  package Grid::Elem;
  use Scalar::Util 'weaken';

  use overload qw(
    "" stringify
    eq equal
    == equal
  );

  my %dir = (
    #       x, y
    n  => [ 0, 2],
    s  => [ 0,-2],
    e  => [ 2, 0],
    w  => [-2, 0],

    ne => [ 1, 1],
    nw => [-1, 1],

    se => [ 1,-1],
    sw => [-1,-1],
  );

  sub new{
    my($class,$parent,$x,$y) = @_;
    weaken $parent;
    my $self = bless {
      parent => $parent,
      pos    => [$x,$y]
    }, $class;

    $self->_init_possible;

    return $self;
  }

  sub _init_possible{
    my($self) = @_;
    my $parent = $self->parent;
    my $width  = $parent->width;
    my $height = $parent->height;
    my($x,$y)  = $self->pos;

    my @return;
    for my $dir ( keys %dir ){
      my($xd,$yd) = @{$dir{$dir}};
      my $x = $x + $xd;
      my $y = $y + $yd;

      next if $y < 0 or $height <= $y;
      next if $x < 0 or $width  <= $x;

      push @return, $dir;
      $self->{$dir} = [$x,$y];
    }
    return  @return if wantarray;
    return \@return;
  }

  sub list_possible{
    my($self) = @_;
    return unless defined wantarray;

    # only return keys which are
    my @return = grep {
      $dir{$_} and defined $self->{$_}
    } keys %$self;

    return  @return if wantarray;
    return \@return;
  }

  sub parent{
    my($self) = @_;
    return $self->{parent};
  }

  sub pos{
    my($self) = @_;
    my @pos = @{$self->{pos}};
    return @pos if wantarray;
    return \@pos;
  }

  sub visit{
    my($self,$v) = @_;
    my $return = $self->{visit} || 0;

    $v = 1 if @_ == 1;
    $self->{visit} = $v?1:0 if defined $v;

    return $return;
  }

  sub all_neighbors{
    my($self) = @_;
    return $self->neighbor( $self->list_possible );
  }
  sub neighbor{
    my($self,@n) = @_;
    return unless defined wantarray;
    return unless @n;

    @n = map { exists $dir{$_} ? $_ : undef } @n;

    my $parent = $self->parent;

    my @return = map {
      $parent->elem($self->{$_}) if defined $_
    } @n;

    if( @n == 1){
      my($return) = @return;
      #die unless defined $return;
      return $return;
    }
    return  @return if wantarray;
    return \@return;
  }

  BEGIN{
    for my $dir ( qw'n ne e se s sw w nw' ){
      no strict 'refs';
      *$dir = sub{
        my($self) = @_;
        my($return) = $self->neighbor($dir);
        die unless $return;
        return $return;
      }
    }
  }

  sub stringify{
    my($self) = @_;
    my($x,$y) = $self->pos;
    return "($x,$y)";
  }

  sub equal{
    my($l,$r) = @_;
    "$l" eq "$r";
  }

  sub reset{
    my($self) = @_;
    delete $self->{visit};
    return $self;
  }
}

# Main code block
{
  my $grid = Grid->new();

  my $start = $grid->elem(0,0);
  my $dest  = $grid->elem(-1,-1);

  my @all = solve($start,$dest);
  #say @$_ for @all;
  say STDERR scalar @all;
}

sub solve{
  my($current,$dest,$return,@stack) = @_;
  $return = [] unless $return;
  my %visit;
  $visit{$_} = 1 for @stack;

  die if $visit{$current};

  push @stack, $current->stringify;

  if( $dest == $current ){
    say @stack;

    push @$return, [@stack];
  }

  my @possible = $current->all_neighbors;
  @possible = grep{
    ! $visit{$_}
  } @possible;

  for my $next ( @possible ){
    solve($next,$dest,$return,@stack);
  }

  return @$return if wantarray;
  return  $return;
}

This program came up with more than 100,000 possible solutions before it was terminated. I sent STDOUT to a file, and it was more than 200 MB.

Answer 4

I decided to look at the problem and see if I could break it into 5x5 solutions with the ending of a solution one jump away from the corner of another.

First assumption was that 5x5 is solvable. It is and fast.

So I ran solve(0,5) and looked at the results. I drew a 10x10 numbered grid in Excel with a 5x5 numbered grid for translation. Then I just searched the results for #] (ending cells) that would be a jump away from the start of the next 5x5. (ex. for the first square, I searched for "13]".)

For reference:

10 x 10 grid                       5 x 5 grid 
 0  1  2  3  4 |  5  6  7  8  9     0  1  2  3  4
10 11 12 13 14 | 15 16 17 18 19     5  6  7  8  9
20 21 22 23 24 | 25 26 27 28 29    10 11 12 13 14
30 31 32 33 34 | 35 36 37 38 39    15 16 17 18 19
40 41 42 43 44 | 45 46 47 48 49    20 21 22 23 24
---------------+---------------
50 51 52 53 54 | 55 56 57 58 59
60 61 62 63 64 | 65 66 67 68 69
70 71 72 73 74 | 75 76 77 78 79
80 81 82 83 84 | 85 86 87 88 89
90 91 92 93 94 | 95 96 97 98 99

Here is a possible solution:

First square: [0, 15, 7, 19, 16, 1, 4, 12, 20, 23, 8, 5, 17, 2, 10, 22, 14, 11, 3, 18, 6, 9, 24, 21, 13] puts it a diagonal jump up to 5 (in 10x10) the first corner of the next 5 x 5.

Second Square: [0, 12, 24, 21, 6, 9, 17, 2, 14, 22, 7, 15, 18, 3, 11, 23, 20, 5, 8, 16, 19, 4, 1, 13, 10] puts it with last square of 25 in the 10x10, which is two jumps away from 55.

Third Square: [0, 12, 24, 21, 6, 9, 17, 5, 20, 23, 8, 16, 19, 4, 1, 13, 10, 2, 14, 11, 3, 18, 15, 7, 22] puts it with last square of 97 in the 10x10, which is two jumps away from 94.

Fourth Square can be any valid solution, because end point doesn't matter. However, the mapping of the solution from 5x5 to 10x10 is harder, as the square is starting on the opposite corner. Instead of translating, ran solve(24,5) and picked one at random: [24, 9, 6, 21, 13, 10, 2, 17, 5, 20, 23, 8, 16, 1, 4, 12, 0, 15, 18, 3, 11, 14, 22, 7, 19]

This should be possible to all do programatically, now that 5x5 solutions are know to be valid with endpoints legal moves to the next 5x5 corner. Number of 5x5 solutions was 552, which means storing the solutions for further calculation and remapping is pretty easy.

Unless I did this wrong, this gives you one possible solution (defined above 5x5 solutions as one through four respectively):

def trans5(i, col5, row5):
    if i < 5: return 5 * col5 + 50 * row5 + i
    if i < 10: return 5 + 5 * col5 + 50 * row5 + i
    if i < 15: return 10 + 5 * col5 + 50 * row5 + i
    if i < 20: return 15 + 5 * col5 + 50 * row5 + i
    if i < 25: return 20 + 5 * col5 + 50 * row5 + i

>>> [trans5(i, 0, 0) for i in one] + [trans5(i, 1, 0) for i in two] + [trans5(i, 0, 1) for i in three] + [trans5(i, 1, 1) for i in four]
    [0, 30, 12, 34, 31, 1, 4, 22, 40, 43, 13, 10, 32, 2, 20, 42, 24, 21, 3, 33, 11, 14, 44, 41, 23, 5, 27, 49, 46, 16, 19, 37, 7, 29, 47, 17, 35, 38, 8, 26, 48, 45, 15, 18, 36, 39, 9, 6, 28, 25, 50, 72, 94, 91, 61, 64, 82, 60, 90, 93, 63, 81, 84, 54, 51, 73, 70, 52, 74, 71, 53, 83, 80, 62, 92, 99, 69, 66, 96, 78, 75, 57, 87, 65, 95, 98, 68, 86, 56, 59, 77, 55, 85, 88, 58, 76, 79, 97, 67, 89]

Can some one double check the methodology? I think this is a valid solution and method of breaking up the problem.

Answer 5

An optimization can me made to check for islands (i.e. non-visited spaces with no valid neighbors.) and back out of the traverse until the island is eliminated. This would occur near the "cheap" side of a certain tree traverse. I guess the question is if the reduction is worth the expense.

Answer 6

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".

The key optimisation I remember from tackling the Knights Tour recursively is take your next moves in increasing order of the number of available moves on the destination square. This encourages the search to try and move densely in one area and filling it rather than zooming all over the board and leaving little island squares that can never be visited. (This is Warnsdorff's algorithm.)

Also make sure you have considered symmetry where you can. For example, at the simplest level the x and y of your starting square only need to go up to 5 since (10,10) is the same as (1,1) with the board rotated.

Answer 7

This is just an example of the http://en.wikipedia.org/wiki/Hamiltonian_path problem. German wikipedia claims that it is NP-hard.