Knight's tour

March 15, 2018

Introduction

It is very classical dynamic programming called Knight's tour. The problem statement is here on stackoverflow.com.

The most important thing is to know that we only need to count the number of phone numbers, but we do not need to know what numbers for each phone number. The second tip is to know that there are 10 numbers for each step at most.

Algorithm practice

Here is my C# algorithm.

My problem is that it takes me too long to come out the idea and write a solution. I need to make it fit into 20 minutes, 6 to 8 minutes to come out the idea, and I should be able to write the algorithm in less than 10 minutes.

Thinking process

We all know that most important is thinking process. Of course I had long thinking process this time. I drew something on paper, and I took time to think and play with the example.

What I like to do it to make some presentable notes here and document my thinking process. Good thinking process is the gold, the coding part is easy specially for dynamic programming algorithm.

1   2    3

4   5    6

7   8    9

    0

We can tell that 1 can reach 6 and 8. Please check next row and then next column. we denote that knights[1] = new int[]{6, 8}.
Same applies to each number in the first row, next row.

One thing I have to pay attention is number 6, there are 3 numbers to reach, row above, row below, column before, knights[6] = new int[]{0, 1, 7}.

Let us call it first play.

Next play is to work on a graph using those numbers as node, and then connections as edges. It is directed graph as well. Originally in my practice, my drawing is kind of messy. In the following, I try to simplify and make the drawing more readable.

For example, knights[1] = new int[]{6, 8}, I will draw like the following:


0   1    2    3    4   5     6    7    8    9

     ----------------------->

    ------------------------------->


And then we need to add knights[0] = new int[] { 4, 6},

0   1    2     3      4     5    6    7    8    9

------------------->

------------------------------>

We can use depth first search, but time complexity is too high using depth first search. We do not care the path detail. There are so many paths, all we care about the total number of paths.

Once I decide to use a table to store all intermediate result. I have ideas to solve the problem using polynomial time.

Suppose that we start from number 1, and then go over 4 steps and see how many results we can generate.


3              1       3    4     2
2    2   1       1            1
1    0   0   0  0  0 0  1 0  1   0
0    0   1   0  0  0 0  0 0  0   0
-------------------------------------------------
     0   1   2  3  4 5  6  7  8   9