PERBANDINGAN KEEFEKTIFAN ALGORITMA BACKTRACKING DAN SOFT COMPUTING DALAM MEMECAHKAN PERMAINAN PAPAN NONOGRAM
DOI:
https://doi.org/10.55606/jutiti.v3i1.2069Keywords:
Soft computing, Nonogram, Depth-First SearchAbstract
Solving logic puzzles using specific algorithms presents an intriguing challenge where the efficiency of the approaches is crucial. One such puzzle involves solving nonograms, where the task is to fill in board fields according to the conditions specified for each row and column. The availability of various methods allows for comparing their efficiency and effectiveness. This study aimed to evaluate the effectiveness of two algorithms from different categories. We selected a modified Depth-First Search (DFS) method and a soft computing method based on permutations generation to solve a set of chosen nonograms. The research was conducted using four different board sizes, and the results indicated that the effectiveness of the methods largely depends on the complexity of the nonogram. The algorithm employing permutations consistently produced stable results, while the DFS method did not always guarantee a complete solution.
References
Agrawal, A., Gans, J., Goldfarb, A., 2018. Prediction machines: the simple economics of artificial intelligence. Harvard Business Press.
Asano, T., Izumi, T., Kiyomi, M., Konagaya, M., Ono, H., Otachi, Y., Schweitzer, P., Tarui, J., Uehara, R., 2014. Depth-first search using o(n) bits, in: International Symposium on Algorithms and Computation, Springer. pp. 553–564.
Batenburg, K.J., Henstra, S., Kosters, W.A., Palenstijn, W.J., 2009. Constructing simple nonograms of varying difficulty. Pure Mathematics and Applications (Pu. MA) 20, 1–15.
Batenburg, K.J., Kosters, W.A., 2009. Solving nonograms by combining relaxations. Pattern Recognition 42, 1672–1683.
Berend, D., Pomeranz, D., Rabani, R., Raziel, B., 2014. Nonograms: Combinatorial questions and algorithms. Discrete Applied Mathematics 169, 30–42.
Bonet, B., Geffner, H., 2006. Learning depth-first search: A unified approach to heuristic search in deterministic and non-deterministic settings, and its application to mdps., in: ICAPS, pp. 142–151.
Chandrasekaran, M., Muralidhar, M., Krishna, C.M., Dixit, U., 2010. Application of soft computing techniques in machining performance prediction and optimization: a literature review. The International Journal of Advanced Manufacturing Technology 46, 445–464.
Chaturvedi, D.K., 2008. Soft computing. Studies in Computational intelligence 103.
Chen, Y.C., Lin, S.S., 2019. A fast nonogram solver that won the taai 2017 and icga 2018 tournaments. ICGA Journal 41, 2–14.
Conant, E.F., Toledano, A.Y., Periaswamy, S., Fotin, S.V., Go, J., Boatsman, J.E., Hoffmeister, J.W., 2019. Improving accuracy and efficiency with concurrent use of artificial intelligence for digital breast tomosynthesis. Radiology: Artificial Intelligence 1, e180096.
Dick, S., 2019. Artificial intelligence .
Du, K.L., Swamy, M.N., 2006. Neural networks in a softcomputing framework. Springer Science & Business Media.
Fethi, M.D., Pasiouras, F., 2010. Assessing bank efficiency and performance with operational research and artificial intelligence techniques: A survey. European journal of operational research 204, 189–198.
Firmansyah, E.R., Masruroh, S.U., Fahrianto, F., 2016. Comparative analysis of a* and basic theta* algorithm in android-based pathfinding games, in: 2016 6th International Conference on Information and Communication Technology for The Muslim World (ICT4M), IEEE. pp. 275–280.
Herrera, F., Lozano, M., Molina, D., et al., 2010. Test suite for the special issue of soft computing on scalability of evolutionary algorithms and other metaheuristics for large scale continuous optimization problems. Last accessed: July .
Khan, K.A., 2020. Solving nonograms using integer programming without coloring. IEEE Transactions on Games .
Konar, A., 2018. Artificial intelligence and soft computing: behavioral and cognitive modeling of the human brain. CRC press.
Kotsiantis, S.B., Zaharakis, I., Pintelas, P., 2007. Supervised machine learning: A review of classification techniques. Emerging artificial intelligence applications in computer engineering 160, 3–24.
Malhotra, R.K., Indrayan, A., 2010. A simple nomogram for sample size for estimating sensitivity and specificity of medical tests. Indian journal of ophthalmology 58, 519.
McCarthy, J., 1998. What is artificial intelligence? .
Mingote, L., Azevedo, F., 2009. Colored nonograms: an integer linear programming approach, in: Portuguese Conference on Artificial Intelligence, Springer. pp. 213–224. [22] Mitchell, R., Michalski, J., Carbonell, T., 2013. An artificial intelligence approach. Springer.
Nilsson, N.J., 2014. Principles of artificial intelligence. Morgan Kaufmann.
Rahim, R., Abdullah, D., Simarmata, J., Pranolo, A., Ahmar, A.S., Hidayat, R., Napitupulu, D., Nurdiyanto, H., Febriadi, B., Zamzami, Z., 2018. Block architecture problem with depth first search solution and its application, in: Journal of Physics: Conference Series, IOP Publishing. p. 012006.
ur Rehman, A., Sałabun, W., Faizi, S., Hussain, M., W ˛atróbski, J., 2021. On graph structures in fuzzy environment using optimization parameter. IEEE Access 9, 75699–75711.
Rhodes, C., Blewitt, W., Sharp, C., Ushaw, G., Morgan, G., 2014. Smart routing: A novel application of collaborative path-finding to smart parking systems, in: 2014 IEEE 16th Conference on Business Informatics, IEEE. pp. 119–126.
Russell, S., Norvig, P., 2002. Artificial intelligence: a modern approach .
Senthilkumaran, N., Rajesh, R., 2009. Image segmentation-a survey of soft computing approaches, in: 2009 International Conference on Advances in Recent Technologies in Communication and Computing, IEEE. pp. 844–846.
Sohn, Y.S., Oh, K., Kim, B.S., 2007. A recognition method of the printed alphabet by using nonogram puzzle, in: Proceedings of The 8th International Symposium on Advanced Intelligent Systems, pp. 232–236.
Stojmenovic, I., Russell, M., Vukojevic, B., 2000. Depth first search and location based localized routing and qos routing in wireless networks, in: Proceedings 2000 International Conference on Parallel Processing, IEEE. pp. 173–180.
Tan, X., Ma, Z., Yan, L., Ye, W., Liu, Z., Liang, C., 2019. Radiomics nomogram outperforms size criteria in discriminating lymph node metastasis in resectable esophageal squamous cell carcinoma. European radiology 29, 392–400.
Tsai, J.T., 2012. Solving japanese nonograms by taguchi-based genetic algorithm. Applied Intelligence 37, 405–419.
Tsai, J.T., Chou, P.Y., Fang, J.C., 2011. Learning intelligent genetic algorithms using japanese nonograms. IEEE Transactions on Education 55, 164–168.
Wang, W.L., Tang, M.H., 2014. Simulated annealing approach to solve nonogram puzzles with multiple solutions. Procedia Computer Science 36, 541–548.
Wiggers, W., van Bergen, W., 2004. A comparison of a genetic algorithm and a depth first search algorithm applied to japanese nonograms, in: Twente student conference on IT, Citeseer.
Wu, I.C., Sun, D.J., Chen, L.P., Chen, K.Y., Kuo, C.H., Kang, H.H., Lin, H.H., 2013. An efficient approach to solving nonograms. IEEE Transactions on Computational Intelligence and AI in Games 5, 251–264.
Yu, C.H., Lee, H.L., Chen, L.H., 2011. An efficient algorithm for solving nonograms. Applied Intelligence 35, 18–31.
Zadeh, L.A., 1996. Soft computing and fuzzy logic, in: Fuzzy Sets, Fuzzy Logic, and Fuzzy Systems: Selected Papers by Lotfi a Zadeh. World Scientific, pp. 796–804.
Zavistanavicius, R., 2013. Nonogram solving algorithms analysis and implementation for augmented reality system
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Jurnal Teknik Informatika dan Teknologi Informasi
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
