Congratulations to my self.

[wtf]

I just wanted to do a little public boasting, I thought this would be a better place than the other areas of the forums.

AFTER NEARLY 5 MONTHS I've Done it!!!
I've finally got my sudoku solver to solve the most challenging sudokus, like this one posted on the net. Invented by a finnish mathematician, allegedly it is the hardest known sudoku:

 ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
 ▓ 1 |   |   ▓   |   | 7 ▓   | 9 |   ▓
 ▓-----------▓-----------▓-----------▓
 ▓   | 3 |   ▓   | 2 |   ▓   |   | 8 ▓
 ▓-----------▓-----------▓-----------▓
 ▓   |   | 9 ▓ 6 |   |   ▓ 5 |   |   ▓
 ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
 ▓   |   | 5 ▓ 3 |   |   ▓ 9 |   |   ▓
 ▓-----------▓-----------▓-----------▓
 ▓   | 1 |   ▓   | 8 |   ▓   |   | 2 ▓
 ▓-----------▓-----------▓-----------▓
 ▓ 6 |   |   ▓   |   | 4 ▓   |   |   ▓
 ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
 ▓ 3 |   |   ▓   |   |   ▓   | 1 |   ▓
 ▓-----------▓-----------▓-----------▓
 ▓   | 4 |   ▓   |   |   ▓   |   | 7 ▓
 ▓-----------▓-----------▓-----------▓
 ▓   |   | 7 ▓   |   |   ▓ 3 |   |   ▓
 ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓

And it was solved in 3.67 seconds. Which probably would have been faster except I'm on windows 7. And I know it may not seem like anything to brag about to some of you, it is a real big deal to me. I have done all of this without a computer of my own, and have had to go from library to library computer lab to computer lab in order to be able to work on it, sometimes as little as 1 hour at a time per day. Learning c++ as I go. Although i still have some finishing touches to do on it, already it can generate a easy or medium (according to www.sudoku-solutions.com) sudoku in less than a second or a hard sudoku in 10 - 20 seconds (also according to www.sudoku-solutions.com)

