Number of tours through m x n grid?

问题:

Let T(x,y) be the number of tours over a X × Y grid such that:

1. the tour starts in the top left square
2. the tour consists of moves that are up, down, left, or right one square,
3. the tour visits each square exactly once, and
4. the tour ends in the bottom left square.

It’s easy to see, for example, that T(2,2) = 1, T(3,3) = 2, T(4,3) = 0, and T(3,4) = 4. Write a program to calculate T(10,4).

• I have been working on this for hours ... I need a program that takes the dimensions of the grid as input and returns the number of possible tours? Any idea on how I should go about solving this?

回答1:

Since you're new to backtracking, this might give you an idea how you could solve this:

You need some data structure to represent the state of the cells on the grid (visited/not visited).

Your algorithm:

step(posx, posy, steps_left)
    if it is not a valid position, or already visited
        return
    if it's the last step and you are at the target cell
        you've found a solution, increment counter
        return
    mark cell as visited             
    for each possible direction:
       step(posx_next, posy_next, steps_left-1)
    mark cell as not visited

and run with

step(0, 0, sizex*sizey)

The basic building blocks of backtracking are: evaluation of the current state, marking, the recursive step and the unmarking.

This will work fine for small boards. The real fun starts with larger boards where you have to cut branches on the tree which aren't solvable (eg: there's an unreachable area of not visited cells).

回答2:

The assigned exercise is a good one. It forces you to think through several concepts, step-by-step. I cannot think all the concepts through for you, but maybe I can help by asking the following question.

At some point, your program must represent a partially completed tour. That is, it must represent a path which does not yet pass through all the squares and has not yet reached its target in the bottom left, but which might do both if the path were later extended. How do you mean to represent a partially completed tour?

If you can answer the question, and if you grasp the concept of recursion, then one suspects that you can solve the problem with some work but without too much real trouble. To represent the partially completed tour is your obstacle, so my recommendation is that you go to work on that.

Update: See the comment of @KarolyHorvath below. If you have not yet learned the use of dynamically allocated memory (or, equivalently, of STL containers like std::vector and std::list), then you should rather follow his hint, which is a good hint in any case.