Найти все комбинации 3х3 дырокола

Question

Найти все комбинации 3х3 дырокола

Я был на карнавале, где в каждой локации они отмечали вашу программу специальным дыроколом. Перфоратор представляет собой сетку из 3х3 пробелов. В каждом месте есть либо булавка, которая прокалывает вашу бумагу, либо ее нет. Это заставило меня задуматься о том, сколько разных шаблонов вы можете сделать с помощью этого инструмента. Моей первой мыслью было: 2^9 = 512, но все 9 пробелов без булавок на самом деле не удар, так что на самом деле: 511.

Тогда сложность ударил меня. Тем более, что рабочие не так уж и осторожны, когда бьют в бумагу, все это выглядит одинаково:

x..  .x.  ...  etc.
.x.  x..  .x.
...  ...  ..x

Вопрос: Как можно написать тест для учета вращения и сдвига?

Трудолюбие и мысли пока:

Двоичный файл ощущается как очевидная часть этого уравнения
Когда уникальный образец найден, сохраните его в памяти, чтобы будущие образцы могли быть проверены против него
Есть 4 варианта вращения.
Редактировать: то, что я имею в виду под "поворотами", это то, что вы можете принять любую форму и повернуть ее на 90 градусов. Рассмотрите образец, который является точкой в верхнем левом углу. Вы можете повернуть / повернуть его на 90 градусов и получить точку в правом верхнем углу. Сделайте это снова, и это в правом нижнем углу. Снова и это в левом нижнем углу. Используя чистый расчет 2 ^ 9, это 4 разные комбинации. Для этой проблемы, однако, именно такие дубликаты я пытаюсь отсеять.
Для каждого поворота существует 25 способов перекрытия сетки 3х3:

Перекрытия:

/ = the spaces in the new one to test
\ = the spaces in a verified unique one

1               2               25
/ / / . . . .   . / / / . . .   . . . . . . .
/ / / . . . .   . / / / . . .   . . . . . . .
/ / X \ \ . .   . / X X \ . .   . . \ \ \ . .
. . \ \ \ . .   . . \ \ \ . .   . . \ \ \ . .
. . \ \ \ . .   . . \ \ \ . .   . . \ \ X / /
. . . . . . .   . . . . . . .   . . . . / / /
. . . . . . .   . . . . . . .   . . . . / / /

Перекрытие не нужно проверять, если какой-либо шаблон содержит вывод, который не находится в области перекрытия. Побитовое И может помочь здесь.
Если вы сделаете каждую позицию для каждого из 2 шаблонов в строки, вы можете просто проверить на равенство
Можно ли объединить эти две предыдущие идеи для повышения эффективности?

37

algorithm combinations

Источник

user356 04 окт '11 в 20:05

7 ответов

Решение

Мое решение: 116 уникальных форм

При проверке двух форм на равенство сравнение количества выводов экономит много времени. Но моим самым большим прорывом было осознание того, что все эти 25 позиций могут быть заменены следующим образом: для каждой из двух фигур 3х3, которые нужно проверить на равенство, объедините линии с двумя нулями, а затем обрежьте начальные и конечные нули. Конкат нули должны предотвращать закручивание. Пример:

010 => 01000 => 0100010100000 => 1000101
101    10100
000    000

000 => 00000 => 0000001000101 => 1000101
010    01000
101    101

Затем просто проверьте результаты на равенство. Это 4 простых итерации (1 на каждый оборот) вместо 100 (25 позиций * 4 вращения) более сложных.

Время:
только строки:

перебор, все 25 позиций на каждый оборот: 2018 мс
... 00... 00... обрезано: 75 мс
больше оптимизации: 59мс

ООП и лучшее кэширование: 17мс

3

Источник

user356 06 окт '11 в 18:48

Вы запрашиваете не количество уникальных шаблонов вплоть до перевода и поворота, а тест на конгруэнтность.

