  We propose an improved algorithm for counting the number of Hamiltonian
cycles in a directed graph. The basic idea of the method is sequential
acceptance/rejection, which is successfully used in approximating the number of
perfect matchings in dense bipartite graphs. As a consequence, a new bound on
the number of Hamiltonian cycles in a directed graph is proved, by using the
ratio of the number of 1-factors. Based on this bound, we prove that our
algorithm runs in expected time of $O(n^{8.5})$ for dense problems. This
improves the Markov chain method, the most powerful existing method, a factor
of at least $n^{4.5}(\log n)^{4}$ in running time. This class of dense problems
is shown to be nontrivial in counting, in the sense that it is $#$P-Complete.
