Lights out game algorithm

by

There is a standard algorithm for solving this problem that is based on Gaussian elimination over GF(2). The idea is to set up a matrix representing the button presses a column vector representing the lights and then to use standard matrix simplification techniques to determine which buttons to press. It runs in polynomial time and does not require any backtracking.

I have an implementation of this algorithm that includes a mathematical description of how it works available on my personal site. I hope you find it useful!

Edit: If you are forced to use backtracking, you can use the following facts to do so:

  • Any solution will never push the same button twice, since doing so would cancel out a previous move.
  • Any solution either pushes the first button or does not.

Given this approach, you could solve this using backtracking using a simple recursive algorithm that keeps track of the current state of the board and which buttons you’ve already made decisions about:

  • If you’ve decided about each button, then return whether the board is solved or not.
  • Otherwise:
    • Try pushing the next button and seeing if the board is recursively solvable from there.
    • If so, return success.
    • Otherwise, try not pushing the next button and seeing if the board is recursively solvable from there.
    • If so, return success. If not, return failure.

This will explore a search space of size 225, which is about 32 million. That’s big, but not insurmountably big.

Hope this helps!

More Related Contents:

  1. generate all partitions of a set [closed]
  2. Apply Quicksort to the list M,E,R,G,E,S,O,R,T
  3. How to determine if a point is in a 2D triangle? [closed]
  4. Data structures for loaded dice?
  5. Writing your own square root function
  6. How to determine if a linked list has a cycle using only two memory locations
  7. Computing set intersection in linear time?
  8. Best word wrap algorithm? [closed]
  9. Finding closest neighbour using optimized Levenshtein Algorithm
  10. Best Compression algorithm for a sequence of integers
  11. Euler project #18 approach
  12. How to calculate the index (lexicographical order) when the combination is given
  13. What algorithm for a tic-tac-toe game can I use to determine the “best move” for the AI?
  14. K-means algorithm variation with equal cluster size
  15. Quicksort superiority over Heap Sort
  16. Best way of calculating n choose k?
  17. Why DFS and not BFS for finding cycle in graphs
  18. Finding multiple entries with binary search
  19. Painter puzzle – algorithmic estimation from first principles
  20. Polynomial time and exponential time
  21. Given a number, find the next higher number which has the exact same set of digits as the original number
  22. The best shortest path algorithm
  23. Algorithm for permutations of operators and operands
  24. Algorithm for merging two max heaps?
  25. Unbiased random number generator using a biased one
  26. Why is vector array doubled?
  27. maximum subarray of an array with integers [duplicate]
  28. Can brute force algorithms scale?
  29. Find XOR of all numbers in a given range
  30. Best algorithm for matching colours.

Leave a Comment