Выберите строковое представление сетки 3х3. Я выберу построчно сверху вниз. Установив бит, где пробивается соответствующее отверстие, мы можем теперь отобразить 9-битные целые числа в паттерны пробивки (и наоборот.)

Для любого конкретного представления мы можем придумать операции с битами, представляющие повороты и сдвиги. Некоторые переводы являются недопустимыми для некоторых шаблонов, так как мы хотим избежать "обтекания".

Как вращения и переводы обратимы, так и наши операции будут. Если два движения отображают шаблон от A до B, а затем от B до C, мы, безусловно, можем составить движения, чтобы сделать преобразование, переводящее A в C. Ничего не делать (преобразование идентичности) также допустимо, поэтому мы можем достичь A из A. Достижимость следовательно, преобразование - это отношение эквивалентности на шаблонах перфорации, и поэтому эквивалентные шаблоны разделяют пространство.

Имея возможность присваивать положительный целочисленный балл каждому шаблону перфорации, мы можем использовать упорядоченный принцип: класс эквивалентности, содержащий паттерн, будет содержать уникальный паттерн (включая переводы и повороты) наименьшего балла. Мы выберем этот наименьший образец, чтобы он был представителем класса эквивалентности. Если два шаблона имеют одинаковый представитель класса эквивалентности, они обязательно совпадают. Если они этого не делают, они обязательно не совпадают.

Учитывая шаблон, как мы можем найти его представителя с наименьшим весом? По проверке, жадные алгоритмы не гарантированно работают. Мы можем обратиться к одному из многочисленных эвристических алгоритмов оптимизации или заметить, что мы только перемещаемся в 9 бит и исчерпывающе ищем пространство. Следует отметить, что по той же причине это прекрасно подходит для того, чтобы быть вычисленным один раз, а потом помещенным в таблицу поиска навсегда.

Вот исчерпывающий поиск. Обратите внимание, что при правильном кэшировании это все еще довольно быстро (менее секунды).

#!/usr/bin/env ruby

require 'set'

class PunchPattern < String
  @@representatives = Hash.new do |h, k|
    equivalence_class = k.closure
    representative = equivalence_class.min

    k.closure.each do |node|
      h[node] = representative
    end

    representative
  end

  def initialize(s)
    raise "9 digits of 0 and 1, pls" unless s =~ /[01]{9}/
    super
  end

  def left
    return nil unless self =~ /0..0..0../
    PunchPattern.new([self[1...3], 0, self[4...6], 0, self[7...9], 0].join)
  end

  def right
    return nil unless self =~ /..0..0..0/
    PunchPattern.new([0, self[0...2], 0, self[3...5], 0, self[6...8]].join)
  end

  def up
    return nil unless self =~ /000....../
    PunchPattern.new([self[3...9], 0, 0, 0].join)
  end

  def down
    return nil unless self =~ /......000/
    PunchPattern.new([0, 0, 0, self[0...6]].join)
  end

  def turn
    PunchPattern.new([2, 5, 8, 1, 4, 7, 0, 3, 6].collect { |i| self[i].chr }.join)
  end

  def closure
    seen = Set.new([])
    frontier = Set.new([self])

    until frontier.empty?
      node = frontier.first
      frontier.delete(node)
      seen.add(node)

      %w{left right up down turn}.collect do |motion|
        node.send motion
      end.compact.each do |neighbor|
        frontier.add(neighbor) unless seen.include? neighbor
      end
    end

    seen
  end

  def representative
    self.class.representatives[self]
  end

  def self.representatives
    @@representatives
  end

end

(0...512).collect do |p|
  p = PunchPattern.new(p.to_s(2).rjust(9, '0'))
  [p.representative, p]
end.inject(Hash.new { |h, k| h[k] = [] }) do |h, pair|
  h[pair.first] << pair.last
  h
