Self-Avoiding Walks of a Rook on a (M,N) Chessboard

Self-Avoiding Walks of a Rook
on an (M,N) Chessboard

By:

John L. Marcantonio+
Robert S. Goldstein
Jeff J. Denecke Jr.

Polytechnic University
Department of Computer Science
Farmingdale, New York 11735

as prepared for Professor Davis,
Instructor of Advanced Algorithms (CS 202)

Abstract

In this paper we will present a method to determine the number of self-avoiding walks a rook can take on an (m,n) size chessboard. The nature, runtime, and overall performance of this algorithm can be broken down into two fundamental components -- algebraically derived and algorithmiclly produced solutions. It will be shown that a recursive algorithm, although constrained to a large O(n), will reliablyproduce the desired results for any input*.

* - The phrase "any input" is bound directly to the in the
computational ability of the machine in which this algorithm is
being used. / + - J.L.M., R.S.G, and J.J.D. are currently seniors in the Dept. of C.S.--
contact at, ,

</div>

Table of Contents

0.0 The Test System...... 6
Abstract...... 8
1 Introduction...... 8
1.1 Background...... 8
1.2 The Problem...... 8
1.3 The Solution...... 9
2 The Algorithm...... 10
2.1 The Derivation of Constants...... 11
2.1.1 The Solution at N=1...... 11
2.1.2 The Solution at N=2...... 12
2.1.3 Recursion and the Solution at N=3...... 13
2.2 Derivation of the Unknown...... 15
2.2.1 Recursion and the Self-Avoiding Walk...... 15
3 Performance...... 15
3.1 O(N)...... 15
3.2 Improvements...... 17
3.2.1 Forking...... 17
3.2.2 Problems With Forking...... 19
3.3 An Alternative Implementation...... 19
3.3.1 The Port...... 19
3.3.2 The Code...... 20
4 Conclusions...... 20
4.1 Meeting the Objective...... 20
4.2 The Outcome...... 21
4.2.1 Results With C++...... 21
4.2.2 Results With Java...... 22
4.2.3 Linearity Within the Java Results...... 24
4.3 The Results of the Investigatory Process...... 25
4.3.1 Perspectives For Further Research Attempts...... 25
4.3.2 Suggestions For Further Work...... 25
4.4 Critique...... 26

</div>

Appendices

Appendix A
1.0 References...... 27
Appendix B
1.0 Source Code...... 28
1.0.1 Recursive Algorithm...... 28
1.0.2 Recursive Algorithm with Forking...... 32
1.0.3 Program Output...... 35
Appendix C
1.0 Result Tables...... 36
1.0 Result Tables - (M = N) Totals...... 36
1.1 Result Tables - (M x N) Totals...... 37
Appendix D
1.0 Algorithm Times...... 38
1.1 Result Tables - (M=N) Times...... 38
1.2 Result Tables - (MxN) Times (Elapsed)...... 38
1.3 Result Tables - (Time vs. SAWS)...... 39
Appendix E
1.0 Java Source - AboutBox Class...... 40
1.1 Java Source - IntTextField Class...... 41
1.2 Java Source - Rook Class...... 43
1.3 Java Source - Timing Class...... 47
1.4 HTML Source - The Applet Page...... 49
Appendix F
1.0 Algorithm Results - Java Implementation...... 51
1.1 (nxn) Runtime Results...... 51
1.2 (mxn) Runtime Results...... 52
1.3 Board Area vs. Completion Time...... 53

</div>

List of Equations, Diagrams, Tables, and Code Fragments

Equations
Equation (1)...... 10
Equation (2)...... 11
Equation (3)...... 11
Equation (4)...... 12
Equation (5)...... 12
Equation (6)...... 12
Diagrams
Diagram (1)...... 7
Diagram (2)...... 9
Diagram (3)...... 10
Diagram (4)...... 16
Tables
Table (1)...... 7
Table (2)...... 8
Table (3)...... 10
Table (4)...... 18
Table(4.1)...... 22
Table(4.2)...... 23
Table(4.3)...... 24
Code Fragment
Code Fragment (1)...... 14
Code Fragment (2)...... 14
Code Fragment (3) ...... 15

</div>

0.0 The Test System

For the purpose of this paper the algorithm was tested on a two machines, and all performance mentions in this paper are from those machines. The use of two machines are a direct result of the use of two distinct languages and execution environment. The computers used consists of the following components:

