今天做每日一题的时候刚好看到了 数独简单版 这道题。于是去翻了翻被我雪藏了很久很久的代码练习文件夹,没想到真的找到了当初的解数独程序。
当时我还在用着体积十分庞大的Visual Studio 2017,装了一大堆直到卸载也没用上的组件,(现在基本用VScode了,真香)经历了高中三年摧残之后,捡起许久未曾动过一下下的编程,当时作为初学者我急于找一种方式来”证明”一下自己,思考了许久,选择了看起来不算太难,也不需要复杂交互的数独问题。没想到一下子就掉进了坑= - =
本以为是很简单的问题(现在看来确实比较简单,但当时大脑完全没有DFS之类的概念)只能凭着自己的感觉做,于是很快就确定了通过查找每一个格子的”候选数”的方法来一格一格的求解。如果某个格子有唯一的候选数,那么这个格子一定是要填这个数,每填一个新数字,就把整个棋盘的候选数更新一遍,花了大概3天,撸了一份初版的代码,修修补补,终于能用了,兴奋的构造了一组数据,通过!然后兴奋地从网上随便找一个数独问题,程序卡死了!_ (:* 」∠) _
数独解题机初代就这么扑街了,经过深刻的反思,我认识到这样的程序是哪怕复杂一点点点的数独问题都是解决不了的。痛定思痛,痛改前非,心里憋着一股气,坚决不去搜网上现成的可以解数独的程序代码,开始搜起了解数独的方法与技巧(完全走错方向了喂(#`O′),慢慢的了解了唯余解法、区块摒除法、三链数删减法之类的手动解数独的方法,数独解题机也慢慢变成了一个大模拟程序(//̀Д/́/)
这些解法对于人类来说判断起来比较简单,但写到程序里却不那么容易,再加上当时我的代码水平实在一般(现在也是),各种BUG层出不穷,于是每天都在想如何增加新的解法以及如何修好这种找也找不到的BUG,为此我还专门在手机上安装了CIDE使得我不在电脑前的时候也能够进行编写和测试,
这样的日子过了大概半个月,因为大学的事情把这个程序搁置了几天,几天之后当我再次打开cpp文件的时候,震惊的发现:我 竟 然 一 个 变 量 也 看 不 懂 了 !由于变量命名混乱,程序框架随意,我还是写出了开发者自己都维护不了的代码,尝试了进行了理解和重构,结果越改越乱,BUG越出越多,我必须无奈的承认,可能必须重新写一份代码了。回顾半月来的种种,我最终还是放弃了这个想法。。。数独解题机最终带着还未完成的宫格摒除部分永远沉睡在了D盘。jis
尽管这算不上一个成功的程序,但它也确实成为了我加入学校软件创新实验室的一块敲门砖,于是我来到了acwing,于是我又遇到了这个数独问题,于是我去D盘唤醒了它,冥冥之中自有天意。
在这一两年的时间里我也学习了很多很有意思也很有效的算法,让我再次面对数独问题的时候,不再需要考虑各种解开数独的方法技巧,只需要简单的枚举,简单的DFS,简单的暴力,就能轻松得出答案;也不必花费大半个月的时间仅仅做出一个半成品,而是十多分钟就能写出可以解开任何9*9数独的“高效”程序。尽管如此,当绿色的ACCEPT出现时,却也再得不到当初第一次程序完整解开一个数独时的兴奋与快乐。
当我再一次遇到这个问题,我再一次拿出了数独解题机,稍作修改,点击提交,果不其然,仅能通过样例的它得到了WrongAnswer。但我并未感到失落,反而觉得很安心,仿佛一下子又变成了那个啥也不会刚刚踏入大学校门的少年。解题机的代码永远不会升级,因为它本身就成了一种回忆……
努力解题中的解题机
解题成功开心的解题机
得不出答案十分委屈的解题机
解题机的代码(长度警告)
// 数独.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <fstream>
#include <iostream>
using namespace std;
///////////////////////////////////
//全局变量声明
int date[9][9]; //全部数据
int blank[81][3]; //空快数据 //数据结构 X * Y * 区块位置
int blanknum; //空快长度(用于处理长度限制)
int canin[81][9]; //空快可行域
ofstream fout; //文件输出流
///////////////////////////////////
//结构体声明
struct XY
{
int x;
int y;
};
///////////////////////////////////
//全局函数声明
void invation();
void show();
void getin();
void setblank();
int setare(int x, int y);
void setblankare();
int getblanknum();
void setcanin();
bool ninecheck(int load, int nownum);
void update(int x, int y, int newdate);
bool inone();
bool loscheck();
void fshow();
int check();
bool arebc();
void utsetcanin(int x, int y, int date);
void liftmove(int id);
int getblankid(int x, int y);
XY getoxy(int gid);
/////////////////////////////////////////////////////////////////////////////////
/* 数独好难鸭!!!! */
/////////////////////////////////////////////////////////////////////////////////
int main()
{
invation();
getin();
setblank();
setblankare();
blanknum = getblanknum();
setcanin();
cout << endl << "数据已载入." << endl << endl;
show();
fout << "原始数据:" << endl << endl;
fshow();
// cin.get(); cin.get();
cout << endl << "开始处理...." << endl << endl;
while (true)
{
if (!(inone() || loscheck()))
{
if (!arebc())
{
if (!(inone() || loscheck()))
{
break;
}
}
}
}
cout << endl << "当前已无可用解" << endl;
switch (check())
{
case 0:
cout << "出现了错误,请检查原始数据";
break;
case 1:
cout << "程序未能完全解开该数独";
break;
case 2:
cout << "程序已完全解开该数独";
break;
case -1:
cout << "程序出现了未知错误";
break;
}
cout << endl << endl;
show();
fout << endl << endl << "已处理:" << endl << endl;
fshow();
cout << endl;
cin.get();
cin.get();
return 0;
}
//安全性初始化
void invation()
{
fout.open("out.txt");
int blanknum = 0;
for (int i = 0; i < 9; i++)
{
for (int k = 0; k < 9; k++)
{
date[i][k] = 0;
}
}
for (int i = 0; i < 81; i++)
{
for (int k = 0; k < 3; k++)
{
blank[i][k] = -1;
}
}
for (int i = 0; i < 81; i++)
{
for (int k = 0; k < 9; k++)
{
canin[i][k] = -1;
}
}
}
//数据输出
void show()
{
cout << " ";
for (int i = 0; i < 9; i++)
{
for (int k = 0; k < 9; k++)
{
if (date[i][k] == 0)
{
cout << "*";
}
else
{
cout << date[i][k];
}
cout << " ";
if (k == 2 || k == 5)
{
cout << "|"
<< " ";
}
if ((i == 2 || i == 5) && k == 8)
{
cout << endl << " ------|-------|------";
}
}
cout << endl << " ";
}
}
//结果文件输出
void fshow()
{
for (int i = 0; i < 9; i++)
{
for (int k = 0; k < 9; k++)
{
if (date[i][k] == 0)
{
fout << "*";
}
else
{
fout << date[i][k];
}
fout << " ";
if (k == 2 || k == 5)
{
fout << "|"
<< " ";
}
if ((i == 2 || i == 5) && k == 8)
{
fout << endl << "------|-------|------";
}
}
fout << endl;
}
}
//数据输入
void getin()
{
for (int i = 0; i < 9; i++)
{
for (int k = 0; k < 9; k++)
{
cin >> date[i][k];
}
}
}
//空块定位
void setblank()
{
int mun = 0;
for (int i = 0; i < 9; i++)
{
for (int k = 0; k < 9; k++)
{
if (date[i][k] == 0)
{
blank[mun][0] = i;
blank[mun][1] = k;
mun += 1;
}
}
}
}
//区块定位
int setare(int x, int y)
{
int backdate = -1;
if (y >= 0 && y <= 2)
{
if (x >= 0 && x <= 2)
{
backdate = 1;
}
if (x >= 3 && x <= 5)
{
backdate = 4;
}
if (x >= 6 && x <= 8)
{
backdate = 7;
}
}
if (y >= 3 && y <= 5)
{
if (x >= 0 && x <= 2)
{
backdate = 2;
}
if (x >= 3 && x <= 5)
{
backdate = 5;
}
if (x >= 6 && x <= 8)
{
backdate = 8;
}
}
if (y >= 6 && y <= 8)
{
if (x >= 0 && x <= 2)
{
backdate = 3;
}
if (x >= 3 && x <= 5)
{
backdate = 6;
}
if (x >= 6 && x <= 8)
{
backdate = 9;
}
}
return backdate;
}
//为空快载入定位
void setblankare()
{
for (int mun = 0; mun < 81; mun++)
{
int are = setare(blank[mun][0], blank[mun][1]);
blank[mun][3 - 1] = are;
}
}
//获取空快数量
int getblanknum()
{
int blanknum = 0;
for (int i = 0; i < 81; i++)
{
if (blank[i][0] == -1)
{
blanknum = i;
break;
}
}
return blanknum;
}
//可行域载入
void setcanin()
{
for (int load = 0; load < blanknum; load++)
{
int x = blank[load][0];
int y = blank[load][1];
for (int i = 1; i <= 9; i++)
{
bool iscan1 = true;
bool iscan2 = true;
bool iscan3 = true;
for (int k = 0; k < 9; k++)
{
if (date[x][k] == i)
{
iscan1 = false;
break;
}
}
for (int k = 0; k < 9; k++)
{
if (date[k][y] == i)
{
iscan2 = false;
break;
}
}
iscan3 = ninecheck(load, i);
if (iscan1 && iscan2 && iscan3)
{
canin[load][i - 1] = 1;
}
}
}
}
//九宫格区域的可行域判定
bool ninecheck(int load, int nownum)
{
XY t = getoxy(blank[load][2]);
int ox = t.x;
int oy = t.y;
for (int i = 0; i < 3; i++)
{
for (int k = 0; k < 3; k++)
{
int nx = ox + i;
int ny = oy + k;
if (nownum == date[nx][ny])
{
return false;
}
}
}
return true;
}
//原数据覆写及可可行域重载
void update(int x, int y, int newdate)
{
date[x][y] = newdate;
int id = getblankid(x, y);
liftmove(id);
blanknum = getblanknum();
utsetcanin(x, y, newdate);
}
//对确定解的检测和写入
bool inone()
{
for (int load = 0; load < blanknum; load++)
{
int times = 0;
int oneanser = -1;
for (int i = 0; i < 9; i++)
{
if (canin[load][i] == -1)
{
times++;
}
else
{
oneanser = i + 1;
}
}
if (times == 8)
{
cout << "找到唯一余数解:"
<< "坐标" << blank[load][0] + 1 << " " << blank[load][1] + 1
<< "数值 " << oneanser << endl;
update(blank[load][0], blank[load][1], oneanser);
return true;
}
}
return false;
}
//对可行域内余数解的检测
bool loscheck()
{
for (int load = 0; load < blanknum; load++)
{
int anwser = 0;
for (int i = 0; i < 9; i++)
{
bool hasfound = true;
if (canin[load][i] == -1)
{
continue;
}
for (int k = 0; k < blanknum; k++)
{
if (blank[k][0] == blank[load][0] &&
blank[k][1] != blank[load][1])
{
if (canin[k][i] == canin[load][i])
{
hasfound = false;
break;
}
else
{
anwser = i + 1;
continue;
}
}
else
{
continue;
}
}
anwser = i + 1;
if (hasfound == true)
{
cout << "找到行摒除解:"
<< "坐标" << blank[load][0] + 1 << " "
<< blank[load][1] + 1 << "数值 " << anwser << endl;
update(blank[load][0], blank[load][1], anwser);
return true;
}
hasfound = true;
for (int k = 0; k < blanknum; k++)
{
if (blank[k][1] == blank[load][1] &&
blank[k][0] != blank[load][0])
{
if (canin[k][i] == canin[load][i])
{
hasfound = false;
break;
}
else
{
anwser = i + 1;
continue;
}
}
else
{
continue;
}
}
anwser = i + 1;
if (hasfound == true)
{
cout << "找到列摒除解:"
<< "坐标" << blank[load][0] + 1 << " "
<< blank[load][1] + 1 << "数值 " << anwser << endl;
update(blank[load][0], blank[load][1], anwser);
return true;
}
hasfound = true;
for (int k = 0; k < blanknum; k++)
{
if (blank[k][2] == blank[load][2] &&
(blank[k][0] != blank[load][0] ||
blank[k][1] != blank[load][1]))
{
if (canin[k][i] == canin[load][i])
{
hasfound = false;
break;
}
else
{
anwser = i + 1;
continue;
}
}
else
{
continue;
}
}
anwser = i + 1;
if (hasfound == true)
{
cout << "找到宫摒除解:"
<< "坐标" << blank[load][0] + 1 << " "
<< blank[load][1] + 1 << "数值 " << anwser << endl;
update(blank[load][0], blank[load][1], anwser);
return true;
}
}
}
return false;
}
//结果检测
int check()
{
int returnans = 1;
int nx, ny;
for (nx = 0; nx < 9; nx++)
{
for (ny = 0; ny < 9; ny++)
{
if (date[nx][ny] == 0)
{
continue;
}
for (int i = 0; i < 9; i++)
{
if (date[i][ny] == date[nx][ny] && i != nx)
{
returnans = 0;
return returnans;
}
}
for (int i = 0; i < 9; i++)
{
if (date[nx][i] == date[nx][ny] && i != ny)
{
returnans = 0;
return returnans;
}
}
for (int kx = 0; kx < 9; kx++)
{
for (int ky = 0; ky < 9; ky++)
{
if (setare(kx, ky) == setare(nx, ny) &&
(nx != kx || ny != ky) &&
date[nx][ny] == date[kx][ky])
{
returnans = 0;
return returnans;
}
}
}
}
}
if (getblanknum() == 0)
{
returnans = 2;
return returnans;
}
else
{
return returnans;
}
}
// update后的可行域载入
void utsetcanin(int x, int y, int date)
{
for (int i = 0; i < blanknum; i++)
{
if (blank[i][0] == x || blank[i][1] == y || blank[i][2] == setare(x, y))
{
canin[i][date - 1] = -1;
}
}
return;
}
//获取特定位空块id
int getblankid(int x, int y)
{
int id = -1;
for (int i = 0; i < 81; i++)
{
if (blank[i][0] == x && blank[i][1] == y)
{
return i;
}
}
return -1;
}
//数据左移
void liftmove(int id)
{
for (int load = id; load < 81 - 1 && blank[load][0] != -1; load++)
{
for (int i = 0; i < 3; i++)
{
blank[load][i] = blank[load + 1][i];
}
for (int i = 0; i < 9; i++)
{
canin[load][i] = canin[load + 1][i];
}
}
return;
}
//获取宫格起始点
XY getoxy(int gid)
{
XY oxy;
int ox = -1;
int oy = -1;
int are = gid;
if (are == 1 || are == 4 || are == 7)
{
oy = 0;
}
else if (are == 2 || are == 5 || are == 8)
{
oy = 3;
}
else if (are == 3 || are == 6 || are == 9)
{
oy = 6;
}
if (are >= 1 && are <= 3)
{
ox = 0;
}
else if (are >= 4 && are <= 6)
{
ox = 3;
}
else if (are >= 7 && are <= 9)
{
ox = 6;
}
oxy.x = ox;
oxy.y = oy;
return oxy;
}
//区块摒除
bool arebc()
{
//行摒除
for (int gid = 1; gid <= 9; gid++)
{
XY oxy = getoxy(gid);
for (int i = oxy.x; i < oxy.x + 3; i++)
{
for (int k = 0; k < 9; k++)
{
bool hasd = true;
int times = 0;
for (int m = oxy.y; m < oxy.y + 3; m++)
{
if (getblankid(i, m) != -1)
{
if (canin[getblankid(i, m)][k] != 1)
{
hasd = false;
break;
}
}
else
{
times++;
}
}
if (times == 3)
{
hasd = false;
continue;
}
if (hasd == true)
{
for (int a1 = 0; a1 < 3; a1++)
{
for (int a2 = 0; a2 < 3; a2++)
{
if (a1 != i && canin[getblankid(a1, a2)][k] == 1)
{
hasd = false;
break;
}
}
}
}
if (hasd == true)
{
for (int load = 0; load < blanknum; load++)
{
if (blank[load][0] != i && blank[load][2] == gid && canin[load][k] == 1)
{
hasd = false;
break;
}
}
}
if (hasd == true)
{
cout << "\nBC:第" << i + 1 << "行,第 " << gid << "宫格 数据:" << k + 1 << endl;
for (int nload = 0; nload < blanknum; nload++)
{
if (blank[nload][0] == i && blank[nload][2] != gid)
{
canin[nload][k] = -1;
}
}
}
}
}
}
/*
for (int gid = 1; gid <= 9; gid++)
{
XY oxy = getoxy(gid);
for (int i = oxy.y; i < oxy.y + 3; i++)
{
for (int k = 0; k < 9; k++)
{
bool hasd = true;
int times = 0;
for (int m = oxy.x; m < oxy.x + 3; m++)
{
if (getblankid(m, i) != -1)
{
if (canin[getblankid(m, i)][k] != 1)
{
hasd = false;
break;
}
}
else
{
times++;
}
}
if (times == 3)
{
hasd = false;
continue;
}
if (hasd == true)
{
for (int a1 = 0; a1 < 3; a1++)
{
for (int a2 = 0; a2 < 3; a2++)
{
if (a2 != i && canin[getblankid(a1, a2)][k] == 1)
{
hasd = false;
break;
}
}
}
}
if (hasd == true)
{
for (int load = 0; load < blanknum; load++)
{
if (blank[load][1] != i && blank[load][2] == gid && canin[load][k] == 1)
{
hasd = false;
break;
}
}
}
if (hasd == true)
{
cout << "\nBC:第" << i + 1 << "列,第 " << gid << "宫格 数据:" << k + 1 << endl;
for (int nload = 0; nload < blanknum; nload++)
{
if (blank[nload][1] == i && blank[nload][2] != gid)
{
canin[nload][k] = -1;
}
}
}
}
}
}
*/
return false;
}
本题AC代码(比较菜,只会这样写)
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <set>
#include <map>
#include <cctype>
#include <fstream>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <functional>
#include <bitset>
#include <random>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define size_t ll
#define pii pair<int, int>
#define SSS std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
bool _Debug_Flag = 1;
#define DEBUG \
{ \
cout << endl \
<< (_Debug_Flag ? R"(\\\\\\debug//////)" : R"(//////debug\\\\\\)") << endl; \
_Debug_Flag = !_Debug_Flag; \
}
#define caseT \
ll T; \
cin >> T; \
cin.get(); \
while (T--)
#define ra(i, a, b) for (ll i = (a); i <= (b); i++)
#define rr(i, a, b) for (ll i = (a); i >= (b); i--)
#define rep(i, a, b) for (ll i = (a); i < (b); i++)
#define rect(n, m) ra(i, 1, n) ra(j, 1, m)
#define cti(c) int(c - '0')
#define itc(i) char(i + '0')
using namespace std;
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
const ull INF = 0x3f3f3f3f;
const ld EPS = 1e-7;
typedef pair<ll, ll> pll;
////////////////////////////////////////////////////////////////
bool cannotuse[10][10][10];
char g[10][10];
int kg = 0;
////////////////////////////////////////////////////////////////
struct logs
{
ll i, j, k;
};
vector<logs> doedit(int i, int j, int t, bool f)
{
vector<logs> vec;
ra(k, 1, 9)
{
if (cannotuse[i][k][t] != f)
{
cannotuse[i][k][t] = f;
vec.push_back({i, k, t});
}
}
ra(k, 1, 9)
{
if (cannotuse[k][j][t] != f)
{
cannotuse[k][j][t] = f;
vec.push_back({k, j, t});
}
}
int x = (ceil(1.0 * i / 3) - 1) * 3 + 1;
int y = (ceil(1.0 * j / 3) - 1) * 3 + 1;
for (size_t q = 0; q < 3; q++)
{
for (size_t r = 0; r < 3; r++)
{
if (cannotuse[x + q][y + r][t] != f)
{
cannotuse[x + q][y + r][t] = f;
vec.push_back({x + q, y + r, t});
}
}
}
return vec;
}
pii getmin()
{
pii res;
int mi = INF;
rect(9, 9)
{
if (g[i][j] != '.')
continue;
int r = 0;
ra(k, 1, 9)
{
if (cannotuse[i][j][k] == 0)
{
r++;
}
}
if (r == 1)
{
return {i, j};
}
else if (r != 0 && r < mi)
{
mi = r;
res = {i, j};
}
}
return res;
}
bool dfs(int r)
{
if (r > kg)
{
return true;
}
pii res = getmin();
int i = res.first;
int j = res.second;
if (g[i][j] == '.')
{
ra(k, 1, 9)
{
if (cannotuse[i][j][k] == 0)
{
vector<logs> vec = doedit(i, j, k, 1);
g[i][j] = itc(k);
doedit(i, j, k, 1);
if (dfs(r + 1))
{
return true;
}
else
{
g[i][j] = '.';
for (size_t i = 0; i < vec.size(); i++)
{
cannotuse[vec[i].i][vec[i].j][vec[i].k] = 0;
}
}
}
}
return false;
}
return false;
}
int main()
{
SSS;
rect(9, 9)
{
cin >> g[i][j];
if (g[i][j] != '.')
{
doedit(i, j, cti(g[i][j]), 1);
}
else
{
kg++;
}
}
dfs(1);
ra(i, 1, 9)
{
ra(j, 1, 9)
{
cout << g[i][j];
}
cout << endl;
}
return 0;
}
////////////////////////////////////////////////////////////////
那么,第一篇题解(?)就献给你啦~
stO
大佬果然是大佬……
就离谱 大佬果然是大佬
上学期大作业做的数独图片的识别与求解,然后学了数独求解的3种方法哈哈哈哈
现在看来,暴力大法好啊2333
确实,当时现学01规划和舞蹈链挺自闭的
膜拜大佬
本来想随便写一下的结果越写越长awa
nb!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
800行,《随便写一下》!!!!!!!!!!!!!!!