Asking for advice from fellow programmers on sudoku.

I have been trying to solve this sudoku by writing an algorithm that pretty much just inserting random numbers, checking, and discarding bad results.----------------------------
| _ 4 _ | 1 _ _ | _ 2 3 |
| _ _ 1 | 8 _ _ | 4 _ 5 |
| _ _ 5 | _ 9 2 | _ _ _ |
----------------------------
| 2 _ _ | _ _ _ | 1 3 _ |
| _ 1 _ | _ 7 _ | _ 4 _ |
| _ 6 4 | _ _ _ | _ _ 8 |
----------------------------
| _ _ _ | 5 3 _ | 2 _ _ |
| 1 _ 9 | _ _ 6 | 4 _ _ |
| 4 _ _ | _ _ 9 | _ 8 _ |
----------------------------The point is to get to fill in the grid so that the numbers 1 through 9 appear only once in every horizontal row, every vertical column and every 3x3 mini-box.My program works just fine the way I wanted it to, but it looks like it's not coming up with any result anytime soon.Any idea on a better algorithm than just plugging in random numbers and use natural selection?

---

AKA G.A.S.B.Y.George Absolutely Stupid Bush the Younger

start with the most common number in the grid and solve for possible other locations - if you look at your example for number 4 you will find solutions for 2 of the missing 4's fairly easily:----------------------------
| _ 4 _ | 1 _ _ | _ 2 3 |
| _ _ 1 | 8 _ _ | 4 _ 5 |
| _ _ 5 | 4 9 2 | _ _ _ |
----------------------------
| 2 _ _ | _ _ _ | 1 3 _ |
| _ 1 _ | _ 7 _ | _ 4 _ |
| _ 6 4 | _ _ _ | _ _ 8 |
----------------------------
| _ _ _ | 5 3 4 | 2 _ _ |
| 1 _ 9 | _ _ 6 | 4 _ _ |
| 4 _ _ | _ _ 9 | _ 8 _ |
----------------------------and that gives you the last one.people who like to play can usehttp://www.websudoku.com/
or
JigsawdokuEnjoy.Edited by RAZD, : No reason given.Edited by RAZD, : example

---

Join the effort to unravel AIDS/HIV, unfold Proteomes, fight Cancer,
compare Fiocruz Genome and fight Muscular Dystrophy with Team EvC! (click)

---

we are limited in our ability to understand
by our ability to understand

​

