The following information was submitted:
Transactions: WSEAS TRANSACTIONS ON MATHEMATICS
Transactions ID Number: 31-324
Full Name: Hsien-lun Wong
Position: Associate Professor
Age: ON
Sex: Male
Address: No1 Hsin-Hsing Road, HsinFong, HsinChu, TAIWAN
Country: TAIWAN
Tel: 886-3-5593142 ext3522
Tel prefix:
Fax: 886-3-5593142 ext 3503
E-mail address: alan@mail.must.edu.tw
Other E-mails: alan.an0624@msa.hinet.net
Title of the Paper: Applications of Assignment Models for Solving Sudoku Puzzles
Authors as they appear in the Paper: Hsien-lun wong, Shang-hsing Hsieh
Email addresses of all the authors: alan@mail.must.edu.tw, shhsieh@cc.nctu.edu.tw
Number of paper pages: 10
Abstract: The Sudoku puzzle is in nature a mathematical problem. This paper proposes two optimization programs for finding the solution to any Soduku puzzle. One is a Mixed Integer Programming (MIP) model, in which a technique is presented for setting up functional constraints in LP when two variables are required not equal. However, we need additional 36¡Ñ9¡Ñ2¡Ñ3 = 1,944 constraints and 972 indicator variables for this purpose, which make it very hard to solve this MIP model. The other is formulated as a multi-job assignment model. Before setting up the model, the paper indicates each kind of job (e.g., digit in Sudoku) by using different letter. Although there are several groups of decision variables, the number of decision variables and constraints can be greatly reduced to 729 and 324, respectively. This model is in nature a Binary Integer Programming (BIP) model. Any Sudoku puzzle can be formulated in the BIP model and can be solved within 2 seconds by computer software!
(e.g., LINGO 6.0) in a common personal computer with a Pentium III CPU. An illustrative example is also presented in the paper.
Keywords: Sudoku; Mixed Integer Programming; Binary Integer Programming; Optimization Assignment Model
EXTENSION of the file: .ps
Special (Invited) Session: invited paper (by wseas.headquarters@gmail.com)
Organizer of the Session: invited paper (by wseas.headquarters@gmail.com)
How Did you learn about congress: No1 Hsin-Hsing Road, HsinFong, HsinChu, TAIWAN. University library, Minghsin University of Science and Technology
IP ADDRESS: 210.240.222.28