I understand that recursive algorithms can (although I DON'T UNDERSTAND HOW!!!) solve the above sudoku in a fraction of a second (like I said I would have thought that my inference rule based approach would have been far faster) I believe that inference rule based solving approach is necessary to estimate a difficulty level so all is not waisted.

Now will someone please tell me how is a brute force recursive algorithm actually able to solve unique solution sudokus faster than my method? It is really perplexing to me.

Also please feel free to share your solving times for your own sudoku solvers and how fast they were able to solve the above puzzle. Also what rating system are you using to calculate difficulty level? With the weightings I have in effect right now the above puzzle on my program has 2,394 3,474 points, with the average Hard puzzle having between 1500 and 2500. This will very likely vary as I toy with my weightings system.

Thanks all for your help along the way!

[Albatross]

Well, congratulations! I'm so happy for you right now. ^_^ What method does your solver use to solve these puzzles? I'd be interested as there are several I can think of.

...alright, that's enough. Now it's time for you to write a Kakuro solver in Fortran.

-Albatross

[helios]

3.67 s?! That's insane! That particular puzzle can be recursively brute-forced in a few milliseconds.

#include <iostream>
#include <algorithm>
#include <ctime>

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=
	{
		1,0,0,	0,0,7,	0,9,0,
		0,3,0,	0,2,0,	0,0,8,
		0,0,9,	6,0,0,	5,0,0,
		
		0,0,5,	3,0,0,	9,0,0,
		0,1,0,	0,8,0,	0,0,2,
		6,0,0,	0,0,4,	0,0,0,
		
		3,0,0,	0,0,0,	0,1,0,
		0,4,0,	0,0,0,	0,0,7,
		0,0,7,	0,0,0,	3,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;
	return 0;
}

Solved in 80491 iterations.
15 ms

[Null]

Maybe his computer is slow?

@wtf: Can you post the source code of your sudoku solver?

[Albatross]

Actually, wait a sec (or 3.67). That many seconds? That is pretty darn slow. Null++: Could we see the source code? Even my old Compaq running at 333 MHz with Windows XP wouldn't take 1 second, depending on the algorithm.

Still, congratz!

-Albatross

[helios]

Ah, I just saw this:

Now will someone please tell me how is a brute force recursive algorithm actually able to solve unique solution sudokus faster than my method? It is really perplexing to me.

Different algorithms have different sets of data that are their worst case. For example, a reverse-sorted array is the worst case for a bubble sort, but the best case for an insertion sort some other sort (probably).
There are puzzles that a brute force can take several minutes to solve, while a smarter algorithm will only take a few seconds. Brute force's weak point is that its worst cases are more expensive than a smarter algorithm's own worst case. It's strong point is that if there's a solution, brute force is guaranteed to find it.

EDIT: I just run the near-worst case set for brute force on the Wikipedia article. I think the text is somewhat outdated. It says a 3 GHz computer can solve it in 30-45 minutes, but one of my Core 2 cores running @ 1.86 GHz solved it in 27 seconds (622.5 M iterations).

[wtf]

I pointed out that it is slow... although now on the defensive.... its not that slow. for a novice programmer it isn't slow at all. and just my sudoku class itself is over 3,000 lines of code. So I still have ideas of how to optimize it, possibly move member functions outside of the class so when I declare a sudoku within a function it will operate more smoothly.... it might only shave a fraction off the total time.... but what else can I do? I am also looking at other options.


And no one answered my question as how it is possible for a recursive algorithm to be slower than mine, which only at the worst implements a pseudo recursive call to reductio ad absurdiom etc. (mine isn't fully recursive because instead of calling solve() rad() i.e. reductio ad absurdum only calls solve_lite() which does not in turn call rad().


also are you forgetting that in the recursive examples above it could take many times longer to solve all possible solutions with puzzles with hundreds of solutions, whereas in my program it takes less than 1 second to realize that it is not solveable to a unique solution.

also in your program it took 8 seconds to realize that the following was insoluable:

	sudoku matrix=
	{
		1,2,3,4,5,6,7,8,9,
		4,5,6,7,8,9,1,2,3,
		7,8,9,1,2,3,4,5,6,
		2,1,4,3,6,5,8,7,7,


	};

Unsolvable!
Solved in 157563351 iterations.
8242 ms

[helios]

See my previous post.

[wtf]

sorry my bad...

[thepedestrian]

This is awesome. :)

WOW. I'm starting to fall in love with C++. When I first started programming, I didn't like it much and thought it was way to strict but it's a beautiful language. I hope to be able to do what you are doing some day.

[kfmfe04]

and just my sudoku class itself is over 3,000 lines of code.

helios' is <100 lines: I prefer to play with fewer lines of code, whenever possible (fewer bugs, easier to understand, etc...)

But am I comparing apples to oranges here? Will both programs solve for general sudoku problems?

[sohguanh]

Actually based on my experience, the number of lines of code does not mean the program is doing the job well. In fact, a well written program can be short by using libraries and coding efficient algorithm and data structures.

Most of the time, we do a lot of exception and return values handling that they "corrupted" the actual business logic flowing.

But the question still remains like what kfmfe04 wrote "But am I comparing apples to oranges here? Will both programs solve for general sudoku problems?"

[chrisname]

You should always use the best (fastest, clearest, most flexible, etc.) means to an end.

[CQQL]

@helios: Why are you transposing it first?

[wtf]

I think the main point, though Helios's code is very simple and elegant, simply it does something completely different than my program. In order to "generate" a random sudoku, you would need toadd more code. My program first generates a random completed sudoku grid. Next it uses the inferences rules that I coded, with a weighted point system based on perceived level of difficulty a human would encounter applying those inference rules when solving the puzzle by hand, to systematically find a puzzle (or permutation of cells of the completed grid) that is in the desired difficulty range.

Surely my code is not the most optimal code ever written that accomplishes this task, but a simple recursive algorithm that solves all possible puzzle solutions does not do what mine does, even if you were to add functionality to generate a random puzzle, without some set of inference rules, its just going to be a random sudoku, no telling how easy or hard. Even finding a sudoku that is difficult (time consuming) for a computer to solve recursively is not guaranteed to be challenging for a human, indeed I believe correlation is very low.

[helios]

I can't remember. It might have something to do with how the matrix ends up laid out in memory due to the way I'm entering it in the source, and how it's accessed later in the program. It shouldn't affect the solution, since AFAICT solve(M^T)^T=solve(M).

EDIT: Technically, that statement isn't necessarily true for an M with multiple solutions.

EDIT 2: Can your algorithm find how many solutions the puzzle has?

[wtf]

No, I never intended it to. In my book if a puzzle has more than 1 solution its ambiguous, and hence not a valid sudoku. When I solve a puzzle by hand, I'm not interested in using brute force trial & error. I would like to meet someone that is, he deserves to be locked up.

I am going to remove the transpose operation from your code and see how long it takes to solve the near worst case scenario. I'm sure it shouldn't affect the time much. I'm going to go have a cigarette, go run a few errands, watch a production of Wagner's Ring, and perhaps the Godfather Trilogy as well. When I come back I will let you know how long it took to solve. I am also going to read every line of code posted on here much more meticulously from now on.

[helios]

I did that, already.

I just run the near-worst case set for brute force on the Wikipedia article. I think the text is somewhat outdated. It says a 3 GHz computer can solve it in 30-45 minutes, but one of my Core 2 cores running @ 1.86 GHz solved it in 27 seconds (622.5 M iterations).

You must be some kind of real life The Flash.

EDIT: I just ran it again to check the result with the one on Wikipedia (http://en.wikipedia.org/wiki/User_talk:170.115.251.13/Su_Doku ) to make sure the algorithm was correct (maybe I was missing some checks that sped it up enormously). It's correct and, again, it took 27 seconds.