end.sort_by { |pair| pair.first }.each do |representative, patterns|
  puts patterns.collect { |p| p[0...3] + " " }.join
  puts patterns.collect { |p| p[3...6] + " " }.join
  puts patterns.collect { |p| p[6...9] + " " }.join
  puts
end

puts "#{PunchPattern.representatives.values.uniq.size} total congruence classes"

Производит

$ ./congruence.rb 
000 
000 
000 

000 000 000 000 000 000 001 010 100 
000 000 000 001 010 100 000 000 000 
001 010 100 000 000 000 000 000 000 

000 000 000 000 000 000 000 001 010 011 100 110 
000 000 001 010 011 100 110 001 010 000 100 000 
011 110 001 010 000 100 000 000 000 000 000 000 

000 000 001 010 100 101 
000 101 000 000 000 000 
101 000 001 010 100 000 

000 000 001 010 100 111 
000 111 001 010 100 000 
111 000 001 010 100 000 

000 000 000 000 001 010 010 100 
001 010 010 100 010 001 100 010 
010 001 100 010 000 000 000 000 

000 000 000 000 000 000 000 000 001 010 010 011 011 100 110 110 
001 010 010 011 011 100 110 110 011 011 110 001 010 110 010 100 
011 011 110 001 010 110 010 100 000 000 000 000 000 000 000 000 

000 001 010 100 
001 100 000 000 
100 000 001 010 

000 000 001 010 011 100 101 110 
001 101 101 000 000 000 100 000 
101 100 000 011 001 110 000 010 

000 000 001 010 010 011 100 100 
001 011 110 001 010 100 010 100 
110 100 000 001 001 000 010 010 

000 000 001 010 011 100 110 111 
001 111 111 010 001 100 010 100 
111 100 000 011 001 110 010 000 

000 000 001 010 010 010 100 101 
010 101 010 001 100 101 010 010 
101 010 001 010 010 000 100 000 

000 000 001 010 010 010 100 111 
010 111 011 011 110 111 110 010 
111 010 001 010 010 000 100 000 

000 000 011 110 
011 110 011 110 
011 110 000 000 

000 000 010 011 011 100 101 110 
011 101 001 010 101 010 110 100 
101 110 011 001 000 110 000 010 

000 010 011 100 
011 011 110 110 
110 001 000 010 

000 000 010 011 011 100 110 111 
011 111 011 011 111 110 110 110 
111 110 011 001 000 110 010 000 

000 001 010 100 
100 000 000 001 
001 010 100 000 

000 000 001 001 010 010 100 110 
100 110 001 010 010 100 011 001 
011 001 010 010 100 100 000 000 

000 000 001 010 011 100 101 110 
100 101 000 000 000 101 001 000 
101 001 011 110 010 000 000 100 

000 000 001 010 011 100 110 111 
100 111 001 010 010 111 100 001 
111 001 011 110 010 000 100 000 

000 000 001 010 011 101 110 110 
101 110 010 100 001 011 010 101 
011 101 011 110 010 000 100 000 

000 011 101 110 
101 000 101 000 
101 011 000 110 

000 000 011 011 101 110 110 111 
101 111 001 010 111 010 100 101 
111 101 011 011 000 110 110 000 

000 001 010 110 
110 011 110 011 
011 010 100 000 

000 000 001 010 011 110 110 111 
110 111 011 110 011 110 111 011 
111 011 011 110 010 100 000 000 

000 011 110 111 
111 011 110 111 
111 011 110 000 

001 100 
000 000 
100 001 

001 100 101 101 
000 000 000 000 
101 101 001 100 

001 011 100 100 
000 000 001 100 
110 100 001 001 

001 100 101 111 
000 100 001 000 
111 101 001 100 

001 001 100 110 
001 100 000 000 
100 100 011 001 

001 100 101 111 
001 000 100 000 
101 111 100 001 

001 011 100 110 
001 100 100 001 
110 100 011 001 

001 100 111 111 
001 100 001 100 
111 111 001 100 

