Trò chơi Ếch và Nhái

Mình được chơi trò chơi này khi đi team building với công ty. Mặc dù luật chơi rất đơn giản nhưng là khá hấp dẫn và khó giải quyết, kiểu như Hanoi Tower vậy. Tên nguyên bản của trò chơi là Frogs and Toads, được giới thiệu bởi nhà toán học người Anh Richard Kenneth Guy. Xin giới thiệu với mọi người.

Luật chơi

Một nhóm người gồm $n$ người đội $A$ và $n$ người đội $B$ ngồi trên một dãy cái ghế theo thứ tự sau:

Với $-$ là ghế trống. Hãy tìm cách để dịch chuyển vị trí chỗ ngồi của từng người sao cho đạt được thứ tự $BB\dots B-AA\dots A$, nghĩa là 2 đội chuyển đổi vị trí cho nhau, với quy luật:

• Mỗi lần chỉ dịch chuyển 1 người vào chiếc ghế trống

• Một người được dịch chuyển với điều kiện:

  • Nếu người ấy ngồi sát bên trái hoặc bên phải ghế trống

  • Nếu người ấy cách ghế trống đúng một người khác đội

Ví dụ:

• Với $n=1$ thì cách dịch chuyển có thể như sau: A-B => -AB => B-A

• Với $n=2$ thì cách dịch chuyển có thể như sau: AA-BB => A-ABB => ABA-B => AB-AB => -BAAB => B-AAB => BA-AB => BABA- => BAB-A => B-BAA => BB-AA

Giải bằng Breadth First Search (BFS)

Có lẽ sẽ có những thuật toán tốt hơn, bài này mình chỉ đơn giản giải bằng BFS. Ý tưởng cơ bản là tại một trạng thái, mình sẽ sinh ra tất cả các trạng thái mới có thể biến đổi từ trạng thái đã cho rồi lưu vào một queue trạng thái, và dùng một tập hợp các trạng thái đã xét để tránh lặp vô tận. Dưới đây là đoạn code BFS.

function solveBFS(startArr, targetStr) {
        const queue = [new State(startArr, null)];
        const visited = new Set([startArr.join('')]);
        while (queue.length > 0) {
          const st = queue.shift();
          const key = st.state.join('');
          if (key === targetStr) return st;
          const nexts = st.generateNewStates();
          for (const ns of nexts) {
            const k = ns.state.join('');
            if (!visited.has(k)) {
              visited.add(k);
              queue.push(ns);
            }
          }
        }
        return null;
      }

Demo