Jogo de chaves de Berlekamp é o jogo de tabuleiro mais nerd já feito

O jogo tem 100 lâmpadas, 10×10. Cada fileira e cada coluna possuem uma chave que apaga as lâmpadas quando está ligada e acende as lâmpadas quando está desligada. Você conseguiria apagar todas as lâmpadas?

A resposta, mesmo que você tente todas as combinações possíveis, é não. Mas de acordo com a Microsoft Research, existe uma maneira de “solucionar” o quebra-cabeça com aproximação de 1%, mesmo que o tabuleiro tenha 1 milhão de lâmpadas. O engraçado é que a solução algorítmica do quebra-cabeça (construído originalmente por Elwyn Berlekamp em 1960) pode ser usada como uma maneira de dar um bypass na programação de força bruta para a solução de problemas. Os pesquisadores da Microsoft estão mais interessados na coisa toda, mas eu estou mais interessado em como um cara qualquer conseguiu construir este totalmente excelente jogo de tabuleiro como parte de seu emprego do dia a dia, como se fosse para exibir no Show de Calouros. Bom trabalho, cara!

Eis as regras, caso você queira fazer a sua versão caseira (Phil Torrone, tá me ouvindo?):

Esta é uma réplica do jogo de chaves de Elwyn Berlekamp de 1960:
•    Matriz de 10×10 de lâmpadas
•    1 chave para cada uma das 100 lampadas
•    10 chaves que trocam o estado das lâmpadas de toda uma fileira
•    10 chaves que trocam o estado das lâmpadas de toda uma coluna

O desafio é:
•    Para qualquer configuração inicial de lâmpadas acesas, qual é o número mínimo de lâmpadas que podem estar acesas usando-se somente as chaves das fileiras e colunas para alterar o estado delas?

Para um jogador:
Objetivo:    Minimize o número de lâmpadas acesas usando somente as chaves de fileiras e colunas.

Para dois jogadores:
Objetivo:    Minimize o número de lâmpadas acesas alternando jogadas entre os jogadores 1 e 2. O jogador que não for capaz de diminuir o número total de lâmpadas acesas perde o jogo.

Jogador 1:    Só pode alterar o estado das lâmpadas das fileiras.

Jogador 2:    Só pode alterar o estado das lâmpadas das colunas.

A TechFest da Microsoft é um repositório anual de inovação e gadgets da Microsoft Research, o que significa que apesar de nada daquilo sair como produto para um futuro próximo, é em essencial o que o povo de desenvolvimento de produto usa para acrescentar recursos e características bacanas aos seus lançamentos de verdade. Fiquei lá ontem o dia todo.