001 100 
010 010 
100 001 

001 100 101 101 
010 010 010 010 
101 101 001 100 

001 011 100 100 
010 010 011 110 
110 100 001 001 

001 100 101 111 
010 110 011 010 
111 101 001 100 

001 001 100 110 
011 110 010 010 
100 100 011 001 

001 100 101 111 
011 010 110 010 
101 111 100 001 

001 011 100 110 
011 110 110 011 
110 100 011 001 

001 100 111 111 
011 110 011 110 
111 111 001 100 

001 010 100 101 
100 000 001 000 
001 101 100 010 

001 010 010 100 
100 001 100 001 
010 100 001 010 

001 010 101 110 
100 100 001 001 
011 101 010 100 

001 101 101 110 
100 000 001 000 
101 011 100 101 

001 011 100 110 
100 001 001 100 
110 100 011 001 

001 101 110 111 
100 001 100 001 
111 011 101 100 

001 010 100 111 
101 000 101 000 
001 111 100 010 

001 010 010 110 
101 100 101 001 
010 011 100 010 

001 010 110 111 
101 100 101 001 
011 111 100 010 

001 110 
101 000 
100 011 

001 101 110 111 
101 101 000 000 
101 100 111 011 

001 011 110 110 
101 101 001 100 
110 100 011 011 

001 110 111 111 
101 100 001 101 
111 111 011 100 

001 010 100 101 
110 010 011 010 
001 101 100 010 

001 010 010 100 
110 011 110 011 
010 100 001 010 

001 010 101 110 
110 110 011 011 
011 101 010 100 

001 101 101 110 
110 010 011 010 
101 011 100 101 

001 011 100 110 
110 011 011 110 
110 100 011 001 

001 101 110 111 
110 011 110 011 
111 011 101 100 

001 010 100 111 
111 010 111 010 
001 111 100 010 

001 010 010 110 
111 110 111 011 
010 011 100 010 

001 010 110 111 
111 110 111 011 
011 111 100 010 

001 110 
111 010 
100 011 

001 101 110 111 
111 111 010 010 
101 100 111 011 

001 011 110 110 
111 111 011 110 
110 100 011 011 

001 110 111 111 
111 110 011 111 
111 111 011 100 

010 011 100 101 
001 100 001 100 
101 001 110 010 

010 010 011 100 
001 101 100 101 
110 001 010 010 

010 011 100 111 
001 101 101 100 
111 001 110 010 

010 011 100 101 
011 110 011 110 
101 001 110 010 

010 010 011 100 
011 111 110 111 
110 001 010 010 

010 011 100 111 
011 111 111 110 
111 001 110 010 

010 
101 
010 

010 010 011 110 
101 101 101 101 
011 110 010 010 

010 011 101 110 
101 100 101 001 
101 011 010 110 

010 011 110 111 
101 101 101 101 
111 011 110 010 

010 
111 
010 

010 010 011 110 
111 111 111 111 
011 110 010 010 

010 011 101 110 
111 110 111 011 
101 011 010 110 

010 011 110 111 
111 111 111 111 
111 011 110 010 

011 100 101 101 
000 001 000 100 
101 101 110 001 

011 100 
000 101 
110 001 

011 100 101 111 
000 101 101 000 
111 101 001 110 

011 100 101 111 
001 001 100 100 
101 111 110 001 

011 011 100 110 
001 100 101 101 
110 110 011 001 

011 100 111 111 
001 101 100 101 
111 111 110 001 

011 100 101 101 
010 011 010 110 
101 101 110 001 

011 100 
010 111 
110 001 

011 100 101 111 
010 111 111 010 
111 101 001 110 

011 100 101 111 
011 011 110 110 
101 111 110 001 

011 011 100 110 
011 110 111 111 
110 110 011 001 

011 100 111 111 
011 111 110 111 
111 111 110 001 

