Google – Initialize Board

Google – Initialize Board
有一个类似于消方块的游戏，通过滑动交换items，行或者列凑过3个相同的item就消掉。要求是让初始化一个board，初始化之后要能使用户能够做出first move，意思是不能出现还没move就有三个相同的连在一起。
board是满的，不是空一格用来移动方块那种，是通过交换上下左右四个方向的方块。

Backtracking, 有点像sudoku

  public int[][] initializeBoard(int m, int n) {

    int[][] board = new int[m][n];

    int[] items = {1, 2, 3};

     

    initialize(board, 0, 0, items);

    return board;

  }

   

  private boolean initialize(int[][] board, int i, int j, int[] items) {

    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {

      return true;

    }

    if (board[i][j] != 0) {

      return true;

    }

     

    for (int k = 0; k < 3; k++) {

      board[i][j] = items[k]; // choose random one to build random board

      boolean result = true;

      if (isValid(board, i, j)) {

        result &= initialize(board, i - 1, j, items);

        result &= initialize(board, i + 1, j, items);

        result &= initialize(board, i, j - 1, items);

        result &= initialize(board, i, j + 1, items);

         

        if (result == true) {

          return true;

        }

      }

    }

     

    return false;

  }

   

  private boolean isValid(int[][] board, int i, int j) {

    int curr = board[i][j];

    if (i >= 2 && board[i - 2][j] == curr && board[i - 1][j] == curr) {

      return false;

    }

    if (i < board.length - 2 && board[i + 1][j] == curr && board[i + 2][j] == curr) {

      return false;

    }

    if (j >= 2 && board[i][j - 2] == curr && board[i][j - 1] == curr) {

      return false;

    }

    if (j < board[0].length - 2 && board[i][j + 1] == curr && board[i][j + 2] == curr) {

      return false;

    }

     

    return true;

  }

http://www.1point3acres.com/bbs/thread-143308-1-1.html
Design a algorithm to initialize the board of Candy Crush Saga. With M x N board, Q types of candies. (Rules: no 3 for run after initialization, must contain at least one valid move at the beginning)

先把Candy简化成数字，类型数组就成了[0, 1, 2, ..., Q-1]。规则一共三条：随机（至少玩家看上去是）；不能一开始就有3个共线的；开局至少有一步能保证有消除（不然没法玩。。）.鏈枃鍘熷垱鑷�1point3acres璁哄潧
鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
1. 我首先关注的是前两条规则，因为觉得第三条只是小修改（尽管如果初始化完成后，再修改成符合第三条，可能导致连锁反应）。因为“随机”一直在我心头挥之不去，所以首先想到的是遍历所有格子，每次随机挑一个Q放进去，但立刻意识到这样很有可能导致死锁，尤其Q很小的时候，然后举了个死锁的例子。

2. 因为之前考虑过Q很小，所以最简单就是{0, 1}两种，立刻想到国际象棋棋盘：两色相间一定能填满而且无冲突。然后想到能不能先按照国际象棋棋盘填满，然后在这个基础上进行”随机化“。假如我有个遵循前两条规则的函数random()，对棋盘进行随机化。因为是在01棋盘改，所以第一遍下来可能还是很”假“，但既然这个函数是遵循前两条规则的，那么大可放心的多执行几遍。就像PS的滤镜叠加使用~ 然后开始讨论这个random()函数，大体思路是遍历棋盘，对每个格子有0.5 的概率进行”尝试修改“。(随机化就是一个慢慢tweak的过程，这个参数后面提到要根据实际效果调整）。尝试修改的算法就是：q = random(0, Q); 以q为中心向上下左右四个方向，一共有6条长度为3的线会造成潜在冲突，因此逐个检查一遍，假如无冲突就把当前位置替换为q。最后根据实际效果决定是否再来几次~

3. 然后就剩第三条规则：开局至少有一步能走。我上面阐述的时候就一直有个感觉，每局开始看似随机但一定有定势。然后让小哥打开手机游戏开了两局看了下，果然，每局开头一定会有{V型, _/型} 中的一种或两种排列，保证挪一步就能消除。跟小哥聊了这个想法之后，我的做法就是01棋盘生成后，随机选一个排列，比如V型，然后在棋盘上随机选一个（也可以多个）位置，把这个位置画出的V全部mark成不可修改。然后在这个基础上跑上面提到的random()算法。第三条规则也可以有很多随机性，必须类型选择，类型对应位置、个数的选择。

聊到这儿已经超时了。我问小哥这背后怎么实现的，他说他也不知道。。感觉这题很开放，不一定涉及多么高级的算法，几个随机参数的调整或许就能让开局看上去足够无规律了

Read full article from Google – Initialize Board