Lights Out Solver Algorithm

main.go

package main

import (
	"bytes"
	"fmt"
	"os"
)

func main() {
	if len(os.Args) < 2 || len(os.Args[1]) != 25 {
		fmt.Fprintf(os.Stderr, "board must be 5x5 (25 0's and 1's)\n")
		os.Exit(1)
	}
	b := decode(os.Args[1])

	s, ok := solve(b, 0, 0)
	if !ok {
		fmt.Println("cannot be solved")
	}
	fmt.Printf("%s", encode(s))
}

func decode(s string) uint {
	var b uint
	for i, x := range s {
		if x == '1' {
			b |= 1 << uint(i)
		}
	}
	return b
}

func encode(b uint) string {
	buf := &bytes.Buffer{}
	for y := 0; y < 5; y++ {
		for x := 0; x < 5; x++ {
			pos := 5*y + x
			if b&(1<<uint(pos)) != 0 {
				buf.WriteRune('1')
			} else {
				buf.WriteRune('0')
			}
		}
		buf.WriteRune('\n')
	}
	return buf.String()
}

func solve(board, solution uint, pos int) (uint, bool) {
	// Have we reached the end of the board?
	if pos > 24 {
		return 0, false
	}

	// Is the board solved?
	if board == 0 {
		return solution, true
	}

	// Can it be solved further down without pressing it?
	if s, ok := solve(board, solution, pos+1); ok {
		return s, true
	}

	// See if pressing it produces a solution.
	p := press(board, pos)
	t := toggle(solution, pos%5, pos/5)
	if s, ok := solve(p, t, pos+1); ok {
		return s, true
	}

	// I can't solve it this way.
	return 0, false
}

func press(b uint, pos int) uint {
	// Toggle this position and all surrounding.
	x, y := pos%5, pos/5
	b = toggle(b, x, y)
	b = toggle(b, x-1, y)
	b = toggle(b, x+1, y)
	b = toggle(b, x, y-1)
	b = toggle(b, x, y+1)
	return b
}

func toggle(b uint, x, y int) uint {
	// Catch any out of range issues.
	if x < 0 || x >= 5 || y < 0 || y >= 5 {
		return b
	}
	return b ^ (uint(1) << uint(5*y+x))
}

naive.go

// This doesn't appear to be faster but it's much simpler.
func solve(board uint) (uint, bool) {
    var x uint
    for ; x < 1<<25; x++ {
        if pressAll(board, x) == 0 {
            return x, true
        }
    }
    return 0, false
}

func pressAll(b, a uint) uint {
    var x uint
    for ; x < 25; x++ {
        if a&(1<<x) != 0 {
            b = press(b, int(x))
        }
    }
    return b
}