011 101 101 110 
100 001 100 001 
101 110 011 101 

011 101 110 111 
100 101 101 001 
111 011 101 110 

011 101 110 111 
101 101 001 100 
101 110 111 011 

011 110 
101 101 
110 011 

011 110 111 111 
101 101 101 101 
111 111 011 110 

011 101 101 110 
110 011 110 011 
101 110 011 101 

011 101 110 111 
110 111 111 011 
111 011 101 110 

011 101 110 111 
111 111 011 110 
101 110 111 011 

011 110 
111 111 
110 011 

011 110 111 111 
111 111 111 111 
111 111 011 110 

101 
000 
101 

101 101 101 111 
000 001 100 000 
111 101 101 101 

101 101 111 111 
001 100 001 100 
111 111 101 101 

101 
010 
101 

101 101 101 111 
010 011 110 010 
111 101 101 101 

101 101 111 111 
011 110 011 110 
111 111 101 101 

101 111 
101 000 
101 111 

101 111 111 111 
101 001 100 101 
111 111 111 101 

101 111 
111 010 
101 111 

101 111 111 111 
111 011 110 111 
111 111 111 101 

111 
101 
111 

111 
111 
111 

117 total congruence classes

..для 117 классов.

2

Источник

user580412 07 окт '11 в 23:28

Во-первых, мы можем рассматривать два удара, которые эквивалентны, за исключением перевода, как вращения друг друга. Представьте, что рисунок перфорации находится на поверхности сферы: мы можем "перевести" его, вращая сферу вдоль горизонтальной и вертикальной осей (как это происходит в нашей руке).

Два удара, которые эквивалентны вращению (например, поворот на 90 градусов), также фиксируются здесь, когда мы вращаем нашу сферу вдоль третьей, оставшейся оси.

Теперь мы сократили проблему до "Сколько уникальных шаблонов ударов существует на поверхности сферы, вплоть до вращения?" Для подсчета уникальных объектов с точностью до симметрии вам нужна лемма не-Бернсайда. Эта книга - хороший учебник.

1

Источник

user580412 04 окт '11 в 23:15

Я не думаю, что это похоже на случай сферы, так как вы не можете вращаться по краям? IE:

XOO
XXO
XOO

это не то же самое, что

OOX
XOX
OOX

Я попробовал считать на бумаге, чтобы увидеть, что я получил. Рассмотрим случай 2x2 - у вас есть 1 с 0 точками, 1 с 1 точкой, 2 с 2 точками (смежные или диагональные), 1 с 3 точками и 1 с 4; всего 5 (или 4, если вы пренебрегаете пустым регистром). Обратите внимание, что перечисление симметрично, так как оно такое же, чтобы считать пустые места как полные. Для случая 3х3 я получил это:

C(0) = 1
C(1) = 1
C(2) = 5
C(3) = 10
C(4) = 21

а затем по симметрии, 21, 10, 5, 1, 1

Я получаю 76. Я мог очень легко ошибиться, особенно в случае 4/5.

Единственный способ, которым я могу придумать их автоматическое перечисление, - это смещение и поворот шаблонов, чтобы увидеть, соответствуют ли они ранее перечисленному. Сдвиг сложен, так как вы можете сдвигаться только до тех пор, пока не столкнетесь с краем.

1

Источник

user914705 04 окт '11 в 23:50

Стоит отметить, что если вам действительно нужно, чтобы каждая фигура "выглядела" уникально, независимо от того, как она повернута или смещена, у вас будет очень мало выбора. Например, один удар, независимо от того, где он находится в сетке, всегда будет выглядеть одинаково. Кроме того, если принять квадратную сетку и круглые штифты и предположить, что незначительные разности расстояний (√2) незначительны, то 2 диагональных отверстия в ряду будут выглядеть так же, как два соседних штыря, так как все, что видит зритель, это 2 отверстия близко друг к другу. Аналогично, 3 по диагонали будут выглядеть как 3 по прямой линии, что резко ограничивает ваши возможности.

