DOI: https://doi.org/10.32515/2664-262X.2019.2(33).190-201

Analysis of the Methods for Solving Game Puzzles such as «Flip-Flop»

Yuriy Parkhomenko, Mykhailo Parkhomenko, Ludmila Rybakova, Andriy Bokiy

About the Authors

Yuriy Parkhomenko, Associate Professor, PhD in Technics (Candidate of Technics Sciences), Central Ukrainian National Technical University, Kropyvnytskyi, Ukraine

Mykhailo Parkhomenko, director, Central Ukrainian National Technical University, Kropyvnytskyi, Ukraine

Ludmila Rybakova, Associate Professor, Central Ukrainian National Technical University, Kropyvnytskyi, Ukraine

Andriy Bokiy, student, Central Ukrainian National Technical University, Kropyvnytskyi, Ukraine

Abstract

There is a variety of popular puzzles having a goal of reducing an arbitrary binary matrix to either all “0” or “1” matrix. In this paper we study methods for solving “Flip-Flop” like puzzles of dimensions 3x3, 3x4, 4x4 applying tools of logical analysis of situations, combinatorics and discrete mathematics. We found that applying the method of sequential analysis of each combination that works well for 3x3 matrices is cumbersome and inefficient for matrices of 4x4 and higher dimensionalities. Therefore, we discovered and analyzed algorithms named trait selection method, stream method and snake method which work better We concluded that in order to find an optimized solution it is helpful to check if each current combination matches one of the pre-final ones, or to swap «0»s with «1»s and vise versa.

Keywords

computer puzzle games, logical situation analysis, combinatorics, discrete mathematics, trait method, stream method, snake method

Full Text:

PDF

References

1. Raskin, M.A. (2008). Vvedeniye v teoriyu igr // Letnyaya shkola «Sovremennaya matematika». Dubna, www.mccme.ru. Retrieved from: https://www.mccme.ru/dubna/2008/courses/raskin.htm [in Russian].

2. Mazalov, V.V. (2010). Matematicheskaya teoriya igr i prilozheniy [Mathematical game theory and applications]. Sankt-Peterburg - Moskva - Krasnodar: Lan' [in Russian].

3. Yablonskiy,S.V. (2003). Vvedeniye v diskretnuyu matematiku [Introduction to Discrete Mathematics]. Moskow: Vyssh. shk. [in Russian].

4. Míshchenko, N. (2006). Shtuchniy íntelekt-viklik chasu [Artificial Intelligence Challenge of Time]. Naukoviy svít, № 10, 12-13 [in Ukrainian]

5. Vilenkin, N.YA. (1975). Populyarnaya kombinatorika [Popular combinatorics]. Moskow: Nauka [in Russian].

GOST Style Citations

Пристатейна бібліографія ГОСТ

  • Раскин М.А. Введение в теорию игр // Летняя школа «Современная математика». Дубна, 2008. URL: https://www.mccme.ru/dubna/2008/courses/raskin.htm (дата обращения: 08.11.2019)
  • Мазалов В.В. Математическая теория игр и приложения. – Санкт-Петербург - Москва - Краснодар: Лань, 2010. 446 с.
  • Яблонский С.В. Введение в дискретную математику. Москва: Высш. шк., 2003. 384 с.
  • Міщенко Н. Штучний інтелект-виклик часу. Науковий світ. 2006. № 10. C. 12-13
  • Виленкин Н.Я. Популярная комбинаторика. Москва: Наука, 1975. 208 с.
    • Copyright (c) 2019 Yuriy Parkhomenko, Mykhailo Parkhomenko, Ludmila Rybakova, Andriy Bokiy