"Flip all"(Light Out) 게임을위한 알고리즘?

Question

이 게임의 경우 : http://www.mathsisfun.com/games/allout.html 해결 기능을 사용하면 원본 보드를 "남용"하는 경우에도 문제를 해결할 수 있습니다. 이 게임을 해결하는 알고리즘을 알려주십시오. 나는 며칠 동안 생각하려고 노력했지만 모든 경우를 해결할 아무런 단서도 발견하지 못했습니다.

확인 후, 나는 내 질문을 확장 일부 답변과 의견을 읽고 (그리고 라이트 밖으로 게임에 잠깐 봐) :

윌 게임 다른 내가 좋아 (격자의 크기를 확장하는 경우 25x25)? 어떤 가능한 알고리즘을 케이스, 수용 할 수 시간 (< 2s) 해결할 수 있습니까?

각 노드가 게임 상태와 상태의 아이들이 그 상태 사이의 전이를 표현하는 트리 구조를 구현 : 대부분의 AI "게임"문제처럼

Answer 1

이 게임은 더 일반적으로 소등이라고 알려져 있으며, 몇 가지 표준이지만 다소 진보 된 수학을 기반으로하는 다양한 고급 솔루션을 제공합니다. 나는이 모든 것을 여기에 설명하지는 않겠지 만, 구글이 조금이라도 간단한 절차에서 선형 대수학이나 그룹 이론으로 변하는 모든 종류의 설명을 찾을 수 있다면. 몇 링크 :

http://www.hamusutaa.com/pilot/solution.html

http://www.ripon.edu/academics/macs/summation/2010/articles/M.%20Madsen%20-%20Lights%20Out.pdf

http://people.math.sfu.ca/~jtmulhol/math302/notes/24-Lights-Out.pdf

편집 : 제목 : Re : 두 번째 질문. 내가 게시 한 두 번째 링크에 제시된 알고리즘은 O (n^6) 시간에 nx n 보드를 풀 수 있습니다. 즉, 25 x 25 보드를 빨리 풀 수 있어야합니다.

Answer 2

는 일반적인 방법이있다.

너비가 큰 검색으로 보아도됩니다 (너가 본 과거 상태의 로그를 유지하고 다시 방문하기를 거부하고 최적의 솔루션을 찾는 것에 신경 쓰지 않는다면 깊이 우선). 당신이 A *를 사용할 수있는 낙관적 인 발견 적 방법을 사용하십시오. 내가 생각할 수있는 매우 끔찍한 경험주의는 "퍼즐을 이기기 위해 뒤집어 져야하는 원의 수를 5로 나눈 것"입니다. 나는 더 나은 것이 있는지 확실하지 않다. 나는 이것에 대한 사람들의 의견을 듣는 데 관심이있다. (그것은 낙관적이어야한다. 즉, 휴리스틱은 절대 필요한 움직임의 수를 절대 계산할 수 없다는 점에 유의해야한다.)

좀 더 자세히 들어가는 것은 약간 바보 같다. 이것은 매우 큰 주제이며, 게다가 너비 우선 탐색이나 A *를하는 ​​방법을 알면 아주 간단합니다.

Answer 3

이 문제를 해결하기위한 잘 알려진 방법이 있습니다. x_1, ..., x_n을 n 번째 버튼을 솔루션의 일부로 누르는 지 여부에 해당하는 변수로 놓고 a_1, ..., a_n을 초기 상태로 놓습니다. 당신은 몇 가지를 기록 할 수

a_1 a_2 a_3 
a_4 a_5 a_6 
a_7 a_8 a_9 

지금 :

의 당신이 3 × 3의 문제를 해결하고 있다고 가정 해 봅시다, 그리고 변수는 다음과 같이 설정됩니다 :

x_1 x_2 x_3 
x_4 x_5 x_6 
x_7 x_8 x_9 

을이 초기 상태입니다 솔루션이 만족해야하는 방정식 (모듈로 2)이것은 기본적으로 스위치가 특정 조명을 토글하게하는 규칙을 인코딩합니다.

a_1 = x_1 + x_2 + x_4 
a_2 = x_1 + x_2 + x_3 + x_5 
... 
a_5 = x_2 + x_4 + x_5 + x_6 + x_8 
... 
a_9 = x_6 + x_8 + x_9 

이제 가우시안 제거를 사용하여이 연립 방정식을 풀 수 있습니다. 왜냐하면 당신은 modulo 2로 계산하기 때문에, 실제로는 실수에 대한 연립 방정식보다 약간 쉽습니다. 예를 들어, 두 번째 방정식에서 x_1을 제거하려면 방정식에 첫 번째 방정식을 추가하면됩니다.

a_1 + a_2 = (x_1 + x_2 + x_4) + (x_1 + x_2 + x_3 + x_5) = x_3 + x_4 + x_5 

즉, 여기서 산술 모듈 (2)의 가우스 소거법 알고리즘이다 :

• 그것의 X_1와 방정식을 지정. 이름을 E_1로 지정하십시오.
• x_1이 포함 된 다른 모든 수식에 E_1을 추가하십시오.
• x_2, x_3, ...., x_n에 대해 반복하십시오.

이제 E_n은 x_n 만 포함하는 방정식입니다. x_n의 값을 이전 방정식으로 대체 할 수 있습니다. E_ {n-1}, ..., E_1에 대해 반복하십시오.

전체적으로 O (n^3) 연산의 문제를 해결합니다.

여기에 몇 가지 코드가 있습니다.

class Unsolvable(Exception): 
    pass 

def switches(vs): 
    n, m = len(vs), len(vs[0]) 
    eqs = [] 
    for i in xrange(n): 
     for j in xrange(m): 
      eq = set() 
      for d in xrange(-1, 2): 
       if 0 <= i+d < n: eq.add((i+d)*m+j) 
       if d != 0 and 0 <= j+d < m: eq.add(i*m+j+d) 
      eqs.append([vs[i][j], eq]) 

    N = len(eqs) 
    for i in xrange(N): 
     for j in xrange(i, N): 
      if i in eqs[j][1]: 
       eqs[i], eqs[j] = eqs[j], eqs[i] 
       break 
     else: 
      raise Unsolvable() 
     for j in xrange(i+1, N): 
      if i in eqs[j][1]: 
       eqs[j][0] ^= eqs[i][0] 
       eqs[j][1] ^= eqs[i][1] 

    for i in xrange(N-1, -1, -1): 
     for j in xrange(i): 
      if i in eqs[j][1]: 
       eqs[j][0] ^= eqs[i][0] 
       eqs[j][1] ^= eqs[i][1] 
    return [(i//m,i%m) for i, eq in enumerate(eqs) if eq[0]] 

print switches(([1, 0, 0], [0, 1, 0], [0, 0, 1], [0, 0, 0])) 

한 번에 한 행 씩 초기 상태로 지정하십시오. 모든 표시등을 끄기 위해 눌러야하는 스위치를 반환합니다.

내 랩톱에서 0.5 초 이내에 50x50 문제를 해결합니다.