For the original series of algorithms that were devleloped in C++ the following equipment was used:

- AMD K62 - 350 MHZ.
- 64 MB. PC-100 RAM
- 4.3 GB. UDMA - 33 MB/sec Hard Drive
- Graphics, networking, and other options are standard equipment.

</div>

The operating system used was Red Hat Linux 6.0. The compiler used was the standard install of the GNU C/C++ compiler. When creating executables on the system NO code optimization was used -- including either processor specific compilation or optimization flags for the compiler. All executables were given top priority on the system and executed with super-user privileges. While the code was being executed on the system there were no other processes active. All input for the size of the chessboards were defined within the code and compiled as such. All output from the system was through STDIO to the screen -- no file access occurred.

Throughout this paper there are several references to the time it took for that particular algorithm to finish its task, displayed in the format of (Minutes):(Seconds).(Fractions of a Second). To determine this value the UNIX system call time was used on the command line in addition to the executable.

For the first algorithm all system calls and functions are ANSI C++ standard calls. These routines should compile and execute on any compiler that conforms to those standards. The second algorithm however uses UNIX specific calls from the following header files:

- <sys/types.h>
- <unistd.h>

</div>

These include files are used for the fork() function call and the pid_t variable type used to capture the process identification number of the newly spawned process and perform error checking accordingly.

For the second stage of the project it was required that we implement a version of the algorithm in the Java language, using the Java Virtual Machine as the platform in which performance tests were run. The hardware used to develop and test the Java version consisted of the following:

- Pentium II 400 Mhz.
- 128 MB RAM
- Standard UDMA and Networking Hardware

</div>

The execution and time testing of this algorithm was conducted on a base platform consisting of Microsoft Windows NT Version 4.0 Workstation, with a Java Virtual Machine conforming to the specifications set forth by Sun Microsystems in their release of JDK version 1.2. Compilation of the Java code and debugging were all done in this environment. To test the algorithms performance and aesthetic qualities the constructed applet was view from a web page using Netscape Communicator version 4.7.

Abstract

In this paper we will present a method to determine the number of self avoiding walks a rook can take on an (m,n) size chessboard. The nature, runtime, and overall performance of this algorithm can be broken down into two fundamental components -- algebraically derived and algorithmicly produced solutions. It will be shown that a recursive algorithm, although constrained to a large O(n), will reliablyproduce the desired results for any input*.

1 Introduction

1.1 Background

A self-avoiding walk (SAW) in a graph is a walk which starts at a fixed origin and passes through each vertex at most once[1]. Much work has been done in recent years to find a complete mathematical solution to this problem not only on the two dimensional plane, but higher ones as well. The research efforts to find this solution have been concentrated specifically on finding self-avoiding walks in d-dimensional rectangular lattices Zd [2]. The difficulty in this problem surprisingly enough does not originate in high level dimensions. For examples in which dis greater than 4 more is known about the behavior and solutions to this problem. Since the self-avoidance constraints in problems above the forth dimension become increasingly insignificant the behavior of those high dimensional SAWS begin to resemble simpler walks of the non-self-avoiding variety [2].

Unfortunately the problem that this paper addresses is not of a high order dimension. A two dimensional MxN chessboard is considered one of the more difficult problems to construct a unified theory around due to the difficultly of the self-avoidance constraint.

1.2 The Problem

What is a self-avoiding walk of a rook on an MxN chessboard? The problem itself is simple enough. An MxN two dimensional square lattice is the board in which we move our piece. The object is to move the rook from the lower left corner of the board to the upper right corner of the board without duplicating visits of any vertex. The only movement constraints placed upon the piece is that it must follow the movement rules set forth for a rook in the game of chess. Mainly, the piece can only move vertically and horizontally and is not limited in distance (although spanning multiple vertices of the board will be considered separate moves for the purposes of this paper).

* - The phrase "any input" is bound directly to the computational ability
of the machine in which this algorithm is being used.

</div>

1.3 The Solution

The following is an example of how the self-avoiding walk would work in this exercise. Below is a mapping of a (3,3) sized lattice. Filled in the different patterns are the various walks the rook can take to complete its path from one side of the board to the other. As illustrated below we can see that there are a total of 12 distinct ways in which the rook can complete this task.

Diagram (1): [1]

