각 열을 비트 정수로 표현한다. 비트 은 흰색, 비트 은 파란색을 뜻한다.
먼저 같은 색이 세 칸 연속하는 구간이 없는 열 마스크만 남긴다. 이러한 마스크의 집합을 , 크기를 라고 하자. 에서 이다. 각 열마다 이미 색칠된 칸과 일치하는 마스크만 선택할 수 있다.
가로 조건을 판정하려면 마지막 두 열만 기억하면 된다. 를 현재까지 색칠했을 때 끝의 두 열 마스크가 인 경우의 수로 정의한다. 새로운 열 를 붙일 때, 모든 행에서 의 해당 비트 세 개가 모두 같지 않아야 한다. 가능한 경우 에 를 더한다. 모든 계산은 로 나눈 나머지로 수행한다.
이면 첫 열에 놓을 수 있는 마스크의 개수를 센다. 그렇지 않으면 처음 두 열에 놓을 수 있는 모든 마스크 쌍으로 DP를 초기화한다. 세 번째 열부터 전이를 적용하고, 마지막에 모든 상태를 합한다.
열 마스크를 구하는 데 , 허용 여부를 계산하는 데 , DP에 시간이 걸린다. 메모리 사용량은 전이를 미리 저장하면 이다. 필요한 덧셈은 항상 두 개의 나머지 사이에서만 이루어지므로 32비트 부호 있는 정수 범위 안에 있다.
