数独求解器中无限循环中的问题 [英] Problem in infinite loop in a sudoku solver
问题描述
我正在制作一个简单的数独求解器，这个算法非常简单而且愚蠢找到一个块，其中只有一个可能的位置。它在简单的游戏中工作一次，当我尝试使用极端和中等的困难时它进入无限循环，当我尝试另一个简单的游戏失败！
Hi, I'm making a simple Sudoku solver, The algorithm is very simple and dumb find a block where there is only one possible place for this number in it. it worked once in easy game when I tried it using an extremely and medium difficulties it entered an infinite loop when I tried another easy game it failed!!
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct maxes
{
int number;
int used;
};
bool compare_by_used(const maxes& a,const maxes& b);
class sudoku
{
public :
void take_board(); //Done //takes the board by asking the user to enter each row one by one
void solve_game(); //solves the games completely
void show_board(); //Done //show the game board
sudoku(); //Done
~sudoku() {} // Done //destructor do nothing
private :
enum {AVAILABLE_MOVES = 0,GAME_BOARD = 1}; // Done
//this array contains both of game board and available free boxes for each number // Done
short game[2][10][10];
vector < maxes > maxes_sorted;
inline void sort_maxes();
//returns index of the first element in a box in form of xy. for x and separately x = xy/10 y = xy%10
short get_location(const short& box_index);//Done
//find available boxes for each number
void find_availables(); //Done
//return true if the the number if the number is available in this box
bool is_available_in_box(const short& num,const short& box_index);//Done
//number of occupied places
short allocated_places; // Done
//if the number has one available place it return xy of the place else it returns 0
short is_available_here_only(const short& box_index,const short& num); // Done
//find if the number is available in this place
bool is_available_here(const short& x,const short& y,const short& num); // Done
//find next possible box for a number
inline short find_next(short i);
};
bool compare_by_used(const maxes& a,const maxes& b)
{
return ( a.used > b.used );
}
inline void sudoku::sort_maxes()
{
sort(maxes_sorted.begin(),maxes_sorted.end(),compare_by_used);
}
inline short sudoku::find_next(short i)
{
for (short j = 1; j < 10; j++)
{
if (game[AVAILABLE_MOVES][i][j] != 0)
{
return game[AVAILABLE_MOVES][i][j];
}
}
return 10;
}
void sudoku::solve_game()
{
register short i , j , place;
while (allocated_places != 81)
{
if (allocated_places == 41)
{
allocated_places = allocated_places;
}
for (i = 1; i < 10;i++)
{
if (maxes_sorted[i].used == 9)
{
continue;
}
for (j = 1; j < 10; j++)
{
if (game[AVAILABLE_MOVES][i][j] == 0)
continue;
place = is_available_here_only(game[AVAILABLE_MOVES][i][j], i);
if (place != 0)
{
game[GAME_BOARD][place/10][place%10] = i;
game[AVAILABLE_MOVES][i][j] = 0;
maxes_sorted[i].used++;
allocated_places++;
j = find_next(i);
sort_maxes();
}
}
}
}
}
void sudoku::show_board()
{
for (short i = 1; i < 10; i++)
{
if (i == 1)
cout << "+---+---+---+---+---+---+---+---+---+\n|\n";
for (short j = 1; j < 10; j++)
{
if (j == 1)
cout << "| ";
cout << int(game[GAME_BOARD][i][j]);
cout << " | ";
}
cout << endl;
cout << "\n+---+---+---+---+---+---+---+---+---+\n";
}
}
void sudoku::take_board()
{
cout << " 1 2 3 4 5 6 7 8 9\n";
for (short i = 1; i < 10; i++)
{
cout << "Enter the " << int(i) << " row : ";
for (short j = 1; j < 10; j++)
{
cin >> game[GAME_BOARD][i][j];
if (game[GAME_BOARD][i][j] > 0)
{
maxes_sorted[ game[GAME_BOARD][i][j] ].used++;
allocated_places++;
}
}
}
find_availables();
}
bool sudoku::is_available_here(const short& x,const short& y,const short& num)
{
if (game[GAME_BOARD][x][y] != 0)
{
return false;
}
for (short i = 1; i < x; i++)
{
if (game[GAME_BOARD][i][y] == num )
return false;
}
for (short i = x+1; i < 10; i++)
{
if (game[GAME_BOARD][i][y] == num )
return false;
}
for (short i = y+1; i < 10; i++)
{
if (game[GAME_BOARD][x][i] == num )
return false;
}
for (short i = 1; i < y; i++)
{
if (game[GAME_BOARD][x][i] == num )
return false;
}
return true;
}
short sudoku::is_available_here_only(const short& box_index,const short& num)
{
if (box_index == 0)
{
return 0;
}
short place = get_location(box_index);
short available_place = 0;
short counter = 0;
for (short x = place / 10 ; x <= (place / 10 + 2); x++)
{
for (short y = place % 10 ; y <= (place % 10 + 2); y++)
{
if ( is_available_here(x,y,num) )
{
counter++;
if (counter > 1)
{
return 0;
}
available_place = ( x * 10 ) + y;
}
}
}
if (counter != 1)
{
return 0;
}
return available_place;
}
bool sudoku::is_available_in_box(const short& num,const short& box_index)
{
int place = get_location(box_index);
for (short i = place / 10; i <= (place/10 + 2); i++)
{
for (short j = place % 10; j <= (place%10 + 2); j++)
{
if ( game[GAME_BOARD][i][j] == num )
{
return false;
}
}
}
return true;
}
void sudoku::find_availables()
{
short i,j;
for (i = 1; i < 10; i++) // number
{
for (j = 1; j < 10; j++) // box
{
if (is_available_in_box(i,j))
{
game[AVAILABLE_MOVES][i][j] = j;
}
}
}
sort_maxes();
}
inline short sudoku::get_location(const short& box_index)
{
switch (box_index)
{
case 1:
return 11;
break;
case 2:
return 14;
break;
case 3:
return 17;
break;
case 4:
return 41;
break;
case 5:
return 44;
break;
case 6:
return 47;
break;
case 7:
return 71;
break;
case 8:
return 74;
break;
case 9:
return 77;
break;
default :
return 0;
break;
}
}
sudoku::sudoku()
{
short i = 0,k = 0,j = 0;
allocated_places = 0;
maxes_sorted.resize(10);
for (int i = 0; i < maxes_sorted.size(); i++)
{
maxes_sorted[i].number = i;
maxes_sorted[i].used = 0;
}
for (k = 0; k < 2; k++)
{
for (i = 0; i < 10; i++)
{
for (j = 0; j < 10; j++)
{
game[int(k)][int(i)][int(j)] = 0;
}
}
}
}
int main()
{
sudoku my_game;
my_game.take_board();
my_game.show_board();
my_game.solve_game();
cout << endl << endl;
my_game.show_board();
}
问题出在哪里？为什么这个算法失败？什么是更好的算法??
谢谢，塞缪尔。
Where is the problem ? why this algorithm failed ? what are better algorithms ??
Thanks, Samuel.
推荐答案
你的无限循环似乎在solve_game函数（使用调试器验证）：
Your infinite loop seems to be in the solve_game function (use the debugger to verify):
while (allocated_places != 81)
{
if (allocated_places == 41)
{
allocated_places = allocated_places; // doesn't do anything!
}
...
}
在省略号标记的代码中，不保证allocate_places增加。在这种情况下，您正在进入无限循环。并且第五行中的陈述没有做任何事情。你想在那里完成什么？
在互联网上寻找解算器算法并不困难：使用数独算法C ++的谷歌搜索提供了大约400,000次点击。例如：
https://en.wikipedia.org/wiki / Sudoku_solving_algorithms [ ^ ]
为了您在编程技能方面的进步，我认为您需要完成两件事：了解有关C ++的更多信息并学习如何使用调试器。如果不使用调试器，你就不会走得太远。
In the code marked by the ellipsis it is not guaranteed that allocated_places is increased. In that case you are entering an infinite loop. And the statement in the fifth line doesn't do anything. What were you trying to accomplish there?
Finding a solver algorithm on the Internet is not difficult: A google search with "Sudoku algorithm C++" delivered some 400.000 hits. For example:
https://en.wikipedia.org/wiki/Sudoku_solving_algorithms[^]
For your progress in programming skills I think you need to work on two things: Learn more about C++ and learn to use the debugger. Without using a debugger you will not get really far.
这篇关于数独求解器中无限循环中的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
