Finding a solution for lights out game using greedy method(backtracking)

user_13218692 0
Viewed 578

I am trying to find the solution of lights out game using backtracking method. I am not able to understand the algorithm for this process. My approach is to enumerate all integers from 0 to 2n2 - 1 and For each integer convert it into a binary number which has n*n bits. Then, separate it into n2 binary digits (0 for light off, 1 for light on) and assign them into a n × n grid, for example: I have written the following code:-

    void find_solution(int dest[][MAX_SIZE], int size) {

    int y = pow(size,size);
    int remainder;

    for (int x = 0; x<pow(2,y); x++){
        int i = 1;
        int binary_number = 0;
        int n = x;
        while (n!=0) {
            remainder = n%2;
            n/=2;
            binary_number += remainder*i;
            i *= 10;
        }
        int binary_number_digits[size][size];
        for (int k = 0; k<size; k++) {
            for (int l = 0; l<size; l++) {
                binary_number_digits[k][l] = binary_number%10;
                binary_number/=10;
            }
        }
        int count = 0;
        for (int i = 0; i<size; i++) {
            for (int j = 0; j<size; j++) {
                if (binary_number_digits[i][j] == dest[i][j]) {
                    count++;
                }
                if (count <= 4 && count > 0) {
                    if (binary_number_digits[i][j] == 1) {
                        cout << i << j;
                    }
                }
            }
        }
    }
}

I have converted the decimal digits to binary numbers and stored it in an array and checking if they match the randomly generated n*n grid. If it is a 1, it prints that coordinate(x,y). Anyone could please help me solve the problem with this algorithm. Thanks!

algorithm c++
1 Answers

The following observations are required (as listed on the Wiki):

  • In a solution each light has to be pressed at most once. This is because pressing a light an odd number of times is equivalent to pressing it once and pressing a light an even number of times is equivalent to not pressing it.

  • The order in which the lights are pressed does not matter. This follows from the previous point: Switching a light changes its neighbors, but for the end result of the neighbor it only matters if it was changed an even or odd number of times.

From this we can conclude that we can represent a solution as a 0-1 matrix of the same size as the board, where 1 means that in the solution the light at that position should be pressed. The brute-force algorithm then is to check all nxn 0-1 matrices to see if any of these solves the initial board.

In your implementation, you do the first step (generating all nxn 0-1 matrices that represent ways of pressing the lamps). You are missing the step of checking which of these solve the board.

I would slightly simplify the binary number handling by using std::bitset.

(The following code also requires C++17 for std::optional.)

#include <bitset>
#include <iostream>
#include <optional>
#include <random>

template <size_t N>
class board_t {
public:
  void print() const {

    for (size_t i = 0; i < data.size(); i++) {
      std::cout << data[i];

      if (i % N == N - 1) {
        std::cout << std::endl;
      }
    }
  }

  void randomize() {
    std::random_device device;
    std::default_random_engine generator{device()};
    std::bernoulli_distribution bernoulli(0.5);

    for (size_t i = 0; i < data.size(); i++) {
      data[i] = bernoulli(generator);
    }
  }

  /**
   * Brute-force all possible ways of pressing the lights.
   */
  std::optional<board_t<N>> solve() const {
    board_t<N> press{};

    do {
      board_t<N> applied{this->apply(press)};

      if (applied.data.none()) {
        return press;
      }

      press.increment();

      /**
       * Aborts when incrementing press overflows back to the initial
       * solution of not pressing any lamp.
       */
    } while (press.data.any());

    /**
     * Return empty std::optional when no solution was found.
     */
    return {};
  }

private:
  /**
   * Indicates which lights are on.
   */
  std::bitset<N * N> data;

  /**
   * Interpret the board as a N*N bit binary number and increment it by one.
   */
  void increment() {
    for (size_t i = 0; i < data.size(); i++) {
      if (data[i]) {
        data[i] = false;
      } else {
        data[i] = true;
        break;
      }
    }
  }

  /**
   * Press each light indicated by press.
   */
  board_t<N> apply(const board_t<N>& press) const {
    board_t<N> copy{*this};

    for (size_t y = 0; y < N; y++) {
      for (size_t x = 0; x < N; x++) {

        size_t offset = x + y * N;

        if (press.data[offset]) {
          copy.data.flip(offset);

          /**
           * Check neighbors.
           */
          if (x > 0) {
            copy.data.flip(offset - 1);
          }

          if (x < N - 1) {
            copy.data.flip(offset + 1);
          }

          if (y > 0) {
            copy.data.flip(offset - N);
          }

          if (y < N - 1) {
            copy.data.flip(offset + N);
          }
        }
      }
    }

    return copy;
  }
};

int main(void) {

  constexpr size_t N = 3;

  board_t<N> board{};

  board.randomize();
  board.print();

  auto solution{board.solve()};

  if (solution) {
    std::cout << "Solution:" << std::endl;
    solution->print();
  } else {
    std::cout << "No solution!" << std::endl;
  }

  return 0;
}
user_109921730
Related