howeversome algorithms have big values that are so large that they can be used only for relatively small values of many real-world problems that require such algorithms simply cannot be solved in reasonable length of time such problems are said to be intractable (another term used for such problems is np completewhere np means non-deterministic polynomial an explanation of what this means is beyond the scope of this book the knight' tour the knight' tour (programming project in is an example of an intractable problem because the number of possible moves is so large the total number of possible move sequences is difficult to calculatebut we can approximate it each move can end on maximum of eight squares this number is reduced by moves that would be off the edge of the board and moves that would end on square that was already visited in the early stages of tourthere will be closer to eight movesbut this number will gradually decrease as the board fills up let' assume (conservativelyan average of only two possible moves from each position after the initial squarethe knight can visit more squares thusthere is total of possible moves this is about assume computer can make million moves second ( there are roughly seconds in yearso the computer can make moves in year solving the puzzle by brute force can therefore be expected to take or around million years this particular problem can be made more tractable if strategies are used to "prunethe game tree one is warnsdorff' heuristic ( von warnsdorff )which specifies that you always move to the square that has the fewest possible exit moves the traveling salesman problem here' another famous intractable problem suppose you're salesperson and you need to drive to all the cities where you have clients you would like to minimize the number of miles you travel you know the distance from each city to every other city you want to start in your home cityvisit each client city once and only onceand return to your home city in what sequence should you visit these cities to minimize the total miles traveledin graph theory this is called the traveling salesman problemoften abbreviated tsp figure shows an arrangement of cities and distances what' the shortest way to travel from through each of the other cities and back to anotice that it' not necessary that every pair of cities be connected by an edge because of geography it may be impossible to drive from washingtond to new york without going through philadelphiafor example