|
|
Hi,
I ported the code of the program to C++, which proved to be more than 2 times faster than the C# version. Although, This release fixed the previous issues, I would like you to take a look at this algorithm(A C++ code snippet):
#include <iostream>
#include <algorithm>
#include <ctime>
#include<conio.h>
const unsigned SIZE = 9;
typedef unsigned char sudoku[SIZE][SIZE];
bool check(sudoku matrix, unsigned x, unsigned y){
unsigned char val = matrix[x][y];
for (unsigned a = 0; a<x; a++)
if (matrix[a][y] == val)
return 0;
for (unsigned a = x + 1; a<SIZE; a++)
if (matrix[a][y] == val)
return 0;
for (unsigned a = 0; a<y; a++)
if (matrix[x][a] == val)
return 0;
for (unsigned a = y + 1; a<SIZE; a++)
if (matrix[x][a] == val)
return 0;
unsigned startx = x / (SIZE / 3) * 3,
starty = y / (SIZE / 3) * 3,
endx = startx + SIZE / 3,
endy = starty + SIZE / 3;
for (unsigned a = startx; a<endx; a++){
for (unsigned b = starty; b<endy; b++){
if (a != x && b != y && matrix[a][b] == val)
return 0;
}
}
return 1;
}
void printMatrix(sudoku matrix){
for (unsigned b = 0; b<SIZE; b++){
for (unsigned a = 0; a<SIZE; a++){
if (matrix[a][b])
std::cout << (int)matrix[a][b];
else
std::cout << '_';
if (a && a % (SIZE / 3) == SIZE / 3 - 1)
std::cout << ' ';
}
std::cout << std::endl;
if (b && b % (SIZE / 3) == SIZE / 3 - 1)
std::cout << std::endl;
}
}
void transpose(sudoku matrix){
for (unsigned y = 0; y<SIZE - 1; y++){
for (unsigned x = y + 1; x<SIZE; x++){
std::swap(matrix[x][y], matrix[y][x]);
}
}
}
unsigned solution_time = 0;
bool solve(sudoku matrix, unsigned pos = 0){
unsigned x = pos%SIZE,
y = pos / SIZE;
if (y >= SIZE)
return 1;
if (matrix[x][y])
return solve(matrix, pos + 1);
for (unsigned a = 1; a <= SIZE; a++){
solution_time++;
matrix[x][y] = a;
if (check(matrix, x, y) && solve(matrix, pos + 1))
return 1;
}
matrix[x][y] = 0;
return 0;
}
int main(){
sudoku matrix =
{
8, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 3, 6, 0, 0, 0, 0, 0,
0, 7, 0, 0, 9, 0, 2, 0, 0,
0, 5, 0, 0, 0, 7, 0, 0, 0,
0, 0, 0, 0, 4, 5, 7, 0, 0,
0, 0, 0, 1, 0, 0, 0, 3, 0,
0, 0, 1, 0, 0, 0, 0, 6, 8,
0, 0, 8, 5, 0, 0, 0, 1, 0,
0, 9, 0, 0, 0, 0, 4, 0, 0,
};
clock_t t0, t1;
t0 = clock();
transpose(matrix);
if (!solve(matrix))
std::cout << "Unsolvable!" << std::endl;
else
printMatrix(matrix);
t1 = clock();
std::cout << "Solved in " << solution_time << " iterations." << std::endl;
std::cout << double(t1 - t0) / (double(CLOCKS_PER_SEC) / 1000.0) << " ms" << std::endl;
_getch();
return 0;
}
This algorithm is much-much faster than the current one(in C++) and insanely fast than C# version. Kindly go through it. Also, I found out that many puzzles have multiple solutions, and no unique. So, on clicking validate, the program should report the puzzle not being unique, rather than just checking for its validity.
|
|
|
|
|
Thank you for your great work and contribution. With my job I have not got the time to invest in this little project of mine. And after a 10 hour per day of writing code I don't do much programming when I'm at home. I'm on vaction now, so I can revise this project. C++ is quite faster than C# and your code surely is way faster than mine, but when I wrote this code I started from the idea that it should be written in "object oriented" code entirely. That's why I made those srtuctures for each line, 3x3 square, column etc. It's not the fastest choice... I can make the "solve" method faster using your idea. Keep the good work. Thanks
|
|
|
|
|
I have fixed some major bugs and added new functionality to the application. Now the validation routine searches for numbers filled in cells where only other numbers could be filled. Invalid games are easier to spot. (See invalid1.sdk file included to test)
The solving routine now uses this same principle to solve. For each group of nine cells (Row,Column or Square) is searched "this number is only possible in this cell". Errors are now displayed in red background.
|
|
|
|
|
Wow...
it's great project.
thanks alot my dear
|
|
|
|
|
Hi,
I was going through the program and found a bug.
you can see that the input game is faulty and has no solution, but the program assumes it to be a valid game and starts an infinite loop.
100000000000100000000000002000000100000000000000000000000000010000000000000000000
Kindly go through similar kinds of error prone test cases.
Thanks!
|
|
|
|
|
Sorry. I've been working really hard and I have not found time to revisit my code. I will try to solve this as fast as I can.
|
|
|
|
|
Hi Rui,
Try
2,4,6,8,7,5,9,1,3
3,1,7,9,2,4,5,8,6
5,8,9,1,6,3,4,1,5
8,5,2,3,4,1,6,7,9
4,6,1,7,8,9,2,3,5
9,7,3,2,5,6,8,4,1
1,2,4,5,9,7,3,6,8
6,3,5,4,1,8,7,9,2
7,9,8,6,3,2,1,5,4
and you will get "Puzzle solved in 0,000000000 seconds.
Impossible then there are two errors in the input, without warning.
The number 1 is in the 1. row and in the 3.; 5 in 2. and 3. row
Good luck
|
|
|
|
|
My routine solves the sudoku game without checking your input. It trustes you...
I have the code already written in my aplication to solve your program...
I just have to alter the "Solve" button to do: "validate the game and then solve" instead of just "solve"....
In that case, it will warn you "Invalid"...
I will correct it and update the article.
|
|
|
|
|
Hi Rui Jorge,
I'm sorry, but the program does not appear much. I have tested it and found many errors in solving.
So my vote: 5
|
|
|
|
|
Can you be more specific. Tell me what errors have you found and I will try to correct them. Keep in mind that Sudoku games have many solutions, not only one solution. I tested my program a lot and I haven´t found any errors...
|
|
|
|
|