The image gives us an example of one method used to determine the number of SAWS the rook will take. It is possible, although extremely time consuming, to graphically represent and map every possible route the rook might take on its journey. Although this might seem like an easy and reliable method for finding a solution, as the number of vertices increase in size the complexity and total number of paths becomes extremely large. In fact, the number of possible SAWS increases so quickly the it becomes infeasible to use this for any practical application of this problem.

With the introduction and subsequent elimination of the graphical method for moderate to large values of M and N, the question then becomes what other methods can be used to arrive at a conclusion to this problem? To understand how quickly the solution values grow in this problem, below are two tables listing solution values for the number of SAWS on a given lattice.

Table 1 - [3-5]

m=n W(n,m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 / 1
2
12
184
8512
1262816
575780564
789360053252
3266598486981642
41044208702632496804
1568758030464750013214100
182413291514248049241470885236
64528039343270018963357185158482118
69450664761521361664274701548907358996488
227449714676812739631826459327989863387613323440

</div>

Table 2 - [3-5]

m/n 2 3 4 5 6 7

2 2

3 4 12

4 8 38 184

5 16 125 976 8512

6 32 414 5382 79384 1262816

7 64 1369 29739 752061 20562673 575780564

8 128 4522 163496 7110272 336067810 16230458696

9 256 14934 896476 67005561 549330332 549133264944

10 512 49322 913258 630588698 89803472792

11 1024 162899 26932712

12 2048 538020 147657866

13 4096 1776961

14 8192 5868904

Now that we have shown the solutions for a variety of (N,M) chessboards, the questions now becomes how did the authors, and by extension ourselves, arrive at these values.

2 The Algorithm

In any mathematical problem the easiest way to arrive at a solution is to find an equation and solve for the desired parameters. This problem is no exception to this rule. Rather than having to compute every single path it would be much easier to find a simple equation that would allow us to compute the answer for any given size chessboard without the computational overhead we would encounter with massive circuit analysis. This particular problem does have a few mathematical expression that will allow us to instantly derive the answers for certain sized boards. Unfortunately for the vast majority of cases there is no set formula that will allow us to easily find the solution for large board sizes.

2.1 The Derivation of Constants

The computational complexity with this problem is associated directly with the size of the chessboard. As the length and width increase, so do the number and possible walks and thus the number of calculations that must be performed to find a solution. To our dismay we find that the only computable solutions through equations are at very small size chessboards, in particular those at 1 and 2.

2.1.1 The Solution at N = 1

It can be shown rather easily that for N=1 there is at most 1 path for all values of M. This solution can be shown graphically for small values of M and expanded to include all M. Below are examples for M=1, M=2, M=3, and M=4 verifying this theory.

Diagram (2):

M=1

M=2

M=3

M=4

As we can see in the preceding examples since N=1 the problem in this particular instant has been transformed from a two dimensional rectangular lattice problem to a one dimensional path problem. The elimination of the second dimension in this case eliminates any variance from the path of the rook. Since the rook is limited to a straight path, and there is only one path in which the rook can follow to travel from the bottom left side of the board to the top right (in this case from the left side to the right), there is only one path the rook can travel for all M. As the length of the path increase it only increase the number of countable moves the rook has to take to reach the other side. For this case of the problem there need not be any computation at all, with the following rule holding true:

Equation (1):

For N=1, (M,N) = 1 ; For all M

2.1.2 The Solution at N = 2

The solution for all M at N=2, like that for N=1, can be found through an equation. For this, let us first examine an example of this for a (2,2) sized grid.

Diagram (3): [6]

The image above shows that for the smallest value two dimensional rectangular lattice there exists exactly 2 solutions to the problem. This value can be verified on Table 1 in Section 1.3. If we now take into account the solutions for all of the cases listed in Table 2, again from Section 1.3 of N=2, we begin to notice a pattern forming.

Table 3 - Selected Solution From Table 2 (Section 1.3): N=2

M = 1 2 3 4 5 6 7 8 9 10 11

Solution = 1 2 4 8 16 32 64 128 256 512 1024

(continued)

M = 12 13 14

Solution = 2048 4096 8192

If we examine the values from Table 3 we start to notice a pattern. As M increase, the solution to that particular self-avoiding walk increases according in a power of 2. Upon examining this more carefully we can derive the following formula to determine the number of self-avoiding walks a rook can take on a chessboard with N=2.

Equation (2):

For N=2, (M,N) = 2M-1 ; For all M>= 1

2.1.3 Recursion and the Solution at N = 3

Unlike its close relatives at N=2 and N=1, the solution to the case of N=3 is not as clear cut as we would like. Several expressions to find the value of N=3 have been investigated, primarily by H.L. Abbott and D. Hanson, who both came up with a recursive formula for finding the solutions for N=3.

Equation (3): [7-8]

W(1, 3) = 1, W(2, 3) = 4, W(3, 3) = 12, W(4, 3) = 38

W(M,3) = 4*W(M-1, 3) - 3*W(M-2, 3) + 2*W(M-3, 3) + W(M-4, 3)

For M >= 5

The expression in Equation (3) has been illustrated to produce a function-type formula of the following type:

Equation (4):

From this example it has been further demonstrated that there exists an exact algebraic formula of the following type:

Equation (5):

Where (i) denotes the imaginary unit.

From Equation (5) it has further been shown that there is a near approximation for large values of M given by the following:

Equation (6):

As we can see in this section, from Equations (3-6), that the complexity of determining the number of self-avoiding walks increases as well as the approximation with the incrementing of N beyond 2. It is for this reason that an algebraic solution can no longer be implemented and an algorithmic solution must be used to find the solution for larger cases of N.

2.2 The Derivation of the Unknown

This is where the real work to determine a solution is found, in the algorithm we are going to use. To find the quickest solution to any computational problem it makes sense to remove the already known constants. It is for this reason that we remove the computation of N=1 and N=2. Since these values can be computed independently and hold true for all the cases we will be examining, there is no need to compute them in the actual algorithm. The question then becomes how do we solve for the cases we don't know?

2.2.1 Recursion and the Self-Avoiding Walk

Section 2.1.3, Equation (3) showed us that H.L. Abbott and D. Hanson had decided to come up with a recursive algorithm to find the solution for N=3 within certain bounds. Their methods for finding a solution was hinged upon finding the solutions to smaller elements of the problem -- the point of recursion itself. Since recursion can be applied algebraically to certain instances of the problem, why can't it be applied to the problem as a whole?

The difficulty in finding a solution to this problem lies in the fact that every possible path must be examined to find an exact answer. In trying to find a method to span every possible move a rook can make on the board, recursion appears to be an ideal choice. The use of a recursive algorithm would allow the rook to traverse a given path, and then at each juncture it encounters spawn off another instances of that traversal recursively to examine the other options given it. This pattern would continue until the rook reaches the far corner of the board -- its final destination.

Although this algorithm appears simple, as do many recursive ones, the fact that this method does use recursion to arrive at a solution means that it is a very costly one.

3 Performance

With any algorithm of its kind the execution costs for finding a solution increase in the order of O(NX) as the search parameters increase. The O(N) for finding self-avoiding walks with a recursive method very quickly begins to cost an unreasonable amount of time.

3.1 O(N)

The algorithm implemented in this project carries with it two of the greatest consumers of clock cycles present in computing -- nested For loops with recursive calls. This is where the real consumption of processor time occurs. If we look into the source code (Appendix B) for our first algorithm we can find the nested recursive calls in the main() routine. A pseudocode representation of that code is as follows:

Code Fragment (1):

for (i=0 and < # of Columns, increment)

for (j=0 and < # of Rows, increment)

if (j >= 1)

traverse()

As we can see the O(N) of the For loops itself carries with it some expense. The real cost of the recursion occurs in the recursive call itself. Code fragments for that are as follows:

Code Fragment (2):

if (i != 0 & gmatrix[i-1][j] == 0) {

gmatrix[i][j] = 1;

traverse(c, r, i-1, j);

}

if (j != r & gmatrix[i][j+1] == 0) {

gmatrix[i][j] = 2;

traverse(c, r, i, j+1);

}

if (j != 0 & gmatrix[i][j-1] == 0) {

gmatrix[i][j] = 3;

traverse(c, r, i, j-1);

}

if (i != c & gmatrix[i+1][j] == 0) {

traverse(c, r, i+1, j);

}

Using this method the algorithm will continue to traverse in every direction it can until it arrives at the finishing point. Once that has occurred to a given path the algorithm will return from its call and try a different route it has not already done.