A novel sudoku solving method based on sparse optimization
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

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

    In order to solve the sudoku more efficiently,a novel approach was proposed.We employed the realnumber coding to get rid of the integer constraint,meanwhile used the L0norm to guarantee the sparsity of the solution.Moreover,the L1norm was used to approximate the L0norm on the basis of RIP and KGG condition.Finally,the slack vectors were introduced to transfer the L1norm into a convex linear programming problem,which was solved by the primaldual interior point method.Experiments demonstrate that this algorithm reach 100% success rate on easy,medium,difficult,and evil levels,and reach 864% success rate on only 17clue sudokus.Besides,the average computation time is quite short,and has nothing to do with the difficulty of sudoku itself.In all,this algorithm is superior to both constraint programming and Sinkhorn algorithm in terms of success rate and computation time.

    Reference
    Related
    Cited by
Get Citation

ZHANGYudong, WANG Shuihua,HUO Yuankai,WU Lenan. A novel sudoku solving method based on sparse optimization[J]. Journal of Nanjing University of Information Science & Technology,2011,(1):23-27

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 20,2010
  • Revised:
  • Adopted:
  • Online:
  • Published:

Address:No. 219, Ningliu Road, Nanjing, Jiangsu Province

Postcode:210044

Phone:025-58731025