[c#] 비트 연산의 실제 적용 [닫기]

나는 당신이 생각하는 스도쿠를 해결하는 것이 얼마나 실용적인지 모르겠지만 그것이 있다고 가정합시다.

보드를 보여주고 퍼즐을 직접 풀 수 있지만 동작이 합법적인지 확인하는 스도쿠 해결사 또는 단순한 프로그램을 작성하고 싶다고 상상해보십시오.

보드 자체는 아마도 다음과 같은 2 차원 배열로 표현 될 것입니다.

uint [, ] theBoard = new uint[9, 9];

값 0은 셀이 여전히 비어 있고 [1u, 9u] 범위의 값이 보드의 실제 값임을 의미합니다.

이제 어떤 움직임이 합법적인지 확인하고 싶다고 상상해보십시오. 분명히 몇 개의 루프로 할 수 있지만 비트 마스크를 사용하면 작업을 훨씬 빠르게 할 수 있습니다. 규칙을 준수하는 단순한 프로그램에서는 중요하지 않지만 솔버에서는 가능합니다.

각 행, 각 열 a 및 각 3×3 상자에 이미 삽입 된 숫자에 대한 정보를 저장하는 비트 마스크 배열을 유지할 수 있습니다.

uint [] maskForNumbersSetInRow = new uint[9];

uint [] maskForNumbersSetInCol = new uint[9];

uint [, ] maskForNumbersSetInBox = new uint[3, 3];

숫자 세트에 해당하는 1 비트를 사용하여 숫자에서 비트 패턴으로의 매핑은 매우 간단합니다.

1 -> 00000000 00000000 00000000 00000001
2 -> 00000000 00000000 00000000 00000010
3 -> 00000000 00000000 00000000 00000100
...
9 -> 00000000 00000000 00000001 00000000

C #에서는 다음과 같이 비트 패턴을 계산할 수 있습니다 ( valueis an uint).

uint bitpattern = 1u << (int)(value - 1u);

위의 줄 1u에서 비트 패턴에 해당하는 것은 00000000 00000000 00000000 00000001왼쪽으로 이동합니다 value - 1. 예를 들어 value == 5다음과 같은 경우

00000000 00000000 00000000 00010000

처음에 각 행, 열 및 상자의 마스크는 0입니다. 보드에 숫자를 입력 할 때마다 마스크를 업데이트하므로 새 값에 해당하는 비트가 설정됩니다.

행 3에 값 5를 삽입한다고 가정합니다 (행과 열은 0부터 번호가 매겨 짐). 행 3의 마스크는에 저장됩니다 maskForNumbersSetInRow[3]. 삽입하기 전에 이미 {1, 2, 4, 7, 9}행 3에 숫자가 있다고 가정 해 보겠습니다 . 마스크의 비트 패턴은 maskForNumbersSetInRow[3]다음과 같습니다.

00000000 00000000 00000001 01001011
bits above correspond to:9  7  4 21

목표는이 마스크의 값 5에 해당하는 비트를 설정하는 것입니다. 비트 또는 연산자 ( |)를 사용하여 수행 할 수 있습니다 . 먼저 값 5에 해당하는 비트 패턴을 만듭니다.

uint bitpattern = 1u << 4; // 1u << (int)(value - 1u)

그런 다음을 사용 operator |하여 마스크에 비트를 설정합니다.maskForNumbersSetInRow[3]

maskForNumbersSetInRow[3] = maskForNumbersSetInRow[3] | bitpattern;

또는 더 짧은 형식 사용

maskForNumbersSetInRow[3] |= bitpattern;

00000000 00000000 00000001 01001011
                 |
00000000 00000000 00000000 00010000
                 =
00000000 00000000 00000001 01011011

이제 마스크는 {1, 2, 4, 5, 7, 9}이 행 (3 행)에 값 이 있음을 나타냅니다 .

확인하고자하는 경우 행에 어떤 값이 operator &있으면 해당 비트가 마스크에 설정되어 있는지 확인하는 데 사용할 수 있습니다 . 마스크에 적용된 해당 연산자의 결과와 해당 값에 해당하는 비트 패턴이 0이 아니면 값이 이미 행에있는 것입니다. 결과가 0이면 값은 행에 없습니다.

예를 들어 값 3이 행에 있는지 확인하려면 다음과 같이 할 수 있습니다.

uint bitpattern = 1u << 2; // 1u << (int)(value - 1u)
bool value3IsInRow = ((maskForNumbersSetInRow[3] & bitpattern) != 0);

00000000 00000000 00000001 01001011 // the mask
                 |
00000000 00000000 00000000 00000100 // bitpattern for the value 3
                 =
00000000 00000000 00000000 00000000 // the result is 0. value 3 is not in the row.

다음은 보드에 새 값을 설정하고 적절한 비트 마스크를 최신 상태로 유지하고 이동이 합법적인지 확인하는 방법입니다.

public void insertNewValue(int row, int col, uint value)
{

    if(!isMoveLegal(row, col, value))
        throw ...

    theBoard[row, col] = value;

    uint bitpattern = 1u << (int)(value - 1u);

    maskForNumbersSetInRow[row] |= bitpattern;

    maskForNumbersSetInCol[col] |= bitpattern;

    int boxRowNumber = row / 3;
    int boxColNumber = col / 3;

    maskForNumbersSetInBox[boxRowNumber, boxColNumber] |= bitpattern;

}

마스크가 있으면 다음과 같이 이동이 합법적인지 확인할 수 있습니다.

public bool isMoveLegal(int row, int col, uint value)
{

    uint bitpattern = 1u << (int)(value - 1u);

    int boxRowNumber = row / 3;
    int boxColNumber = col / 3;

    uint combinedMask = maskForNumbersSetInRow[row] | maskForNumbersSetInCol[col]
                        | maskForNumbersSetInBox[boxRowNumber, boxColNumber];

    return ((theBoard[row, col] == 0) && ((combinedMask & bitpattern) == 0u);
}