Sieve Algorithm to N Queens Problem
DOI:
CSTR:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    So far, there have been many different algorithm of eight queens problem. A similar sieve algorithm is presented in this paper: Using a algorithm similar to the sieve method in number theory: place the first queen in the first grid of the first row, and mark out the row, the column, the downward diagonal and the upward diagonal through the first queen;then place the second queen on the most left grid of the unmarked grid of the second row, and mark out the row, the column, the downward diagonal and the upward diagonal through the second queen;like this, queens are added, one by one. if all the queens can be placed on the board, a layout or a solution received. Traversing all grids of all row, we would get all solutions of N-queens problem. Based on the simple idea, we can develop a N-queens program easily. The experimental results show that the efficiency of the sieve program is much higher than the classic backtracking program.

    Reference
    Related
    Cited by
Get Citation

程元斌.类似筛法的N皇后问题求解算法.计算机系统应用,2013,22(10):147-150

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:April 03,2013
  • Revised:May 13,2013
  • Adopted:
  • Online: October 18,2013
  • Published:
Article QR Code
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-3
Address:4# South Fourth Street, Zhongguancun,Haidian, Beijing,Postal Code:100190
Phone:010-62661041 Fax: Email:csa (a) iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063