使用十六进制字符的 16x16 数独解算器
16x16 sudoku solver using hex characters
#include <iostream>
#include <fstream>
#define N 16
using namespace std;
string grid[N][N];
string allowed[16]= {"0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"};
int reoccur = 0;
void getFromFile()
{
char character;
fstream fp;
fp.open("optionalnew.txt",ios::in);
for(int x = 0; x < N; x++)
{
for(int y = 0; y < N; y++)
{
fp >> character;
grid[x][y] = character;
cout << character;
}
}
cout << "\n";
}
bool allowedCol(int col, string num)
{
//Check if a number is already present in a col
for(int row = 0; row < N; row++)
if(grid[row][col] == num)
return true;
return false;
}
bool allowedRow(int row, string num)
{
//Check if a number is already present in a row
for(int col = 0; col < N; col++)
if(grid[row][col] == num)
return true;
return false;
}
bool allowedBox(int boxRow, int boxCol, string num)
{
//Check if a number is already present in a box
for(int row = 0; row < 4; row++)
for(int col = 0; col < 4; col++)
if(grid[row+boxRow][col+boxCol] == num)
return true;
return false;
}
bool isEmpty(int &row, int &col)
{
for(row = 0; row < N; row++)
for(col = 0; col < N; col++)
if(grid[row][col] == "X")
return true;
return false;
}
bool checkValid(int row, int col, string num)
{
return !allowedBox(row - row%4, col - col%4, num) && !allowedCol(col, num) && !allowedRow(row, num);
}
void dispBoard()
{
cout << " --------------------------------------------" << endl;
for(int row = 0; row < N; row++){
for(int col = 0; col < N; col++){
if(col == 4 || col == 8 || col == 12 || col == 0)
cout << " | ";
if(grid[row][col]=="X")
cout << "_ ";
else
cout << grid[row][col] <<" ";
if(col == 15)
cout << "| ";
}
if(row == 3 || row == 7 || row == 11){
cout << endl;
for(int i = 0; i<4; i++)
cout << "-----------";
}
cout << endl;
}
cout << " --------------------------------------------" << endl;
}
bool solveSudoku()
{
dispBoard();
cout << "\n" << endl;
reoccur+=1;
//cout << reoccur << endl;
int row, col;
if(!isEmpty(row,col))
return true;
for(int num = 0; num < 16; num++){
if(checkValid(row, col, allowed[num]))
{
grid[row][col] = allowed[num];
if(solveSudoku())
return true;
grid[row][col] = "X";
}
}
return false;
}
int main()
{
cout << "Here Is The Sudoku Problem:" << endl;
getFromFile();
dispBoard();
// Solving Problem
if(solveSudoku()){
cout << "Solved" << endl;
dispBoard();
}
else{
cout << "No Sol";
}
}
当 运行 没有任何反应时，我假设它一开始没有工作，但在求解函数开始时调用 dispBoard 函数，我发现值被添加到网格中，但从未达到一个结论。这是因为我没有给计算机足够的时间来得出答案吗？如果是这样，我可以进行哪些更改来优化我的代码。
看起来您正在使用“brute-force”方法，尝试所有可能的组合。您是否估算过此类组合的数量？
你熟悉this故事吗？
您尝试的第一个单元格有 16 个选项，下一个单元格有 16 个选项，依此类推。在空棋盘上，您将有 16^256 种组合。我不知道这样一个值的名称，但我怀疑您的计算机能否持续足够长的时间来检查它们。
好的，您可能已填充 100 或 120 个单元格。所以它“只会”是 16^130 :)
你玩数独吗？除了brute-force，你还使用其他策略吗？
哦，为了优化 - 使用 char 而不是 std::string 来存储单个字符。
补充阅读：https://en.wikipedia.org/wiki/Sudoku_solving_algorithms
更新：
在我将您的代码转换为使用 char 之后，令我惊讶的是，这个难题在我午休期间得到了解决。没有计时，但不到30分钟。发布版本。
--------------------------------------------
| 0 _ _ _ | _ _ B A | 3 _ 6 8 | _ 5 _ _ |
| _ _ B _ | 9 _ D _ | F _ 0 _ | 4 _ _ _ |
| _ _ _ _ | _ _ F _ | _ _ _ A | D _ 1 3 |
| _ _ 3 _ | 7 _ _ _ | _ _ C _ | _ _ E _ |
--------------------------------------------
| D _ _ 3 | _ F 8 _ | _ C _ 2 | _ E _ _ |
| C 2 1 _ | _ _ _ B | 8 _ D 5 | _ _ _ _ |
| 9 _ _ 8 | 6 _ _ C | _ _ A F | _ _ 7 4 |
| _ 0 _ _ | 1 _ A _ | _ 4 _ _ | _ _ 8 D |
--------------------------------------------
| _ _ _ 6 | _ _ _ _ | _ E _ _ | _ 3 9 7 |
| F E _ _ | _ _ 9 7 | _ _ _ C | 5 _ 6 A |
| _ _ 9 A | _ _ _ _ | B _ _ _ | 8 _ D C |
| 8 _ _ _ | D _ C _ | _ A _ _ | _ _ F B |
--------------------------------------------
| _ _ _ _ | _ _ 5 _ | _ _ _ _ | _ _ C _ |
| _ _ _ 7 | C A _ D | _ 6 E _ | _ _ 3 _ |
| 1 C _ 0 | E _ _ _ | D 7 _ _ | A 9 _ F |
| E _ 4 _ | _ 7 _ F | _ _ 5 _ | _ 0 _ _ |
--------------------------------------------
Solved
--------------------------------------------
| 0 F 7 E | 4 1 B A | 3 D 6 8 | C 5 2 9 |
| 5 6 B 1 | 9 C D 3 | F 2 0 E | 4 7 A 8 |
| 4 8 2 C | 5 0 F E | 7 B 9 A | D 6 1 3 |
| A D 3 9 | 7 8 6 2 | 4 5 C 1 | B F E 0 |
--------------------------------------------
| D B A 3 | 0 F 8 4 | 6 C 7 2 | 9 E 5 1 |
| C 2 1 4 | 3 E 7 B | 8 9 D 5 | F A 0 6 |
| 9 5 E 8 | 6 D 2 C | 1 0 A F | 3 B 7 4 |
| 7 0 6 F | 1 9 A 5 | E 4 B 3 | 2 C 8 D |
--------------------------------------------
| 2 1 C 6 | A B 4 8 | 5 E F D | 0 3 9 7 |
| F E D B | 2 3 9 7 | 0 8 4 C | 5 1 6 A |
| 3 7 9 A | F 5 E 0 | B 1 2 6 | 8 4 D C |
| 8 4 0 5 | D 6 C 1 | 9 A 3 7 | E 2 F B |
--------------------------------------------
| 6 3 8 2 | B 4 5 9 | A F 1 0 | 7 D C E |
| B 9 F 7 | C A 0 D | 2 6 E 4 | 1 8 3 5 |
| 1 C 5 0 | E 2 3 6 | D 7 8 B | A 9 4 F |
| E A 4 D | 8 7 1 F | C 3 5 9 | 6 0 B 2 |
--------------------------------------------
更新 2：
计时，得到 2,477 秒（~41 分钟）。
更新 3：
实现了数独游戏 notes - 为每个空单元格保留一组所有可能的值。仅通过 solveSudoku() 函数中的那些。这将时间缩短了一半。
实施简单的策略：遍历看板row-by-row，看看我在那一行的笔记是否有唯一编号；然后将其分配给找到它的单元格。在 262 秒内解决。
对 column-by-column 重复该操作。在 1.9 秒内解决。
我也可以这样做 block-by-block，但我正在失去兴趣。除非有人向我发起挑战:)
我不会在这里发布任何代码，假设 OP 想要这样做。
更新 4：
又增加了一个步骤：遍历每个单元格，看看他们的笔记是否只有一个数字；然后插入它。在 161 毫秒!
内解决
代码：
您需要包括
#include <unordered_set>
#include <map>
然后将您的定义更改为
char allowed[16] = { '0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F' };
并定义
unordered_set<char> notes[N][N] = {};
这是构建“笔记”的函数，我在从文件加载数据后立即调用它：
void buildNotes()
{
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if (grid[row][col] == 'X') {
for (int num = 0; num < 16; num++) {
if (checkValid(row, col, allowed[num]))
{
notes[row][col].insert(allowed[num]);
}
}
}
}
}
}
然后 solveSudoku() 中的 for 循环变为：
for (char num: notes[row][col]) {
if (checkValid(row, col, num))
{
grid[row][col] = num;
if (solveSudoku())
return true;
grid[row][col] = 'X';
}
}
我已经像这样实施了我的策略（在 main() 中）：
getFromFile();
dispBoard();
buildNotes();
while (unique()) {
while(singles())
;
}
这里是“智慧”：
bool unique()
{
for (int row = 0; row < N; row++) {
map<char, int> found;
for (int col = 0; col < N; col++) {
if (grid[row][col] == 'X') {
for (char num : notes[row][col]) {
found[num]++;
}
}
}
for (auto i : found) {
if (i.second == 1) { // found unique number in this column
for (int col = 0; col < N; col++) {
if (grid[row][col] == 'X') {
if (notes[row][col].find(i.first) != notes[row][col].end()) {
grid[row][col] = i.first;
// remove it from each cell in that col
for (int r = 0; r < N; r++) {
if (grid[r][col] == 'X')
notes[r][col].erase(i.first);
}
return true;
}
}
}
}
}
}
for (int col = 0; col < N; col++) {
map<char, int> found;
for (int row = 0; row < N; row++) {
if (grid[row][col] == 'X') {
for (char num : notes[row][col]) {
found[num]++;
}
}
}
for (auto i : found) {
if (i.second == 1) { // found unique number in this row
for (int row = 0; row < N; row++) {
if (grid[row][col] == 'X') {
if (notes[row][col].find(i.first) != notes[row][col].end()) {
grid[row][col] = i.first;
// remove it from each cell in that row
for (int c = 0; c < N; c++) {
if (grid[row][c] == 'X')
notes[row][c].erase(i.first);
}
return true;
}
}
}
}
}
}
return false;
}
bool singles()
{
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if (grid[row][col] == 'X') {
if (notes[row][col].size() == 1) {
char num = *notes[row][col].begin();
grid[row][col] = num;
// remove it from each cell in that col
for (int r = 0; r < N; r++) {
if (grid[r][col] == 'X')
notes[r][col].erase(num);
}
// remove it from each cell in that row
for (int c = 0; c < N; c++) {
if (grid[row][c] == 'X')
notes[row][c].erase(num);
}
return true;
}
}
}
}
return false;
}
#include <iostream>
#include <fstream>
#define N 16
using namespace std;
string grid[N][N];
string allowed[16]= {"0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"};
int reoccur = 0;
void getFromFile()
{
char character;
fstream fp;
fp.open("optionalnew.txt",ios::in);
for(int x = 0; x < N; x++)
{
for(int y = 0; y < N; y++)
{
fp >> character;
grid[x][y] = character;
cout << character;
}
}
cout << "\n";
}
bool allowedCol(int col, string num)
{
//Check if a number is already present in a col
for(int row = 0; row < N; row++)
if(grid[row][col] == num)
return true;
return false;
}
bool allowedRow(int row, string num)
{
//Check if a number is already present in a row
for(int col = 0; col < N; col++)
if(grid[row][col] == num)
return true;
return false;
}
bool allowedBox(int boxRow, int boxCol, string num)
{
//Check if a number is already present in a box
for(int row = 0; row < 4; row++)
for(int col = 0; col < 4; col++)
if(grid[row+boxRow][col+boxCol] == num)
return true;
return false;
}
bool isEmpty(int &row, int &col)
{
for(row = 0; row < N; row++)
for(col = 0; col < N; col++)
if(grid[row][col] == "X")
return true;
return false;
}
bool checkValid(int row, int col, string num)
{
return !allowedBox(row - row%4, col - col%4, num) && !allowedCol(col, num) && !allowedRow(row, num);
}
void dispBoard()
{
cout << " --------------------------------------------" << endl;
for(int row = 0; row < N; row++){
for(int col = 0; col < N; col++){
if(col == 4 || col == 8 || col == 12 || col == 0)
cout << " | ";
if(grid[row][col]=="X")
cout << "_ ";
else
cout << grid[row][col] <<" ";
if(col == 15)
cout << "| ";
}
if(row == 3 || row == 7 || row == 11){
cout << endl;
for(int i = 0; i<4; i++)
cout << "-----------";
}
cout << endl;
}
cout << " --------------------------------------------" << endl;
}
bool solveSudoku()
{
dispBoard();
cout << "\n" << endl;
reoccur+=1;
//cout << reoccur << endl;
int row, col;
if(!isEmpty(row,col))
return true;
for(int num = 0; num < 16; num++){
if(checkValid(row, col, allowed[num]))
{
grid[row][col] = allowed[num];
if(solveSudoku())
return true;
grid[row][col] = "X";
}
}
return false;
}
int main()
{
cout << "Here Is The Sudoku Problem:" << endl;
getFromFile();
dispBoard();
// Solving Problem
if(solveSudoku()){
cout << "Solved" << endl;
dispBoard();
}
else{
cout << "No Sol";
}
}
当 运行 没有任何反应时，我假设它一开始没有工作，但在求解函数开始时调用 dispBoard 函数，我发现值被添加到网格中，但从未达到一个结论。这是因为我没有给计算机足够的时间来得出答案吗？如果是这样，我可以进行哪些更改来优化我的代码。
看起来您正在使用“brute-force”方法，尝试所有可能的组合。您是否估算过此类组合的数量？
你熟悉this故事吗？
您尝试的第一个单元格有 16 个选项，下一个单元格有 16 个选项，依此类推。在空棋盘上，您将有 16^256 种组合。我不知道这样一个值的名称，但我怀疑您的计算机能否持续足够长的时间来检查它们。
好的，您可能已填充 100 或 120 个单元格。所以它“只会”是 16^130 :)
你玩数独吗？除了brute-force，你还使用其他策略吗？
哦，为了优化 - 使用 char 而不是 std::string 来存储单个字符。
补充阅读：https://en.wikipedia.org/wiki/Sudoku_solving_algorithms
更新：
在我将您的代码转换为使用 char 之后，令我惊讶的是，这个难题在我午休期间得到了解决。没有计时，但不到30分钟。发布版本。
--------------------------------------------
| 0 _ _ _ | _ _ B A | 3 _ 6 8 | _ 5 _ _ |
| _ _ B _ | 9 _ D _ | F _ 0 _ | 4 _ _ _ |
| _ _ _ _ | _ _ F _ | _ _ _ A | D _ 1 3 |
| _ _ 3 _ | 7 _ _ _ | _ _ C _ | _ _ E _ |
--------------------------------------------
| D _ _ 3 | _ F 8 _ | _ C _ 2 | _ E _ _ |
| C 2 1 _ | _ _ _ B | 8 _ D 5 | _ _ _ _ |
| 9 _ _ 8 | 6 _ _ C | _ _ A F | _ _ 7 4 |
| _ 0 _ _ | 1 _ A _ | _ 4 _ _ | _ _ 8 D |
--------------------------------------------
| _ _ _ 6 | _ _ _ _ | _ E _ _ | _ 3 9 7 |
| F E _ _ | _ _ 9 7 | _ _ _ C | 5 _ 6 A |
| _ _ 9 A | _ _ _ _ | B _ _ _ | 8 _ D C |
| 8 _ _ _ | D _ C _ | _ A _ _ | _ _ F B |
--------------------------------------------
| _ _ _ _ | _ _ 5 _ | _ _ _ _ | _ _ C _ |
| _ _ _ 7 | C A _ D | _ 6 E _ | _ _ 3 _ |
| 1 C _ 0 | E _ _ _ | D 7 _ _ | A 9 _ F |
| E _ 4 _ | _ 7 _ F | _ _ 5 _ | _ 0 _ _ |
--------------------------------------------
Solved
--------------------------------------------
| 0 F 7 E | 4 1 B A | 3 D 6 8 | C 5 2 9 |
| 5 6 B 1 | 9 C D 3 | F 2 0 E | 4 7 A 8 |
| 4 8 2 C | 5 0 F E | 7 B 9 A | D 6 1 3 |
| A D 3 9 | 7 8 6 2 | 4 5 C 1 | B F E 0 |
--------------------------------------------
| D B A 3 | 0 F 8 4 | 6 C 7 2 | 9 E 5 1 |
| C 2 1 4 | 3 E 7 B | 8 9 D 5 | F A 0 6 |
| 9 5 E 8 | 6 D 2 C | 1 0 A F | 3 B 7 4 |
| 7 0 6 F | 1 9 A 5 | E 4 B 3 | 2 C 8 D |
--------------------------------------------
| 2 1 C 6 | A B 4 8 | 5 E F D | 0 3 9 7 |
| F E D B | 2 3 9 7 | 0 8 4 C | 5 1 6 A |
| 3 7 9 A | F 5 E 0 | B 1 2 6 | 8 4 D C |
| 8 4 0 5 | D 6 C 1 | 9 A 3 7 | E 2 F B |
--------------------------------------------
| 6 3 8 2 | B 4 5 9 | A F 1 0 | 7 D C E |
| B 9 F 7 | C A 0 D | 2 6 E 4 | 1 8 3 5 |
| 1 C 5 0 | E 2 3 6 | D 7 8 B | A 9 4 F |
| E A 4 D | 8 7 1 F | C 3 5 9 | 6 0 B 2 |
--------------------------------------------
更新 2：
计时，得到 2,477 秒（~41 分钟）。
更新 3：
实现了数独游戏 notes - 为每个空单元格保留一组所有可能的值。仅通过 solveSudoku() 函数中的那些。这将时间缩短了一半。
实施简单的策略：遍历看板row-by-row，看看我在那一行的笔记是否有唯一编号；然后将其分配给找到它的单元格。在 262 秒内解决。
对 column-by-column 重复该操作。在 1.9 秒内解决。
我也可以这样做 block-by-block，但我正在失去兴趣。除非有人向我发起挑战:)
我不会在这里发布任何代码，假设 OP 想要这样做。
更新 4：
又增加了一个步骤：遍历每个单元格，看看他们的笔记是否只有一个数字；然后插入它。在 161 毫秒!
内解决代码：
您需要包括
#include <unordered_set>
#include <map>
然后将您的定义更改为
char allowed[16] = { '0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F' };
并定义
unordered_set<char> notes[N][N] = {};
这是构建“笔记”的函数，我在从文件加载数据后立即调用它：
void buildNotes()
{
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if (grid[row][col] == 'X') {
for (int num = 0; num < 16; num++) {
if (checkValid(row, col, allowed[num]))
{
notes[row][col].insert(allowed[num]);
}
}
}
}
}
}
然后 solveSudoku() 中的 for 循环变为：
for (char num: notes[row][col]) {
if (checkValid(row, col, num))
{
grid[row][col] = num;
if (solveSudoku())
return true;
grid[row][col] = 'X';
}
}
我已经像这样实施了我的策略（在 main() 中）：
getFromFile();
dispBoard();
buildNotes();
while (unique()) {
while(singles())
;
}
这里是“智慧”：
bool unique()
{
for (int row = 0; row < N; row++) {
map<char, int> found;
for (int col = 0; col < N; col++) {
if (grid[row][col] == 'X') {
for (char num : notes[row][col]) {
found[num]++;
}
}
}
for (auto i : found) {
if (i.second == 1) { // found unique number in this column
for (int col = 0; col < N; col++) {
if (grid[row][col] == 'X') {
if (notes[row][col].find(i.first) != notes[row][col].end()) {
grid[row][col] = i.first;
// remove it from each cell in that col
for (int r = 0; r < N; r++) {
if (grid[r][col] == 'X')
notes[r][col].erase(i.first);
}
return true;
}
}
}
}
}
}
for (int col = 0; col < N; col++) {
map<char, int> found;
for (int row = 0; row < N; row++) {
if (grid[row][col] == 'X') {
for (char num : notes[row][col]) {
found[num]++;
}
}
}
for (auto i : found) {
if (i.second == 1) { // found unique number in this row
for (int row = 0; row < N; row++) {
if (grid[row][col] == 'X') {
if (notes[row][col].find(i.first) != notes[row][col].end()) {
grid[row][col] = i.first;
// remove it from each cell in that row
for (int c = 0; c < N; c++) {
if (grid[row][c] == 'X')
notes[row][c].erase(i.first);
}
return true;
}
}
}
}
}
}
return false;
}
bool singles()
{
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if (grid[row][col] == 'X') {
if (notes[row][col].size() == 1) {
char num = *notes[row][col].begin();
grid[row][col] = num;
// remove it from each cell in that col
for (int r = 0; r < N; r++) {
if (grid[r][col] == 'X')
notes[r][col].erase(num);
}
// remove it from each cell in that row
for (int c = 0; c < N; c++) {
if (grid[row][c] == 'X')
notes[row][c].erase(num);
}
return true;
}
}
}
}
return false;
}