UNSUPERVISED MACHINE LEARNING ALGORITHM TO SOLVE KNIGHT COVERING PROBLEM FOR 6 BY 6 BOARD

Year 2021, , 414 - 426, 31.12.2021

Serkan Güldal

https://doi.org/10.54365/adyumbd.980660

Abstract

Modularity is a well-known method as a machine-learning algorithm to extract information from graphs. The modularity, in essence, divides the considered network into smaller clusters. The extracted clusters highlight the shared properties between the nodes in the same cluster. In the present study, we analyze the 6×6 knight graph by modularity method to obtain 6 Knight Covering Problem (6-KCP) solutions. Our investigation is ranged for the resolutions from 0.1 to 2.0. The maximum modularity score is 0.318 found for resolution 1.2. The resolutions, namely 0.3 and 0.4, identified all solutions, by 8 knights. Moreover, some solutions are obtained by 8 knights for the resolutions 0.2 and by 9, 10, 11, 12, 13 knights for the resolutions 0.2, 0.3, and 0.4. Moreover, resolution 0.3 is the most efficient resolution to find 6-KCP solutions. Also, within our analysis, resolution 0.2 is the best resolution to find more solutions, 195 solutions of 6-KCP. Lastly, the modularity method extracts the solutions from 61, for resolution 0.5, to 195, for resolution 0.2, out of 2253 solutions.

Keywords

Knight graph, modularity, Knight Covering Problem, Machine learning

6'YA 6 TAHTA ÜZERİNDE AT KAPLAMA PROBLEMİNİ ÇÖZMEK İÇİN DENETİMSİZ MAKİNE ÖĞRENME ALGORİTMASI

Abstract

Modülerlik, çizgelerden bilgi çıkarmak için, çok kullanılan bir makine öğrenimi algoritmasıdır. Modülerlik, özünde, ele alınan ağı daha küçük kümelere böler. Oluşturan kümeler, aynı kümedeki düğümler arasındaki paylaşılan özellikleri vurgular. Bu çalışmada 6×6 at çizgesini modülerlik yöntemiyle analiz ederek 6 At Kaplama Probleminin (6-AKP) çözümlerini elde ettik. Araştırmamız 0,1 ile 2,0 arasındaki çözünürlükler için değişmektedir. Çözünürlük 1,2 için bulunan maksimum modülerlik puanı 0,318'dir. 0,3 ve 0,4 olmak üzere çözünürlükler, tüm çözümleri 8 at ile tanımladı. Ayrıca, 0,2 çözünürlükler için 8 at ve 0,2, 0,3 ve 0,4 çözünürlükler için 9, 10, 11, 12, 13 at ile bazı çözümler elde edilmektedir. Ayrıca, çözünürlük 0,3, 6-AKP çözümlerini bulmak için en verimli çözünürlüktür. Ayrıca, analizlerimiz gösterdi ki 0,2 çözünürlüğü, 6-AKP'nin 195 çözümünü daha fazla çözüm bulmak için en iyi çözünürlüktür. Son olarak, modülerlik yöntemi, 2253 çözüm arasından 0,5 çözünürlük için 61'den, 0,2 çözünürlük için 195'e kadar olan çözümleri çıkarıyor.

Keywords

At çizgesi, modülerlik, At Kaplama Problemi, Makine öğrenmesi

References

