证明一个 n x n 的正方形可以用 3x1 的平板和一个 1x1 的平板平铺（分而治之）

Question

如果我有一块尺寸为 3m x 1m 的木板，如果 n 可以被 3 整除，那么木板可以用这种板铺设任何 n x n 的房间。对于每个 n> 3 不能被3、这样的板和一块1m x 1m的板可以平铺一个n x n的正方形吗？我知道这是可能的。但是，如何使用分而治之来证明这一点？

我举个例子来说明。如果我有一个 4x4 的房间，我可以用 3x1 的木板和一个 1x1 的木板把整个房间都铺上瓷砖。

Answer 1

你可以全部覆盖。抱歉没有画图，可惜我没有工具

设边 K 为正方形

a/ 如果 K = 3n + 1 那么我们将正方形分成左上角的 3n x 3n 正方形、垂直的 3n x 1 矩形、水平的 3n x 1 矩形和右下角的 1 x 1 正方形

b/ 如果 K = 3n+2（并且 n>0），那么我们沿着顶部（从 KxK 正方形的左侧开始）将正方形分成一个 2 x 3n 的矩形，沿着右侧（从 KxK 正方形的顶部开始）、底部的 2 x 3n 矩形（从 KxK 的右侧开始）和左侧的 3n x 2 矩形（从 KxK 的底部开始），留下一个 3n+2-4 边的中心正方形。但是 3n+2-4 = 3n-2 = 3(n-1)+1 所以通过 a/ 我们可以覆盖它。

Answer 2

However, how can I prove this using divide and conquer?

当n大于5时，只需填满底下3行右3列，然后求解剩余的n-3方格即可。

. . . . . .  A A A
. . . . . .  B B B
. . . . . .  C C C
. . . . . .  D D D
. . . . . .  E E E
. . . . . .  F F F

a b c d e f  x y z
a b c d e f  x y z
a b c d e f  x y z

只需要解决n==3, 4, 5

3,4,5 的递归思路很简单：在正方形的每个方块处，如果方块为空且适合水平或垂直条，则放置它并递归。然后不适当的酒吧和尝试下一个广场。

如果没有空方块，则成功！

警告代码中有一两个错误

为了不泄露答案，我留下了一些错误。仔细阅读应该可以找到它们。

下面的效率不高，但完成了 3、4、5 的工作。

void tile3_print(int n, char square[n][n]) {
  puts("");
  for (int row = 0; row < n; row++) {
    for (int col = 0; col < n; col++) {
      printf("%c ", square[row][col] ? square[row][col] : ' ');
    }
    printf("\n");
  }
  fflush(stdout);
}

bool tile3_helper(int n, char square[n][n], char ch) {
  //tile3_print(n, square);
  assert(ch <= 127);
  bool all_squares_marked = true;
  for (int row = 0; row < n; row++) {
    for (int col = 0; col < n; col++) {
      if (square[row][col] == 0) {
        all_squares_marked = false;
        if (col + 2 < n && square[row][col + 1] == 0
            && square[row][col + 2] == 0) {
          square[row][col] = square[row][col + 1] = square[row][col + 2] = ch;
          bool success = tile3_helper(n, square, (char) (ch + 1));
          square[row][col] = square[row][col + 1] = square[row][col + 2] = 0;
          if (success) {
            return true;
          }
        }
        if (row + 2 < n && square[row + 1][col] == 0
            && square[row + 2][col] == 0) {
          square[row][col] = square[row + 1][col] = square[row + 2][col] = ch;
          bool success = tile3_helper(n, square, (char) (ch + 1));
          square[row][col] = square[row + 1][col] = square[row + 1][col] = 0;
          if (success) {
            return true;
          }
        }
      }
    }
  }
  if (all_squares_marked) {
    tile3_print(n, square);
  }
  return all_squares_marked;
}

bool tile3_helper1(int n, char square[n][n], char ch) {
  bool all_sqaures_marked = true;
  for (int row = 0; row < n; row++) {
    for (int col = 0; col < n; col++) {
      all_sqaures_marked = false;
      square[row][col] = ch;
      if (tile3_helper(n, square, (char) (ch + 1))) {
        return true;
      }
      square[row][col] = 0;
    }
  }
  return all_sqaures_marked;
}

bool tile3(int n) {
  assert(n >= 3);
  char square[n][n];
  memset(square, 0, sizeof square);
  bool success = n % 3 ? tile3_helper1(n, square, 'A') : //
                         tile3_helper(n, square, 'A');
//  tile3_print(n, square);
  return success;
}

int main(void) {
  for (int i = 3; i < 7; i++) {
    int success = tile3(i);
    printf("Success %d = %d\n", i, success);
  }
}

输出（修正后的代码）

A A A 
B B B 
C C C 
Success 3 = 1

A B B B 
C C C D 
E E E D 
F F F D 
Success 4 = 1

B B B C D 
E E E C D 
F G A C D 
F G H H H 
F G I I I 
Success 5 = 1

证明一个 n x n 的正方形可以用 3x1 的平板和一个 1x1 的平板平铺（分而治之）

Prove an n x n square can be tiled with 3x1 slabs and one 1x1 slab (divide and conquer)

algorithm

divide-and-conquer