모든 고유 한 크로스 워드 퍼즐 그리드 생성

Question

특정 그리드 크기 (4x4는 좋은 크기)의 모든 고유 한 크로스 워드 퍼즐 그리드를 생성하고 싶습니다. 고유하지 않은 퍼즐을 포함하여 가능한 모든 퍼즐은 격자 영역의 길이 (4x4의 경우 16)로 이진 문자열로 표현되므로 가능한 모든 4x4 퍼즐은 범위 0에있는 모든 숫자의 이진 형식으로 표시됩니다 ~ 2^16.

이러한 생성 방법은 간단하지만 유효하지 않은 중복 사례를 프로그래밍 방식으로 제거하는 방법에 대한 좋은 해결책이 있다면 궁금합니다. 예를 들어, 단일 열 또는 단일 행을 가진 모든 퍼즐은 기능적으로 동일하므로 8 가지 경우 중 7 가지를 제거합니다. 또한 십자말 퍼즐 규칙에 따르면 모든 사각형은 인접해야합니다. 모든 중복 구조를 제거해도 성공했지만 솔루션을 실행하는 데 몇 분이 걸렸으며 이상적이지는 않았습니다. 내가 contiguity을 감지하는 방법에 대한 손실의 무언가에있어 만약 누군가가 이것에 대한 아이디어를 가지고 있다면 그것은 많이 감사 할 것입니다.

나는 파이썬으로 솔루션을 선호하지만 선호하는 언어로 작성합니다. 누구든지 원한다면 파이썬 코드를 게시하여 모든 그리드를 생성하고 중복을 제거 할 수 있습니다.

Answer 1

면책 조항 : 대부분의 테스트가 모두 테스트되지 않은 경우 은 일부 그리드를 필터링하여 영향을 미치며 몇 가지 발견 된 오류가 수정되었습니다. 확실하게 최적화 될 수 있습니다.

def is_valid_grid (n): 
    row_mask = ((1 << n) - 1) 
    top_row = row_mask << n * (n - 1) 

    left_column = 0 
    right_column = 0 

    for row in range (n): 
     left_column |= (1 << (n - 1)) << row * n 
     right_column |= 1 << row * n 

    def neighborhood (grid): 
     return (((grid & ~left_column) << 1) 
       | ((grid & ~right_column) >> 1) 
       | ((grid & ~top_row)  << n) 
       | (grid     >> n)) 

    def is_contiguous (grid): 
     # Start with a single bit and expand with neighbors as long as 
     # possible. If we arrive at the starting grid then it is 
     # contiguous, else not. 
     part = (grid^(grid & (grid - 1))) 
     while True: 
      expanded = (part | (neighborhood (part) & grid)) 
      if expanded != part: 
       part = expanded 
      else: 
       break 

     return part == grid 

    def flip_y (grid): 
     rows = [] 
     for k in range (n): 
      rows.append (grid & row_mask) 
      grid >>= n 

     for row in rows: 
      grid = (grid << n) | row 

     return grid 

    def rotate (grid): 
     rotated = 0 
     for x in range (n): 
      for y in range (n): 
       if grid & (1 << (n * y + x)): 
        rotated |= (1 << (n * x + (n - 1 - y))) 

     return rotated 

    def transform (grid): 
     yield flip_y (grid) 

     for k in range (3): 
      grid = rotate (grid) 
      yield grid 
      yield flip_y (grid) 

    def do_is_valid_grid (grid): 
     # Any square in the topmost row? 
     if not (grid & top_row): 
      return False 

     # Any square in the leftmost column? 
     if not (grid & left_column): 
      return False 

     # Is contiguous? 
     if not is_contiguous (grid): 
      return False 

     # Of all transformations, we pick only that which gives the 
     # smallest number. 
     for transformation in transform (grid): 
      # A transformation can produce a grid without a square in the topmost row and/or leftmost column. 
      while not (transformation & top_row): 
       transformation <<= n 

      while not (transformation & left_column): 
       transformation <<= 1 

      if transformation < grid: 
       return False 

     return True 

    return do_is_valid_grid 

def valid_grids (n): 
    do_is_valid_grid = is_valid_grid (n) 
    for grid in range (2 ** (n * n)): 
     if do_is_valid_grid (grid): 
      yield grid 

for grid in valid_grids (4): 
    print grid