• S. Bai, G. Zhu, and J. Huang, "An Intelligent Algorithm for the (1,2,2)-Generalized Knight's Tour Problem," in 2013 Ninth International Conference on Computational Intelligence and Security, 14-15 Dec. 2013 2013, pp. 583-588, doi: 10.1109/CIS.2013.129.
• H. Jian and B. Sen, "An Efficient Algorithm for the Generalized (1,k)-Knight's Tours Problem," in 2009 First International Workshop on Education Technology and Computer Science, 7-8 March 2009 2009, vol. 1, pp. 697-701, doi: 10.1109/ETCS.2009.161.
• P. Hingston and G. Kendall, Ant Colonies Discover Knight's Tours. 2004, pp. 1213-1218.
• S. Bai, X. Liao, X. Qu, and Y. Liu, "Generalized Knight's Tour Problem and Its Solutions Algorithm," in 2006 International Conference on Computational Intelligence and Security, 3-6 Nov. 2006 2006, vol. 1, pp. 570-573, doi: 10.1109/ICCIAS.2006.294200.
• I. Parberry, "An Efficient Algorithm for the Knight's Tour Problem," Discrete Applied Mathematics, vol. 73, pp. 251-260, 03/01 1997, doi: 10.1016/S0166-218X(96)00010-8.
• J. Demaio and B. Mathew, "Which Chessboards have a Closed Knight's Tour within the Rectangular Prism?," Electr. J. Comb., vol. 18, 01/05 2011, doi: 10.37236/495.
• A. Kumar, "Non-crossing Knight's Tour in 3-Dimension," 03/29 2008.
• P. Aliquippa and Pennsylvania, "Thematic Knight's Tour Quotes " 06/29 2020.
• A. Philip, "A Generalized Pseudo-Knight?s Tour Algorithm for Encryption of an Image," IEEE Potentials, vol. 32, no. 6, pp. 10-16, 2013, doi: 10.1109/MPOT.2012.2219651.
• J. Kumar and S. Nirmala, "Securing the contents of document images using knight moves and genetic approach," in 2015 International Conference on Advances in Computing, Communications and Informatics (ICACCI), 10-13 Aug. 2015 2015, pp. 1091-1095, doi: 10.1109/ICACCI.2015.7275755.
• J. Delei, B. Sen, and D. Wenming, "An Image Encryption Algorithm Based on Knight's Tour and Slip Encryption-Filter," in 2008 International Conference on Computer Science and Software Engineering, 12-14 Dec. 2008 2008, vol. 1, pp. 251-255, doi: 10.1109/CSSE.2008.1142.
• M. Singh, A. Kakkar, and M. Singh, "Image Encryption Scheme Based on Knight's Tour Problem," Procedia Computer Science, vol. 70, pp. 245-250, 12/31 2015, doi: 10.1016/j.procs.2015.10.081.
• Q. B. Hou, X. F. Yang, Y. S. Wang, and X. S. Huang, "An image scrambling algorithm based on wavelet transform and Knight's tour," vol. 41, pp. 369-375, 02/01 2004.
• D. C. Fisher, "On the n x n Knight Cover Problem," Ars Comb., vol. 69, / 2003.
• F. Rubin, "Improved Knight Coverings," Ars Combinatoria, vol. 69, / 2003.
• F. Rubin, "Knight Covers for the 50x50 Chessboard," presented at the Mathfest 2004, Providence RI, 2004.
• F. Rubin, "A Family of Efficient Knight Covering Patterns," Journal of Recreational Mathematics, Article vol. 33, no. 3, pp. 165-175, 2005. [Online]. Available: http://search.ebscohost.com/login.aspx?direct=true&db=aph&AN=26073841&site=ehost-live.
• F. Rubin, "An Improved Method for Finding Knight Covers," Ars Combinatoria, vol. 82, / 2007.
• B. Lemaire, "Knights Covers on NxN Chessboards," J. Recr. Math., vol. 31, pp. 87-99, 2003.
• A. H. Jackson and R. P. Pargas, "Solutions to the NxN Knights Covering Problem," Journal of Recreational Mathematics vol. 23, pp. 255-267, 1991.
• F. Wei, "Research on Knight Covering Based on Breadth First Search Algorithm," (in English), Applied Mechanic and Materials, vol. 686, pp. 377-380, 2014.
• S. Güldal, M. Lipscomb, and M. M. Tanik, "Solving Knights Covering Problem: Backtracking, Permutation, Bipartite Graph, and Independent Set," presented at the Nineteenth Annual Early Career Technical Conference, Birmingham, Alabama USA, 2019.
• S. Güldal, M. M. Tanik, and M. M. Lipscomb, "Solving Knights Covering Problem by a Hybrid Algorithm," presented at the IEEE SouthEastConn, Huntsville, Alabama, April 11 - 14 2019.
• S. Güldal, "Connectives of Knights Covering Problem By Girvan-Newman Clustering," presented at the SDPS 2019 Workshop, Madrid, Spain, November 25-26 2019, 2019.
• S. Güldal, "Unsupervised Machine Learning Algorithms to Find 3-KCP Solution: Modularity, Clique Percolation, Spectral, Centrality, and Hierarchical Clustering," 8, 2021, doi: https://dergipark.org.tr/tr/pub/adyumbd/927555.
• S. Güldal, "4×4 Knight’s Graph Analysis by Modularity A Knight Graph Application," 16, 2021, doi: https://dergipark.org.tr/tr/pub/tjst/710151.
• S. Güldal, "Identification of Knights’ Relations for 5×5 Knight Graph by Modularity," 7, 2021, doi: https://dergipark.org.tr/tr/pub/adyumbd/792772.
• "Analysis of the Application of Artificial Intelligence in Computer Networks Technology," IOP Conference Series: Materials Science and Engineering, vol. 750, p. 012097, 03/24 2020, doi: 10.1088/1757-899X/750/1/012097.
• C. Engström and S. Silvestrov, "PageRank for networks, graphs, and Markov chains," Theory of Probability and Mathematical Statistics, vol. 96, p. 1, 10/05 2018, doi: 10.1090/tpms/1034.
• Y. L. Karpov, I. Volkova, A. A. Vylitok, L. Karpov, and Y. G. Smetanin, "Designing classes’ interfaces for neural network graph model," Proceedings of the Institute for System Programming of RAS, vol. 31, pp. 97-112, 10/01 2019, doi: 10.15514/ISPRAS-2019-31(4)-6.
• M. Gençer, "Sosyal Ağ Analizi Yöntemlerine Bir Bakış," Yildiz Social Science Review, vol. 3, pp. 19-34, 12/15 2017.
• P. Nerurkar, M. Chandane, and S. Bhirud, "Understanding attribute and social circle correlation in social networks," Turkish Journal of Electrical Engineering and Computer Sciences, vol. 27, pp. 1228-1242, 03/22 2019, doi: 10.3906/elk-1806-91.
• N. Almolhem, Y. Rahal, and M. Dakkak, "Social network analysis in Telecom data," Journal of Big Data, vol. 6, 12/01 2019, doi: 10.1186/s40537-019-0264-6.
• M. E. J. Newman, "Modularity and community structure in networks," vol. 103, no. 23, pp. 8577-8582, 2006, doi: 10.1073/pnas.0601602103 %J Proceedings of the National Academy of Sciences.
• K. Kugler, L. Mueller, A. Graber, and M. Dehmer, "Integrative Network Biology: Graph Prototyping for Co-Expression Cancer Networks," PloS one, vol. 6, p. e22843, 07/29 2011, doi: 10.1371/journal.pone.0022843.
• B. Eckman and P. Brown, "Graph data management for molecular and cell biology," IBM Journal of Research and Development, vol. 50, pp. 545-560, 12/01 2006, doi: 10.1147/rd.506.0545.
• V. Gadiyaram, S. Vishveshwara, and S. Vishveshwara, From Quantum Chemistry to Networks in Biology: A Graph Spectral Approach to Protein Structure Analyses. 2019.
• L. Johnsen, "Graph Analysis of Word Networks," http://ceur-ws.org/Vol-2021/, vol. 2021, 01/01 2017.
• E. Hasanah and D. Agustiningsih, Analysis of “Halal” Word in Social Media Using Text Mining and Word Networking. 2020.
• R. Ozcelik, G. Uludoğan, S. Parlar, Ö. Bakay, O. Ergelen, and O. Yildiz, User Interface for Turkish Word Network KeNet. 2019, pp. 1-4.
• S. Valverde, B. Vidiella Rocamora, R. Montañez Martínez, A. Fraile, S. Sacristán, and F. García-Arenal, "Coexistence of nestedness and modularity in host–pathogen infection networks," Nature Ecology & Evolution, pp. 1-10, 03/09 2020, doi: 10.1038/s41559-020-1130-9.
• T. Shiino, "Phylodynamic analysis of a viral infection network," Frontiers in microbiology, vol. 3, p. 278, 07/31 2012, doi: 10.3389/fmicb.2012.00278.
• Q. Fan, J. Yang, D. Wipf, B. Chen, and X. Tong, "Image smoothing via unsupervised learning," vol. 37, no. 6 %J ACM Trans. Graph., p. Article 259, 2018, doi: 10.1145/3272127.3275081.
• Y. Zheng, X. Li, and X. Lu, "Unsupervised Learning of Human Action Categories in Still Images with Deep Representations," vol. 15, no. 4 %J ACM Trans. Multimedia Comput. Commun. Appl., p. Article 112, 2019, doi: 10.1145/3362161.
• A. Hart, "Using Neural Networks for Classification Tasks – Some Experiments on Datasets and Practical Advice," Journal of the Operational Research Society, vol. 43, no. 3, pp. 215-226, 1992/03/01 1992, doi: 10.1057/jors.1992.31.
• R. Marxer and H. Purwins, "Unsupervised incremental online learning and prediction of musical audio signals," vol. 24, no. 5 %J IEEE/ACM Trans. Audio, Speech and Lang. Proc., pp. 863–874, 2016, doi: 10.1109/taslp.2016.2530409.
• F. Saki, N. Kehtarnavaz, F. Saki, and N. Kehtarnavaz, "Real-Time Unsupervised Classification of Environmental Noise Signals," vol. 25, no. 8 %J IEEE/ACM Trans. Audio, Speech and Lang. Proc., pp. 1657–1667, 2017, doi: 10.1109/taslp.2017.2711059.
• J. E. Vogt, "Unsupervised structure detection in biomedical data," vol. 12, no. 4 %J IEEE/ACM Trans. Comput. Biol. Bioinformatics, pp. 753–760, 2015, doi: 10.1109/tcbb.2015.2394408.
• J. G. Dy and C. E. Brodley, "Feature Selection for Unsupervised Learning," vol. 5, pp. 845–889, 2004.
• H. Hammarström and L. Borin, "Unsupervised learning of morphology," vol. 37, no. 2 %J Comput. Linguist., pp. 309–350, 2011, doi: 10.1162/COLI_a_00050.
• M. Creutz and K. Lagus, "Unsupervised models for morpheme segmentation and morphology learning," vol. 4, no. 1 %J ACM Trans. Speech Lang. Process., p. Article 3, 2007, doi: 10.1145/1187415.1187418.
• S. Küçükpetek, F. Polat, and H. Oğuztüzün, "Multilevel graph partitioning: an evolutionary approach," Journal of the Operational Research Society, vol. 56, no. 5, pp. 549-562, 2005/05/01 2005, doi: 10.1057/palgrave.jors.2601837.
• M. E. J. Newman, "Analysis of weighted networks," Physical Review E, vol. 70, no. 5, p. 056131, 11/24/ 2004, doi: 10.1103/PhysRevE.70.056131.
• V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, "Fast unfolding of communities in large networks," vol. 2008, p. 10008, October 01, 2008 2008, doi: 10.1088/1742-5468/2008/10/p10008.
• M. Bastian, S. Heymann, and M. Jacomy, "Gephi: an open source software for exploring and manipulating networks," in International AAAI Conference on Weblogs and Social Media, 2009.
• V. D. Blondel, J.-L. Guillaume, R. Lambiotte, E. J. J. o. s. m. t. Lefebvre, and experiment, "Fast unfolding of communities in large networks," vol. 2008, no. 10, p. P10008, 2008.
• R. Lambiotte, J.-C. Delvenne, and M. J. a. p. a. Barahona, "Laplacian dynamics and multiscale modular structure in networks," 2008.