Browsing by Author "Chen, Lung-Ping"

Now showing 1 - 3 of 3

An Efficient Approach to Solving Nonograms
(2013-09-01)
Wu, I-Chen
;
Sun, Der-Johng
;
Chen, Lung-Ping
;
Chen, Kan-Yueh
;
Kuo, Ching-Hua
A nonogram puzzle is played on a rectangular grid of pixels with clues given in the form of row and column constraints. The aim of solving a nonogram puzzle, an NP-complete problem, is to paint all the pixels of the grid in black and white while satisfying these constraints. This paper proposes an efficient approach to solving nonogram puzzles. We propose a fast dynamic programming (DP) method for line solving, whose time complexity in the worst case O(kl) is only, where the grid size l x l is and k is the average number of integers in one constraint, always smaller than. In contrast, the time complexity for the best line-solving method in the past is O(kl(2)). We also propose some fully probing (FP) methods to solve more pixels before running backtracking. Our FP methods can solve more pixels than the method proposed by Batenburg and Kosters (before backtracking), while having a time complexity that is smaller than theirs by a factor of O(l). Most importantly, these FP methods provide useful guidance in choosing the next promising pixel to guess during backtracking. The proposed methods are incorporated into a fast nonogram solver, named LalaFrogKK. The program outperformed all the programs collected in webpbn.com, and also won both nonogram tournaments that were held at the 2011 Conference on Technologies and Applications of Artificial Intelligence (TAAI 2011, Taiwan). We expect that the proposed FP methods can also be applied to solving other puzzles efficiently.
On the Efficiency of Executing Diverse Game Tree Search Applications in a Volunteer Computing Federation
(2013-01-01)
Chen, Lung-Ping
;
Wu, I-Chen
;
Chang, Yuan-Yao
;
Tseng, Wen-Jie
;
資訊工程學系
A game tree search application can be implemented as the malleable parallel jobs that are adapted to various processor allocations. We establish an efficient desktop grid federation to enable the small to mid-sized organizations to perform large-scale game tree search tasks via resource sharing. Due to the uneven task scales of the organizations as well as the dynamic generation/pruning of game tree search tasks, the user credits of the desktop grids may fluctuate dramatically, leading an unstable resource allocation to the hosted applications. This paper shows that stable processor allocation leads to higher efficiency for the parallel tasks. A new brokering algorithm is developed that ensures both fairness and stable resource allocation.
TCGA 2013 COMPUTER GAME TOURNAMENT REPORT
(2013-09-01)
Tseng, Wen-Jie
;
Chen, Jr-Chang
;
Chen, Lung-Ping
;
Yen, Shi-Jim
;
Wu, I-Chen