n-Queen Solution Finder
n-Queen Problem
Program Result
The objective of the assignment was finding the largest number of n-queen problem solution. The mark was given by in-class competition. I found a solution for 40,000,000 queens. I tried to solve the problem using such as stimulated annealing and polynomial time algorithm. My solution was ranked on the third place. The trick that I used was placing queens in the semi-diagonal position (adjacent row & one column between two queens) at the first place. This initialization drastically decrease the number of conflicts of queens at the initial position compared to the random initialization method.
References
- A Polynomial Time Algorithm for the N-Queen Problem, Rok Sosic and Jun Gu, SIGART Vol 1, 3, pp 7-11, Oct, 1990
- 3,000,000 Queens in Less Than One Minute, Rok Sosic and Jun Gu, SIGART Vol 2, 2, pp 22-24, Apr, 1991
- Comparison of Heuristic Algorithms for the N-Queen Problem, Ivica Martinjak and Marin Golub, Proceedings of the ITI 2007 29th Int. Conf. on Information Technology Interfaces, June 25-28, 2007
Naught and Cross Game
Program Result
Naught and Cross Game (also called “Omok” (Korean) or “Gomoku” (Japanese)) is very popular to people in the Asian countries. It is the extended version of Tic-Tac-Toe game.
The board has a grid of 15*15 squares, where two players (Naught and Cross players) could play on. The players will make a move in turn. The ‘Naught’ player will put “O” to an empty square as his move, while the ‘Cross’ player puts “X” for his move. Who ever reaches 5 pieces (X or O) in a row (vertically, horizontally, or diagonally) first will win. If after 15*15 squares are filled in and no one wined then the game is draw.
The objective of the assingment was making AI for the game. The mark was given by in-class league competition. My program took the first place at the tournament.
References
- Go-Moku and Threat-Space Search, L.V. Allis, H.J. van den Herik and M.P.H. Huntjens
- Df-pn: Depth-first Proof Number Search, Ayumu Nagai and Akihiro Kishimoto