RebelAAmericanOZen[Deist
... to learn ... to think ... to live ... to laugh ...
to share.

my father is a graph theorist, and plays sudoku for fun. he actually has an algorithm which solves them fairly quickly. i don't think it's "brute force" solving (like yours), but i know it's not optimal.i'll ask him, maybe i can post it. it's written in maple if anyone here has that.edit: curious. the program fails to solve this one.Edited by arachnophilia, : No reason given.

---

I wrote a brute force (with pruning) sudoku solver. There are no solutions to this particular puzzle.Here is the VS7 file for it.http://personalwebs.oakland.edu/...is/Misc/Sudoku_Solver.zipIf you navigate to bin\release, you can run the program. It's just a little C# app.Open the project and check out the algo if you want.I was going to combine this algo with a scanning/smart guessing one to beef up the speed. With this solver, it solves 99% of the puzzles instantly and will occasionally lock up with the wrong type of board (it would eventually solve the problem, but 36! is quite a few iterations!)For those who don't have visual studios and care about this, here is the meat of the algo...

private bool CanSolveSegment(int row, int col, int guess)
{
	if(++guess >= 10)return false;
	if(num[row,col]==0)
	{
		for(int i=1; i<=9; i++)
		{
			if(Possible(row, col, i))
			{
				num[row,col]=i;
				if(CanSolveSegment(row, col, 0))
				{
					return true;
				}
				num[row,col]=0;
			}
		}
		return false;
	}
	row++;
	if(row >= 9)
	{
		col++;
		if(col >= 9)return true;
		row=0;
	}
	return CanSolveSegment(row, col, 0);
}

private bool Possible(int row, int col, int guess)
{
	for(int x=0; x

So... Start if off by calling...CanSolveSegment(0,0,0);I'm sure the programmers can figure it out from there.Edit: This code looks all nice and pretty when it's tabbed out. Doesn;t show up on the forum though. Whatever.Also.. You don't need to pass 'guess' as a parameter to CanSolveSegment (what a stupid name for the function), you can just start a counter at 0. That was for something else.Oh, thanks for fixing the code Mod. Tricky business adding the code tags to code. Learn something every day.Edited by Chronos, : No reason given.Edited by Chronos, : No reason given.Edited by AdminModulous, : added dbcode 'code' to make the code nice and prettyEdited by Chronos, : No reason given.Edited by Chronos, : No reason given.

----------------------------
| 8 4 6 | 1 5 7 | 9 2 3 |
| 9 2 1 | 8 6 3 | 4 7 5 | - dup 4 in column 7 kept
| 3 7 5 | 4 9 2 | 8 6 1 |
----------------------------
| 2 9 8 | 6 4 5 | 1 3 7 |
| 5 1 3 | 9 7 8 | 6 4 2 |
| 7 6 4 | 3 2 1 | 5 9 8 |
----------------------------
| 6 8 7 | 5 3 4 | 2 1 9 |
| 1 3 9 | 2 8 6 | 7 5 4 | - dup 4 in column 7 moved to column 9
| 4 5 2 | 7 1 9 | 3 8 6 |
----------------------------

---

Join the effort to unravel AIDS/HIV, unfold Proteomes, fight Cancer,
compare Fiocruz Genome and fight Muscular Dystrophy with Team EvC! (click)

---

we are limited in our ability to understand
by our ability to understand

​

RebelAAmericanOZen[Deist
... to learn ... to think ... to live ... to laugh ...
to share.

there are two 4's in column 7see previous message for MY solution (with fix)Edited by RAZD, : No reason given.

---

Join the effort to unravel AIDS/HIV, unfold Proteomes, fight Cancer,
compare Fiocruz Genome and fight Muscular Dystrophy with Team EvC! (click)

---

we are limited in our ability to understand
by our ability to understand

​

RebelAAmericanOZen[Deist
... to learn ... to think ... to live ... to laugh ...
to share.

has two 4's

ah, i figured there was a duplication i didn't notice...your fix, btw, is the only fix. leaving the lower four where it is (and making the one above blank) leaves the puzzle unsolvable.Edited by arachnophilia, : No reason given.

You guys are way smarter than me.Yes, that 4 was suppose to be a 7. My mistake.

---

AKA G.A.S.B.Y.George Absolutely Stupid Bush the Younger

The start form: -------------------------
| 3 9 _ | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | 4 2 _ |
| _ _ _ | 5 7 6 | _ _ _ |
-------------------------
| 4 _ _ | _ _ _ | 1 8 _ |
| 5 _ _ | 2 _ 4 | _ _ 9 |
| _ 2 6 | _ _ _ | _ _ 7 |
-------------------------
| _ _ _ | 9 3 1 | _ _ _ |
| _ 8 7 | _ _ _ | _ _ _ |
| _ _ _ | _ _ _ | _ 6 5 |
-------------------------I got this far before getting stymied: -------------------------
| 3 9 X | _ _ _ | 7 5 6 |
| 7 6 5 | _ _ _ | 4 2 _ |
| _ _ _ | 5 7 6 | _ _ _ |
-------------------------
| 4 3 9 | _ _ _ | 1 8 2 |
| 5 7 Y | 2 X 4 | 6 3 9 |
| X 2 6 | _ _ _ | 5 4 7 |
-------------------------
| 6 5 _ | 9 3 1 | _ 7 _ |
| _ 8 7 | _ _ _ | _ _ _ |
| _ _ 3 | _ _ _ | _ 6 5 |
-------------------------Note the "X" and "Y" space fillers above.Now, I have determined (amongst other things) that the locations marked by the "X" and "Y" needs to be either "1" or "8", with all three of the "X's" being the same value, and the "Y" being the other value. Having the answer key available, I know that all my solutions so far are correct, and that X=8 and Y=1.Now for lack of a better idea, I tried assuming that X=1 (incorrect). I, from there, filled in the rest of the values, but the results had a glitch. I then tried assuming that X=8 (correct). I, from there, again solved for the rest of the values, but again got results with a glitch. Even then, all the values were correct (per the solution information) except for three locations. Perhaps the bad second results were because of some logic error on my part, but I haven't yet gone back and tried redoing it.Here is the solution: -------------------------
| 3 9 8 | 1 4 2 | 7 5 6 |
| 7 6 5 | 8 9 3 | 4 2 1 |
| 2 1 4 | 5 7 6 | 3 9 8 |
-------------------------
| 4 3 9 | 6 5 7 | 1 8 2 |
| 5 7 1 | 2 8 4 | 6 3 9 |
| 8 2 6 | 3 1 9 | 5 4 7 |
-------------------------
| 6 5 2 | 9 3 1 | 8 7 4 |
| 9 8 7 | 4 6 5 | 2 1 3 |
| 1 4 3 | 7 2 8 | 9 6 5 |
-------------------------I include the solution because, unlike crossword puzzles, knowing the solution doesn't really detract from trying to figure out how to get to that solution.What I am looking for, it what key information/observation am I missing at the middle version above? Is this one indeed as tough as it seems to be, or am I missing something that should be obvious?MooseAdded by edit: BTW, I may soon be away from the internet for 24 hours. Unless I power up the generator at home, plug in the clunky laptop, and connect to the slower than hell dial-up. Which I probably will do.Edited by Minnemooseus, : See above.

Probably a glitch the second time. I was able to solve and got the same result as you've given.One of my approaches is to look for paired spaces in a box where one or the other must be a certain number: -------------------------
| 3 9 _ | _ _ _ | _ _ _ |
| _ _ _ | B C D | 4 2 _ |
| _ _ _ | 5 7 6 | E E _ |
-------------------------
| 4 _ F | _ _ _ | 1 8 _ |
| 5 _ _ | 2 _ 4 | _ _ 9 |
| F 2 6 | _ _ _ | _ _ 7 |
-------------------------
| _ _ _ | 9 3 1 | _ _ _ |
| _ 8 7 | _ _ _ | _ A A |
| _ _ _ | _ _ _ | _ 6 5 |
-------------------------Either A must be 1,
B or D must be 3 and C or D must be 9
Either E and either F must be 9This helps limit the possibilities. With this approach I did not need to assume values, they were derived by elimination of other possibilities.ps --http://www.websudoku.com/ allows you to set options to have more than one number in a spot. I use this and would enter "11" for A, B would be "33" C would be "99" (as would E and F) and D would be "39" -- this way it is easy to see which ones have limits but are not finalized.I also like to play on Jigsawdoku where you drag and drop tiles for the numbers.You can time both to see how you do, and set them for different difficulties and setups.(and curse you dan for getting me addicted ... )Edited by RAZD, : added ps

---

Join the effort to unravel AIDS/HIV, unfold Proteomes, fight Cancer,
compare Fiocruz Genome and fight Muscular Dystrophy with Team EvC! (click)

---

we are limited in our ability to understand
by our ability to understand
RebelAAmericanOZen[Deist
... to learn ... to think ... to live ... to laugh ...
to share.

i asked my father how his program works. he said something to the extent of:it fills in all possible answers for each space, and looks for forced removes. repeat. i've also seen him play websudoku in a similar manner -- filling multiple potential numbers in a square, and eliminating impossibles. apparently, this is a pretty effective way to solve the puzzles. the program usually does it less than a dozen cycles.

---

In general, using a random number generator in the equivalent of a graph search problem is a bad idea. The 'brute force' method would be to traverse the graph of all possible boards emanating from your start board and discarding paths that fail.You can check each node in the graph as you build it and stop building certain branches as they fail.At least this is how we learned to solve these kinds of things in college CS courses. Treat the problem as a pathing problem and use well known path finding algorithms to solve it.

---

Of course, biblical creationists are committed to belief in God's written Word, the Bible, which forbids bearing false witness; --AIG (lest they forget)

I think the fill in each square with all numbers, remove repeated ones for all filled in numbers approach is going to be the best. The Soduko board is relatively small, so complicated algorithms for solving it are going to be OTT

The algorithm need not be all that complicated. It is the approach to solving the problem that needs to be thought of in terms of a path finding problem.In fact, Chronos' solution is equivalent to a depth-first-search of a graph of all possible boards in exactly the way I described.

---

Of course, biblical creationists are committed to belief in God's written Word, the Bible, which forbids bearing false witness; --AIG (lest they forget)