4148: 【普及/提高-】四阶数独

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

四阶数独：4*4的格子，每个格子只能写1~4

要求每行、每列、四等分的正方形都正好由1~4组成

问一共有多少种填写方式？

四阶数独的一个例子

样例输入 复制

样例输出 复制

提示

#include<bits/stdc++.h>
using namespace std;
#define size 5
int a[size*size],n=4*4,ans=0;
int b1[size][5],b2[size][5],b3[size][5];  //分别记录横行、竖行、四小块 
void dfs(int x) { // 第x个空填什么
    if (x > n) { // 如果所有空已经填满
        ans++; // 增加结果数量
    return;
    }
    // 根据x计算出所在行、列、小块编号
    int row = (x - 1) / 4 + 1; // 横行编号
    int col = (x - 1) % 4 + 1; // 竖排编号
    int block = (row - 1) / 2 * 2 + (col - 1) / 2 + 1; // 小块编号
    // 枚举所填内容为i
    for (int i = 1; i <= 4; i++)
        if (b1[row][i] == 0 && b2[col][i] == 0 && b3[block][i] == 0) { // 合法性判断
            a[x] = i; // 记录放置位置
            b1[row][i] = 1; b2[col][i] = 1; b3[block][i] = 1; // 占位
            dfs(x + 1); // 下一层递归
            b1[row][i] = 0; b2[col][i] = 0; b3[block][i] = 0; // 取消占位
        }
}
int main(){
    dfs(1);
    printf("%d",ans);
	return 0;
}

来源/分类

提交提交记录统计露一手!