Обратите внимание, что форма - это, вероятно, лучшее слово для того, что мы ищем, чем комбинация, так как нас не волнует, какой была фактическая комбинация, а только то, какая результирующая форма на бумаге.

Я думаю, что мы можем утверждать, что независимо от формы, его можно поворачивать и сдвигать так, чтобы левый верхний штифт был перфорирован (особенно если вы разрешаете вращение на 45 градусов), что позволяет нам сузить наш поиск еще дальше. Мы выполняем это, используя следующие правила:

Если какой-либо угол перфорирован, поворачивайте сетку, пока перфорированный угол не окажется в верхнем левом углу.
В противном случае сдвиньте паттерн как можно выше вверх и влево.
Повторите шаг 1
Если мы зайдем так далеко, то мы знаем, что перфорируется только верхняя средняя позиция (поскольку мы знаем, что ни один из углов не является), и в этом случае мы поворачиваем шаблон на 45 градусов, делая верхнюю середину теперь левой верхней. QED.

Я выполнил очень быстрый поиск возможных форм с помощью ручного и бумажного перебора, и оказалось, что список жизнеспособных вариантов настолько мал, что их можно перечислить всего за несколько минут.

1

Источник

user86060 05 окт '11 в 07:12

Я не совсем понимаю эту часть о вращениях, но для этого сценария:

Есть 3x3=9 лунок и 10 случаев, и каждый раз может иметь место только один случай:

Case 1 = no holes
Case 2 = one hole
...
Case 10 = 9 holes

Тогда это будет выглядеть так с формулой комбинации C(n,k):

Всего = C(9,0)+C(9,1)+....+C(9,9)

это для суммирования k различных комбинаций из n элементов.

Тотол = 1+9+36+84+126+126+84+36+9+1 = 512

Я думаю, что вы правы, 512, кажется, является правильным, и теоретически без булавки также определяется как комбинация, если вы не хотите, чтобы это просто удалили, чтобы получить 511.

Все эти случаи происходят отдельно, поэтому мы добавляем разные случаи.

Если бы они происходили синхронно, например, при расчете комбинаций для 3 сотрудников, пробивающих бумагу один раз, или при расчете комбинаций для маркировки бумаги 3 раза одним сотрудником, то это усложняется и должно составлять 512 * 512 * 512 по правилу nxm.

Правило m*n на простом дисплее:

У меня 4= м карманов и две =n рук:

my_left * 4 (карманы)=4 my_right * 4(карманы) = 4
всего = 4+4=4*2=m*n

Только одна рука может войти в карман за раз, или только одна комбинация одного сотрудника в паре с только одной комбинацией другого сотрудника, и именно поэтому мы принимаем правило m*n.

Это то, что я думаю, я не математик и не претендую на 100% правильность, это только то, что я помню из курса вероятностей.

Я не претендую на 100% правильность, это то, что я помню для вероятностного курса.

Что касается перекрытия шаблонов, проверки того, что шаблон уже найден и т. Д., Я бы не стал беспокоиться, поскольку в псевдокоде так много алгоритмов, которые генерируют комбинации. Так как они генерируют, то нет необходимости проверять совпадения или что-либо еще.

В конце концов, это означает, что Generat предназначен априори, чтобы найти все результаты, просто дайте ему поработать.

Однажды я нашел еще более редкий алгоритм, чем простые комбинации, и когда я переключил его на php, он отлично справился с работой, не нужно было беспокоиться о совпадениях или чем-то еще.

0

Источник

user642173 04 окт '11 в 23:05

Другие вопросы по тегам algorithm combinations

user923873 05 окт '11 в 04:39 2011-10-05 04:39 · Accepted Answer · 2011-10-05 04:39

