Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Math algorithm

  1. Aug 31, 2012 #1
    Hi,

    I am searching for a smart way of calculating all numbers in a special matrix kind of game.
    The game board consist of numbers between 1 and 9 in a 4x4 matrix.

    Swiping over numbers will either add up (swiping left or right), subtract (swiping up or down) or do nothing (diagonal swiping).

    I wonder how many combinations there are and if there is a simple way of getting all the results. There is a free iOS app that resembles of this game idea:
    http://itunes.apple.com/us/app/addictive/id543137735?l=sv&ls=1&mt=8

    I would be glad for any answers, there seems to be a lot of different combinations.
     
  2. jcsd
  3. Aug 31, 2012 #2

    chiro

    User Avatar
    Science Advisor

    Hey najken and welcome to the forums.

    Can you explain the constraints of the matrix? Are there are conditions on the elements in the matrix? When you do your swiping thing how do the matrices change? What's the goal of the game?
     
  4. Aug 31, 2012 #3
    thank you

    the goal of the game is to get numbers specified. it's these specified numbers I would like to find. the matrix is 4x4 random integers between 1 and 9.

    You are not allowed to swipe over the same tile again. You can swipe diagonally, left, right up, down with the affect of adding and subtracting as described in post #1.
     
  5. Aug 31, 2012 #4

    chiro

    User Avatar
    Science Advisor

    If all the numbers are independent and you can all have combinations of numbers in the 4x4 matrix, the number of original configurations is 9^16 which is a big number.

    The only thing now that I am confused with is the swiping. You say you can't swipe the same tile over again so I'm guessing that If I swipe the tiles (1,1) and (2,2) then I can't touch those tiles again. Is this right?
     
  6. Aug 31, 2012 #5
    that is absolutely right, and you cannot "skip" or jump over tiles that are in between to get to a tile further away.

    The app I posted is kind of similar to Rumble/Ruzzle but that one works with letters and words instead of numbers
     
  7. Aug 31, 2012 #6

    chiro

    User Avatar
    Science Advisor

    Well the thing to first look at is the number of swipes you can do.

    This is going to be basically a massive markov style problem: in non-mathematic speak, markov means conditional so that what you do right now affects what you do later but the thing is that this is a lot more complicated than normal markov since normal markov only takes into account what happened one time ago where-as you need to consider the entire history.

    The first thing to do is to classify all the possible swipes you can do. Obviously they will always involve at least two-squares but I'm guessing they could involve at least four squares. These becomes your events.

    Now given this you basically create a new board and simulate it with a computer for each possibility. Each possibility will create a constraint, so you find the number of possible moves given the history of the board and simulate those and keep going until you can't go any more.

    So basically all this means is that you create a program that has simulated all possibilities and then you count all possibilities up in terms of the swipes without respect to the actual numbers.

    You can code this kind of thing up with a computer and use something like C++ or even something like Python.

    You store all the possible swipe histories that work and save that somewhere.

    Once you have the swipes, if you want to find out the possible combinations then you will need to introduce probability and a thing called convolution of discrete random variables.

    The convolution basically creates a probability distribution for X + Y + Z where X,Y,Z are independent and this deals with finding distributions of not only sums but also differences (instead of X + Y + Z you can get X - Y - Z).

    You apply this to every kind of generated swipe sequence and then you will have a probability distribution that is conditional which you can expand out which will give you the probability distribution for every single combination of the game.

    This is not going to be easy and will most likely require a computer to generate the possible swipe sequences so that you can create distributions for each swipe sequence.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook