Scholarlink

In Chess, the Knight is the only piece with unique movements. It can jump over the other chess pieces and it can move two squares horizontally and a vertical square or two squares. The Knight’s tour problem is one of the classic problems in the field of Graph theory. It is solved based on the Hamiltonian cycle problem, finding such cycle in the chessboard is known as Knight’s Tour. The objective is to find the path so that the Knight visits every square of the chessboard exactly once. This problem, when solved using backtracking works incrementally. The time complexity of the Knight’s tour is O (8^(N^2)) Thus parallelization of Knight’s tour for 8*8 chessboard is done using the parallelizing techniques OpenMP, MPI and CUDA. So that the worst running time of the algorithm can be speed up to a certain extent.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Parallelization of Knight’s Tour Using Naive Algorithm

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • R. Manimegalai,
  • S. Lokesh,
  • S. Krishnadharani

摘要

In Chess, the Knight is the only piece with unique movements. It can jump over the other chess pieces and it can move two squares horizontally and a vertical square or two squares. The Knight’s tour problem is one of the classic problems in the field of Graph theory. It is solved based on the Hamiltonian cycle problem, finding such cycle in the chessboard is known as Knight’s Tour. The objective is to find the path so that the Knight visits every square of the chessboard exactly once. This problem, when solved using backtracking works incrementally. The time complexity of the Knight’s tour is O (8^(N^2)) Thus parallelization of Knight’s tour for 8*8 chessboard is done using the parallelizing techniques OpenMP, MPI and CUDA. So that the worst running time of the algorithm can be speed up to a certain extent.