n- Queen Problem

  • 09 Mar 2021
  • Recently published Research - Mathematics

Researchers

Mohamad Abo-Safi & Shawki Al Rashed

Published in

Damascus University Journal of Basic Sciences, Volume 37, Issue 1, 2021.


Abstract

The n-queen problem is one of the problems that can be solved using mathematical concepts, (where   n ≥ 4 is a positive integer), where there are many methods to solve this problem as backtracking search technique[2, 9] and using global parallel genetic algorithm[3] and dynamic programming[10] and using DFS and BFS algorithms[12]. In this paper, we have studied some computation related to the chessboard, and we computed the number of squares associated and disassociated with square (i,j) on a chessboard of size n × n according to the queen's movement through the theorems (1),(2) and (3) and apply it by the implementation on example for a chessboard of size 10 × 10 , to represent this problem algebraically we used some concepts of computation in commutative algebra to solve the n-queen problem which are the concept of graded and the standard graded of rings, the Hilbert series of graded rings, the dimension and multiplicity of the ring, additionally to the concept of the combinatorial dimension of an affine algebras. We connected between queen's movement on the chessboard and the graph by the definition of the queen's graph and coloring it in special case. Using the computer algebra system SINGULAR [15], combinatorial dimension and we found the maximum number of queens can be placed on a chessboard so that no two of them attack one another in general case.

Keywords: Standard graded ring, Graded module, Hilbert series, Hilbert numerator polynomial (simplified), Dimension, Multiplicity, Combinatorial Dimension, Affine algebra, Queen graph.

Link to read full paper

http://damascusuniversity.edu.sy/mag/asasy/FCKBIH/file/1-2021/165-190.pdf