Нам нужно учитывать только шаблоны, которые имеют штампы в первой строке и столбце. Если первая строка пуста, шаблон можно сместить вверх. Если первый столбец пуст, шаблон можно сместить влево. В любом случае мы можем получить аналогичную модель, которую мы рассматриваем.

Для этих шаблонов нам нужно проверить, идентичны ли повернутые версии. Мы делаем это, применяя до трех поворотов на 90 градусов, возможно, смещая влево, чтобы удалить ведущие пустые столбцы (первая строка никогда не бывает пустой) и находя шаблон с наименьшим числовым значением.

Затем мы можем добавить это значение в хэш-набор, который будет хранить только уникальные значения.

Пустой шаблон не включен, потому что все его строки пусты.

Чтобы реализовать это, мы кодируем шаблоны как последовательные биты:

012
345
678

Операции, которые нам понадобятся, в основном очень просты:

Test for an empty row:    (n & 7) == 0     // bits 0,1,2 not set
Test for an empty column: (n & 73) == 0    // bits 0,3,6 not set
Shift pattern up:         n -> (n >> 3)
Shift pattern left:       n -> (n >> 1)

Самая сложная часть - это вращение, которое на самом деле просто переставляет все биты:

n -> ((n & 1) << 2) + ((n & 2) << 4) + ((n & 4) << 6)
   + ((n & 8) >> 2) + (n & 16) + ((n & 32) << 2)
   + ((n & 64) >> 6) + ((n & 128) >> 4) + ((n & 256) >> 2);

В C#:

public static int Count3x3() {
    HashSet<int> patterns = new HashSet<int>();
    for (int i = 0; i < 512; i++) {
        if ((i & 7) == 0 || (i & 73) == 0)
            continue;
        int nLowest = i;
        int n = i;
        do {
            nLowest = Math.Min(nLowest, n);
            n = ((n & 1) << 2) + ((n & 2) << 4) + ((n & 4) << 6)
                + ((n & 8) >> 2) + (n & 16) + ((n & 32) << 2)
                + ((n & 64) >> 6) + ((n & 128) >> 4) + ((n & 256) >> 2);
            while ((n & 73) == 0)
                n >>= 1;
        } while (n != i);
        patterns.Add(nLowest);
    }
    return patterns.Count;
}

Эта функция возвращает 116. Время, затраченное на мою машину, составило 0,023 мс.

РЕДАКТИРОВАТЬ: Вы можете получить дополнительное 7-кратное улучшение, используя 4 наблюдения:

Мы можем использовать простой посещаемый массив вместо хеш-набора. Если образец был замечен прежде, мы не считаем это. Это также устраняет необходимость отслеживать "самый низкий" шаблон во внутреннем цикле. Если шаблон посещался, то посещался и его самый низкий повернутый шаблон.
Если у нас нет симметрии вращения на 180 градусов, то третье вращение не приведет к исходному шаблону. 4-й поворот будет, всегда, поэтому он не нужен.
Выражение вращения может быть немного упрощено.

Итак, если мы применим эти наблюдения и развернем внутренний цикл do, мы получим следующее:

static int Rotate(int n) {
    n = ((n & (1+32)) << 2) + ((n & 2) << 4) + ((n & 4) << 6)
        + ((n & (8+256)) >> 2) + (n & 16)
        + ((n & 64) >> 6) + ((n & 128) >> 4);
    while ((n & 73) == 0) 
        n >>= 1;
    return n;
}
public static int Count3x3_3() {
    bool[] visited = new bool[512];
    int count = 0, r;
    for (int i = 0; i < 512; i++) {
        if (visited[i])
            continue;
        if ((i & 7) == 0 || (i & 73) == 0)
            continue;
        count++;
        if ((r = Rotate(i)) == i) continue;
        visited[r] = true;
        if ((r = Rotate(r)) == i) continue;
        visited[r] = true;
        visited[Rotate(r)] = true;
    }
    return count;
}

Это работает около 3 мкс на той же машине.