数独求解算法的C ++ [英] Sudoku solving algorithm C++
本文介绍了数独求解算法的C ++的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我试图做几天的数独解决方案，但我只能和方法。我发现这个算法，在这里，但我真的不明白：
- 在开始的第一个空单元格，并把1吧。
- 检查整板，看看是否有任何冲突
- 如果有冲突与斗争在板上，增加在当前小区1的数目（因此改变1至2，2〜3等）
- 如果董事会是干净的举动，开始重新第一步。
- 如果一个给定的单元格全部九个可能的数字引起电路板发生冲突，然后设置该单元回空，回到previous细胞，并从第3步重新开始（这正是回溯的意思）。
下面是我的code。我觉得有什么不对我的 Help_Solve（...）的功能。你能帮我找出问题，好吗？
的#include＆LT;的iostream＆GT;
＃包括＆LT;了iomanip＆GT;
＃包括＆LT; time.h中＆GT;
＃包括＆LT; cstdlib＆GT;
＃包括＆LT; WINDOWS.H＆GT;
使用名字空间std;
一流的数独
{
私人：
INT板[10] [9];
INT变化[9] [9];
上市：
数独（）;
无效Print_Board（）;
无效Add_First_Cord（）;
空隙求解（）;
无效Help_Solve（INT I，诠释J）;
布尔Check_Conflicts（INT磷，诠释我，诠释J）;
};
数独游戏;
无效setcolor（无符号短颜色）//你会使用到的功能
{//设置颜色
HANDLE HCON = GetStdHandle（STD_OUTPUT_HANDLE）;
SetConsoleTextAttribute（HCON，颜色）;
}
数独::数独（）
{
的for（int i = 1; I＆LT; = 9;我++）
对于（INT J = 1; J＆LT; = 9; J ++）
板[I] [J] = 0;
}
无效数独:: Print_Board（）
{
的for（int i = 1; I＆LT; = 9;我++）
{
对于（INT J = 1; J＆LT; = 9; J ++）
{
如果（其他城市[I] [J] == 1）
{
setcolor（12）;
COUT＆LT;＆LT;板[I] [J]＆LT;＆LT; ;
setcolor（7）;
}
否则COUT＆LT;＆LT;板[I] [J]＆LT;＆LT; ;
如果（j％3 == 0）COUT＆LT;＆LT; |;
}
COUT＆LT;＆LT; ENDL;
如果（I％3 == 0）COUT＆LT;＆LT; ------ + ------- + ---------＆LT;＆LT; ENDL;
}
}
无效数独:: Add_First_Cord（）
{
板[1] [1] = 5;改变[1] [1] = 1;
板[1] [2] = 3;改变[1] [2] = 1;
板[1] [5] = 7;改变[1] [5] = 1;
板[2] [1] = 6;改变[2] [1] = 1;
板[2] [4] = 1;改变[2] [4] = 1;
板[2] [5] = 9;改变[2] [5] = 1;
板[2] [6] = 5;改变[2] [6] = 1;
板[3] [2] = 9;改变[3] [2] = 1;
板[3] [3] = 8;改变[3] [3] = 1;
板[3] [8] = 6;改变[3] [8] = 1;
板[4] [1] = 8;改变[4] [1] = 1;
板[4] [5] = 6;改变[4] [5] = 1;
板[4] [9] = 3;改变[4] [9] = 1;
板[5] [1] = 4;改变[5] [1] = 1;
板[5] [4] = 8;改变[5] [4] = 1;
板[5] [6] = 3;改变[5] [6] = 1;
板[5] [9] = 1;改变[5] [9] = 1;
板[6] [1] = 7;改变[6] [1] = 1;
板[6] [5] = 2;改变[6] [5] = 1;
板[6] [9] = 6;改变[6] [9] = 1;
板[7] [2] = 6;改变[7] [2] = 1;
板[7] [7] = 2;改变[7] [7] = 1;
板[7] [8] = 8;改变[7] [8] = 1;
板[8] [4] = 4;改变[8] [4] = 1;
板[8] [5] = 1;改变[8] [5] = 1;
板[8] [6] = 9;改变[8] [6] = 1;
板[8] [9] = 5;改变[8] [9] = 1;
板[9] [5] = 8;改变[9] [5] = 1;
板[9] [8] = 7;改变[9] [8] = 1;
板[10] [9] = 9;改变[9] [9] = 1;
}
布尔数独:: Check_Conflicts（INT磷，诠释我，诠释J）
{
对于（INT K = 1; K＆LT; = 9; k ++）
如果（板[I] [K] == p）的返回false;
对于（INT Q = 1; Q＆LT; = 9，Q ++）
如果（板[Q] [J] == p）的返回false;
/ *
* 00
000
000
* /
如果（（j == 1 ||Ĵ== 4 ||Ĵ== 7）＆安培;＆安培;（ⅰ== 1 ||我== 4 ||我== 7））
{
如果（板[I] [J + 1] == p ||板[I] [J + 2] == p ||板[I + 1] [J] == p ||
板[I + 2] [J] == p ||板[I + 1] [J + 1] == p ||板[I + 1] [J + 2] == p ||
板[I + 2] [J + 1] == p ||板[I + 2] [J + 2] == p）的返回false;
}
/ *
000
000
* 00
* /
如果（（j == 1 ||Ĵ== 4 ||Ĵ== 7）＆安培;＆安培;（ⅰ== 3 ||我== 6 ||我== 9））
{
如果（板[I-1] [J] == p ||板[I-2] [J] == p ||板[I] [J + 1] == p ||
板[I] [J + 2] == p ||板[I-1] [J + 1] == p ||板[I-1] [J + 2] == p ||
板[I-2] [J + 1] == p ||板[I-2] [J + 2] == p）的返回false;
}
/ *
000
* 00
000
* /
如果（（j == 1 ||Ĵ== 4 ||Ĵ== 7）＆安培;＆安培;（ⅰ== 2 ||我== 5 ||我== 8））
{
如果（板[I-1] [j]的== p ||板[I + 1] [j]的== p ||板[I-1] [J + 1] == p ||
板[I] [J + 1] == p ||板[I + 1] [J + 1] == p ||板[I + 1] [J + 2] == p ||
板[I] [J + 2] == p ||板[I + 1] [J + 2] == p）的返回false;
}
/ *
0 * 0
000
000
* /
如果（（j == 2 ||Ĵ== 5 ||Ĵ== 8）＆安培;＆安培;（ⅰ== 1 ||我== 5 ||我== 7））
{
如果（板[I-1] [j]的== p ||板[I + 1] [j]的== p ||板[I-1] [J + 1] == p ||
板[I] [J + 1] == p ||板[I + 1] [J + 1] == p ||板[I + 1] [J + 2] == p ||
板[I] [J + 2] == p ||板[I + 1] [J + 2] == p）的返回false;
}
/ *
000
0 * 0
000
* /
如果（（j == 2 ||Ĵ== 5 ||Ĵ== 8）及及（我== 2 ||我== 5 ||我== 8））
{
如果（板[I-1] [j]的== p ||板[I-1] [J-1] == p ||板[I-1] [J + 1] == p ||
板[I] [J + 1] == p ||板[I] [J-1] == p ||板[I + 1] [J + 1] == p ||
板[I] [J] == p ||板[I + 1] [J-1] == p）的返回false;
}
/ *
000
000
0 * 0
* /
如果（（j == 2 ||Ĵ== 5 ||Ĵ== 8）及及（我== 3 ||我== 6 ||我== 9））
{
如果（板[I] [J-1] == p ||板[Ⅰ] [J + 1] == p ||板[I-1] [j]的== p ||
板[I-1] [J + 1] == p ||板[I-1] [J-1] == p ||板[I-2] [J] == p ||
板[I-1] [J + 1] == p ||板[I-2] [J-1] == p）的返回false;
}
/ *
00 *
000
000
* /
如果（（j == 3 ||Ĵ== 6 ||Ĵ== 9）＆安培;＆安培;（ⅰ== 1 ||我== 4 ||我== 7））
{
如果（板[I] [J-1] == p ||板[I] [J-2] == p ||板[I + 1] [J] == p ||
板[I + 1] [J-1] == p ||板[I + 1] [J-2] == p ||板[I + 2] [J] == p ||
板[I + 2] [J-1] == p ||板[I + 2] [J-2] == p）的返回false;
}
/ *
000
00 *
000
* /
如果（（十== 3 ||Ĵ== 6 ||Ĵ== 9）及及（我== 2 ||我== 5 ||我== 8））
{
如果（板[I-1] [j]的== p ||板[I-1] [J-1] == p ||板[I-1] [J-2] == p ||
板[I] [J-1] == p ||板[I] [J-2] == p ||板[I + 1] [J] == p ||
板[I + 1] [J-1] == p ||板[I + 1] [J-2] == p）的返回false;
}
/ *
000
000
00 *
* /
如果（（十== 3 ||Ĵ== 6 ||Ĵ== 9）及及（我== 3 ||我== 6 ||我== 9））
{
如果（板[I] [J-1] == p ||板[Ⅰ] [J-1] == p ||板[I-1] [j]的== p ||
板[I-1] [J-1] == p ||板[I-1] [J-2] == p ||板[I-2] [J] == p ||
板[I-2] [J-1] == p ||板[I-2] [J-2] == p）的返回false;
}
返回true;
}
无效数独:: Help_Solve（INT I，诠释J）
{
如果（J＆所述; = 0）
{
I = I-1;
J = 9;
}
如果（变更[I] [j]的1 ==）返回Game.Help_Solve（I，J-1）;
对于（INT P = 1; P＆LT; = 9，P ++）
如果（Game.Check_Conflicts（P，I，J））
{
板[I] [J] = P;
返回;
}
返回Game.Help_Solve（I，J-1）;
}
无效数独::解决（）
{
的for（int i = 1; I＆LT; = 9;我++）
{
对于（INT J = 1; J＆LT; = 9; J ++）
{
如果（板[I] [J] == 0＆功放;＆amp;转换[I] [J] == 0）
{
Game.Help_Solve（I，J）;
}
}
}
的for（int i = 1; I＆LT; = 9;我++）
对于（INT J = 1; J＆LT; = 9; J ++）
如果（板[I] [j]的== 0）Game.Help_Solve（I，J）;
}
诠释的main（）
{
Game.Add_First_Cord（）;
Game.Solve（）;
Game.Print_Board（）;
系统（暂停）;
返回0;
}
编辑：我需要使用递归吧？但是，也许我给函数的参数是错误的。我真的不知道。在 Add_First_Cord（）我宣布，每个数独在一开始的初始值。下面是我使用的值： http://bg.wikipedia.org/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:Sudoku-by-L2G-20050714.gif 。我希望看到的解决数独，因为它是显示在维基百科。但一些解决的值是对别人都没有。以下是我在控制台中
解决方案
建议的方法
- 在实现一个通用的图搜索算法
- 定义的数独状态
- 的状态下是9x9的阵列，号1，2，...，或者9或在每个位置的空白
- 在定义什么是目标数独状态
- 在所有81个单元格填入
- 在所有的9行有一个数字{1，2，...，9}在其中
- 在所有的9列编号为{1，2，...，9}在其中
- 在全部9个3×3的方格有数字{1，2，...，9}在其中
- 定义您的有效数独的状态后继函数
- 状态
取值可以拥有数N加入一行我，列Ĵ，如果：- 细胞
（I，J）是空 - 有行无其他
N我 - 没有在列没有其他
NĴ - 中有包含3×3平方没有其他
N（I，J）
- 细胞
- 国家后继功能状态
取值映射到向量满足这些规则的状态
- 状态
- 在应用您的通用图搜索算法（1）到数独状态图（2-4）
- （可选）如果您选择使用A *图搜索，你也可以定义为潜在的显着提高性能上的数独状态空间启发式
- 如何设计启发式是另一个整个问题，这是一门艺术的，而不是科学
当前的方法
您目前的做法拌的的规范的图形进行搜索的和的执行的搜索算法的。你将有很多的困难，如果你混合这两种。这个问题自然地分成两个不同的部分 - 算法和图形 - 这样你就可以而且应该利用这一点在您的实现。这将使它更简单。
你，如果你去与这种分离的另一个好处是，你可以的再利用的一个巨大的问题，一些你的图搜索算法 - ！非常酷
I'm trying to make a Sudoku Solving program for a couple of days but I'm stuck with the methods. I found this algorithm here but I don't really understand it:
- start at the first empty cell, and put 1 in it.
- Check the entire board, and see if there are any conflicts
- If there are coflicts on the board, increase the number in the current cell by 1 (so change 1 to 2, 2 to 3, etc)
- If the board is clean move, start at step one again.
- If all nine possible numbers on a given cell cause a conflict in the board, then you set this cell back to empty, go back to the previous cell, and start again from step 3 (this is where the 'backtracking' comes in).
Here is my code. I think something is wrong with my Help_Solve(...) function. Can you help me to identify the problem, please?
#include <iostream>
#include <iomanip>
#include <time.h>
#include <cstdlib>
#include <windows.h>
using namespace std;
class Sudoku
{
private:
int board[9][9];
int change[9][9];
public:
Sudoku();
void Print_Board();
void Add_First_Cord();
void Solve();
void Help_Solve(int i, int j);
bool Check_Conflicts(int p, int i, int j);
};
Sudoku Game;
void setcolor(unsigned short color) //The function that you'll use to
{ //set the colour
HANDLE hcon = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hcon,color);
}
Sudoku::Sudoku()
{
for(int i = 1; i <= 9; i++)
for(int j = 1; j <= 9; j++)
board[i][j] = 0;
}
void Sudoku::Print_Board()
{
for(int i = 1; i <= 9; i++)
{
for(int j = 1; j <= 9; j++)
{
if(change[i][j] == 1)
{
setcolor(12);
cout << board[i][j] << " ";
setcolor(7);
}
else cout << board[i][j] << " ";
if(j%3 == 0) cout << "| ";
}
cout << endl;
if(i%3 == 0) cout << "------+-------+---------" << endl;
}
}
void Sudoku::Add_First_Cord()
{
board[1][1] = 5; change[1][1] = 1;
board[1][2] = 3; change[1][2] = 1;
board[1][5] = 7; change[1][5] = 1;
board[2][1] = 6; change[2][1] = 1;
board[2][4] = 1; change[2][4] = 1;
board[2][5] = 9; change[2][5] = 1;
board[2][6] = 5; change[2][6] = 1;
board[3][2] = 9; change[3][2] = 1;
board[3][3] = 8; change[3][3] = 1;
board[3][8] = 6; change[3][8] = 1;
board[4][1] = 8; change[4][1] = 1;
board[4][5] = 6; change[4][5] = 1;
board[4][9] = 3; change[4][9] = 1;
board[5][1] = 4; change[5][1] = 1;
board[5][4] = 8; change[5][4] = 1;
board[5][6] = 3; change[5][6] = 1;
board[5][9] = 1; change[5][9] = 1;
board[6][1] = 7; change[6][1] = 1;
board[6][5] = 2; change[6][5] = 1;
board[6][9] = 6; change[6][9] = 1;
board[7][2] = 6; change[7][2] = 1;
board[7][7] = 2; change[7][7] = 1;
board[7][8] = 8; change[7][8] = 1;
board[8][4] = 4; change[8][4] = 1;
board[8][5] = 1; change[8][5] = 1;
board[8][6] = 9; change[8][6] = 1;
board[8][9] = 5; change[8][9] = 1;
board[9][5] = 8; change[9][5] = 1;
board[9][8] = 7; change[9][8] = 1;
board[9][9] = 9; change[9][9] = 1;
}
bool Sudoku::Check_Conflicts(int p, int i, int j)
{
for(int k = 1; k <= 9; k++)
if(board[i][k] == p) return false;
for(int q = 1; q <= 9; q++)
if(board[q][j] == p) return false;
/*
*00
000
000
*/
if((j == 1 || j == 4 || j == 7) && (i == 1 || i == 4 || i == 7))
{
if(board[i][j+1] == p || board[i][j+2] == p || board[i+1][j] == p ||
board[i+2][j] == p || board[i+1][j+1] == p || board[i+1][j+2] == p ||
board[i+2][j+1] == p || board[i+2][j+2] == p)return false;
}
/*
000
000
*00
*/
if((j == 1 || j == 4 || j == 7) && (i == 3 || i == 6 || i == 9))
{
if(board[i-1][j] == p || board[i-2][j] == p || board[i][j+1] == p ||
board[i][j+2] == p || board[i-1][j+1] == p || board[i-1][j+2] == p ||
board[i-2][j+1] == p || board[i-2][j+2] == p)return false;
}
/*
000
*00
000
*/
if((j == 1 || j == 4 || j == 7) && (i == 2 || i == 5 || i == 8))
{
if(board[i-1][j] == p || board[i+1][j] == p || board[i-1][j+1] == p ||
board[i][j+1] == p || board[i+1][j+1] == p || board[i+1][j+2] == p ||
board[i][j+2] == p || board[i+1][j+2] == p)return false;
}
/*
0*0
000
000
*/
if((j == 2 || j == 5 || j == 8) && (i == 1 || i == 5 || i == 7))
{
if(board[i-1][j] == p || board[i+1][j] == p || board[i-1][j+1] == p ||
board[i][j+1] == p || board[i+1][j+1] == p || board[i+1][j+2] == p ||
board[i][j+2] == p || board[i+1][j+2] == p)return false;
}
/*
000
0*0
000
*/
if((j == 2 || j == 5 || j == 8) && (i == 2 || i == 5 || i == 8))
{
if(board[i-1][j] == p || board[i-1][j-1] == p || board[i-1][j+1] == p ||
board[i][j+1] == p || board[i][j-1] == p || board[i+1][j+1] == p ||
board[i][j] == p || board[i+1][j-1] == p)return false;
}
/*
000
000
0*0
*/
if((j == 2 || j == 5 || j == 8) && (i == 3 || i == 6 || i == 9))
{
if(board[i][j-1] == p || board[i][j+1] == p || board[i-1][j] == p ||
board[i-1][j+1] == p || board[i-1][j-1] == p || board[i-2][j] == p ||
board[i-1][j+1] == p || board[i-2][j-1] == p) return false;
}
/*
00*
000
000
*/
if((j == 3 || j == 6 || j == 9) && (i == 1 || i == 4 || i == 7))
{
if(board[i][j-1] == p || board[i][j-2] == p || board[i+1][j] == p ||
board[i+1][j-1] == p || board[i+1][j-2] == p || board[i+2][j] == p ||
board[i+2][j-1] == p || board[i+2][j-2] == p) return false;
}
/*
000
00*
000
*/
if((j == 3 || j == 6 || j == 9) && (i == 2 || i == 5 || i == 8))
{
if(board[i-1][j] == p || board[i-1][j-1] == p || board[i-1][j-2] == p ||
board[i][j-1] == p || board[i][j-2] == p || board[i+1][j] == p ||
board[i+1][j-1] == p || board[i+1][j-2] == p) return false;
}
/*
000
000
00*
*/
if((j == 3 || j == 6 || j == 9) && (i == 3 || i == 6 || i == 9))
{
if(board[i][j-1] == p || board[i][j-1] == p || board[i-1][j] == p ||
board[i-1][j-1] == p || board[i-1][j-2] == p || board[i-2][j] == p ||
board[i-2][j-1] == p || board[i-2][j-2] == p) return false;
}
return true;
}
void Sudoku::Help_Solve(int i, int j)
{
if(j <= 0)
{
i = i-1;
j = 9;
}
if(change[i][j] == 1) return Game.Help_Solve(i, j-1);
for(int p = 1; p <= 9; p++)
if(Game.Check_Conflicts(p, i, j))
{
board[i][j] = p;
return;
}
return Game.Help_Solve(i, j-1);
}
void Sudoku::Solve()
{
for(int i = 1; i <= 9; i++)
{
for(int j = 1; j <= 9; j++)
{
if(board[i][j] == 0 && change[i][j] == 0)
{
Game.Help_Solve(i, j);
}
}
}
for(int i = 1; i <= 9; i++)
for(int j = 1; j <= 9; j++)
if(board[i][j] == 0) Game.Help_Solve(i, j);
}
int main()
{
Game.Add_First_Cord();
Game.Solve();
Game.Print_Board();
system("pause");
return 0;
}
Edit: I need to use recursion right? But maybe the parameters I give to the function are wrong. I really don't know. In Add_First_Cord() I declare the starting values that every sudoku has in the beginning. Here are the values that I use: http://bg.wikipedia.org/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:Sudoku-by-L2G-20050714.gif. I expect to see the solved sudoku as it is shown in wikipedia. But some solved values are right others are not. Here is what I get in the console
解决方案
Suggested Approach
- Implement a generic graph search algorithm
- could use either IDFS or A* graph search
- I would prefer the second
- do this for a general directed graph
- node type
TNode - node successor function
TNode => vector<TNode>
- node type
- could use either IDFS or A* graph search
- Define your Sudoku states
- a state is a 9x9 array with a number 1, 2, ..., or 9 or a blank in each position
- Define what a goal Sudoku state is
- all 81 cells filled in
- all 9 rows have numbers {1, 2, ..., 9} in them
- all 9 columns have numbers {1, 2, ..., 9} in them
- all 9 3x3 squares have numbers {1, 2, ..., 9} in them
- Define your valid Sudoku state successor function
- a state
Scan have numberNadded at rowI, columnJif:- cell
(I,J)is empty - there is no other
Nin rowI - there is no other
Nin columnJ - there is no other
Nin the 3x3 square containing(I,J)
- cell
- the state successor function maps a state
Sto thevectorof states that satisfy these rules
- a state
- Apply your generic graph search algorithm (1) to the Sudoku state graph (2-4)
- (optional) If you do choose to use A* graph search, you can also define a heuristic on your Sudoku state space to potentially drastically increase performance
- how to design the heuristic is another whole problem, that's more of an art than a science
Current Approach
Your current approach mixes the specification of the graph to be searched and the implementation of the search algorithm. You're going to have a lot of difficulty if you mix those two. This problem naturally separates into two distinct pieces -- the algorithm and the graph -- so you can and should exploit that in your implementation. It will make it much simpler.
The other benefit you get if you go with this separation is that you will be able to reuse your graph search algorithm on a huge number of problems - very cool!
这篇关于数独求解算法的C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
