The Search for Systems of Diagonal Latin Squares Using the SAT@home Project

Oleg Zaikin, Stepan Kochemazov

Abstract


In this paper we consider the approach to solving the problem of search for systems of diagonal orthogonal Latin squares in the form of the Boolean Satisfiability problem. We describe two different propositional encodings that we use. The first encoding is constructed for finding pairs of orthogonal diagonal Latin squares of order 10. Using this encoding we managed to find 17 previously unknown pairs of such squares using  the volunteer computing project SAT@home. The second encoding is constructed for finding pseudotriples of orthogonal diagonal Latin squares of order 10. Using the pairs found with the help of SAT@home and the second encoding we successfully constructed several new pseudotriples of diagonal Latin squares of order 10.

Full Text:

PDF

References


C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Designs, 2nd ed. (Discrete Mathematics and Its Applications). Chapman & Hall/CRC. 2006.

C. W. H. Lam, L. Thiel, and S. Swiercz, “The non-existence of finite projective planes of order 10,” Canad. J. Math., vol. 41, pp. 1117-1123, 1989.

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, North Holland Publishing Co, 1988.

G. McGuire, B. Tugemann and G. Civario, “There is no 16-clue Sudoku: solving the Sudoku minimum number of clues problem via hitting set enumeration,” Experimental Mathematics, vol. 23, no. 2, pp. 190–217, 2014.

B. D. Mckay, A. Meynert and W. Myrvold, “Small Latin squares, quasigroups and loops,” J. Combin. Designs, vol. 15(2), pp. 98–119, 2007.

H. Zhang, “Combinatorial Designs by SAT Solvers,”. in: Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press, 2009.

Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press, 2009.

M. A. Posypkin, A. A. Semenov and O. S. Zaikin, “Using BOINC desktop grid to solve large scale SAT problems,” Computer Science Journal, vol. 13, no. 1, pp. 25–34, 2012.

J. Egan and I. M. Wanless, “Enumeration of MOLS of small order,” CoRR abs/1406.3681v2.

Brown et al, “Completion of the spectrum of orthogonal diagonal Latin squares,” Lect. Notes Pure Appl. Math., vol. 139, pp. 43–49 (1993)

S. D. Prestwich, “CNF encodings,” in: Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press, 2009, pp. 75–97.

I. Lynce and J. Ouaknine, “Sudoku as a SAT problem,” in: Proc. Ninth International Symposium on Artificial Intelligence and Mathematics, Fort Lauderdale, FL., 2006.

K. E. Batcher, “Sorting networks and their applications,” in Proc. of Spring Joint Computer Conference, New York, USA, 1968, pp. 307–314.

M. Nouman Durrani and J. A. Shamsi, “Review: Volunteer computing: Requirements, challenges, and solutions,” J. Netw. Comput. Appl., vol. 39, pp. 369–380, 2014.

D. P. Anderson and G. Fedak, “The computational and storage potential of volunteer computing,” in 6th IEEE International Symposium on Cluster Computing and the Grid, Singapore, 2006, pp. 73–80.

N. E´en and N. S¨orensson, “An extensible SAT-solver,” in 6th International Conference on Theory and Applications of Satisfiability Testing, Santa Margherita Ligure, Italy, 2003, pp. 502–518.

A. P. Afanasiev, I. V. Bychkov, M. O. Manzyuk, M. A. Posypkin, A. A. Semenov and O. S. Zaikin, “Technology for Integrating Idle Computing Cluster Resources into Volunteer Computing Projects,” in Proc. of The 5th International Workshop on Computer Science and Engineering, Moscow, Russia, 2015, pp. 109-114.

A. Biere, “Lingeling essentials, A tutorial on design and implementation aspects of the the SAT solver lingeling,” in Proc. Fifth Pragmatics of SAT workshop, Vienna, Austria, 2014, p. 88.

Y. Evtushenko, M. Posypkin and I. Sigal. “A framework for parallel large-scale global optimization,”. Computer Science - Research and Development, vol. 23(3-4), pp. 211-215, 2009.

[A. Semenov, O. Zaikin, D. Bespalov and M. Posypkin, “Parallel Logical Cryptanalysis of the Generator A5/1 in BNB-Grid System,” in Parallel Computational Technologies, Kazan, Russia, 2011, pp. 473–483.

M. Black and G. Bard, “SAT Over BOINC: An Application-Independent Volunteer Grid Project,” in 12th IEEE/ACM International Conference on Grid Computing, Lyon, France, 2011, pp. 226–227.

H.-H. Lin and I-C. Wu, “An Efficient Approach to Solving the Minimum Sudoku Problem,” in. Proc. International Conference on Technologies and Applications of Artificial Intelligence, Hsinchu, Taiwan. 2010, pp. 456–461.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162