Asking for advice from fellow programmers on sudoku.

What is the purpose of the 'guess' argument? You never pass it to recursion so it will always be 1 upon entering each call to 'CanSolveSegment'.Am I missing something?

---

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 it is almost always possible to solve a sudoku by using logic. You shouldn't have to use brute force, or guessing.Like it has been mentioned on the thread, a way of looking at it is this.In principle, every field can have nine values. But you have to subtract the values that are in the same quadrant, the same row, and the same column.Look at the uppe left field:---------------------------
| X 4 _ | 1 _ _ | _ 2 3 |
| _ _ 1 | 8 _ _ | 7 _ 5 |
| _ _ 5 | _ 9 2 | _ _ _ |
----------------------------
| 2 _ _ | _ _ _ | 1 3 _ |
| _ 1 _ | _ 7 _ | _ 4 _ |
| _ 6 4 | _ _ _ | _ _ 8 |
----------------------------
| _ _ _ | 5 3 _ | 2 _ _ |
| 1 _ 9 | _ _ 6 | 4 _ _ |
| 4 _ _ | _ _ 9 | _ 8 _ |
----------------------------To begin with, it must have a value of {1,2,3,4,5,6,7,8,9}But {1,4,5} is in the same quadrant, so this leaves only
{2,3,6,7,8,9}{1,2,3,4} is in the same row, leaving{6,7,8,9}{1,2,4} is in the same column, but they have been removed form the set.You can do this for all open fields in the puzzle, this could be implemented quite simple.You could then end up with less than 81 sets.there now are many strategies open to you.1. Singles:If you have a set consisting of only 1 number, then you know this must be the right number. Fill it out, and remove the number you just placed from all the sets in the same Quadrant, Row and Column. (this goes for everytime you place a number)2. Pairs: If you have two sets in the same quadrant, the same row, or the same column, that have the same two members. Then you can remove these members from all of the other sets in the same Q,R or C (depending on where they appear).3. Tuples: The same as above. If you have three similar 3-sets in a Q,R or C. 4-sets etc.4. Filling: Each Q, R an C must have all nine numbers. Check the sets for each of these to find if one number only appears once. That is, the number can only be placed in one of the nine fields of the Q,R or C. then you know where the number should be set.5. "Place Holding": Imagine that the number 1 can be placed only 2 or 3 places in a quadrant. If these to places align on a row, or on a column, then you know, that the number one cannot be placed anywhere else on that row or column, and you can remove it from all of the sets on each row or column.I guess there must be more strategies, but these are those I use when solving in my head.If you just get the set representation up and running in a program, the strategise should alle be simple to implement.

The guess argument to CanSolveSegment is actually worthless. Maybe vestigial?Here is the same thing in perl:

#!/usr/bin/perl -w
no warnings "recursion";

use strict;

# evc_board.txt contains
#
#040100023
#001800405
#005092000
#200000130
#010070040
#064000008
#000530200
#109006004
#400009080
my @board = &build_board_from_file('evc_board.txt');
my @orig_board = @board;

&print_board(@board);

if(!&CanSolveSegment(0,0)){
   print "Cannot Solve Board!";
}

print "\n+++++++++++\n\n";
&print_board(@board);

sub CanSolveSegment {

   my ($row, $col) = @_;

   # Is this location unsolved?
   if($board[$row][$col] == 0){

      # Try all possibilities
      for( my $i=1; $i<=9; $i++){

         # Check to see if the number is legal for this location.
         if(&Possible($row, $col, $i)){

            # If it is go ahead and put the number there.
            $board[$row][$col] = $i;

            # Then try to solve the rest of the puzzle
            # with that number fixed.
            return 1 if(&CanSolveSegment($row, $col));

            # If you can't, clear the number from the
            # location and try the next.
            $board[$row][$col] = 0;
         }
      }

      # If none of the numbers work, this is a dead end.
      return 0;
   }

   # It is solved so move to the next location.
   $row++;
   if($row >= 9){
      $col++;

      # If we have hit all the locations, we are done.
      return 1 if($col >= 9);
      $row = 0;
   }

   # Try to solve the next location. (Yay tail recursion!)
   return &CanSolveSegment($row, $col);
}

sub Possible {

   my ($row, $col, $guess) = @_;

   # If the number is anywhere else in this row it is invalid.
   for(my $i=0; $i<9; $i++){
      next if $i == $row;
      return 0 if $board[$i][$col] == $guess;
   }

   # If the number is anywhere else in the column it is invalid.
   for(my $i=0; $i<9; $i++){
      next if $i == $col;
      return 0 if $board[$row][$i] == $guess;
   }

   # If the number is anywhere else in the quadrant it is invalid.
   my ($qrow,$qcol) = (0,0);
   $qrow = 3 if $row > 2 && $row <= 5;
   $qrow = 6 if $row > 5;
   $qcol = 3 if $col > 2 && $col <= 5;
   $qcol = 6 if $col > 5;

   for(my $i=$qrow; $i<$qrow+3; $i++){
      for(my $j=$qcol; $j<$qcol+3; $j++){
         return 0 if(!($row == $i && $col == $j)
            && $board[$i][$j] == $guess);
      }
   }

   # Otherwise, it is okay.
   return 1;
}

sub print_board {
   my @board = @_;

   for(my $row=0; $row<9; $row++){
      for(my $col=0; $col<9; $col++){
         print $board[$row][$col];
         print '|' if $col == 2 || $col == 5;
      }
      print "\n";
      print "-----------\n" if $row == 2 || $row == 5;
   }
}

sub build_board_from_file {

   my $file = shift;
   my @board = ();
   my $row = 0;

   open BOARDFILE, $file or die "Cannot open $file for reading!";

   while(){

      chomp;
      die "Invalid board file." unless /^\d{9}$/;
      my @numbers = /^(\d)(\d)(\d)(\d)(\d)(\d)(\d)(\d)(\d)$/;

      for(my $col=0; $col<9; $col++){
         $board[$row][$col] = $numbers[$col];
      }
      $row++;
   }
   return @board;
}

---

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

Haha, and when I could come up with an algo that resembles your head, I'd win a nobel prize or something similar.

Well, when I say "in my head" I do mean I have the soduku in front of me and a pencil in my hand, so it's not all that For some of the strategies, I write notes down on the soduku For instance, if I find that to fields can only have the same to numbers in them, I write the numbers in with small letters etcEdited by kongstad, : No reason given.

Prolog is a lovely language, and is well-suited to solving Sudoku.In one of the more popular flavours of Prolog, the rules of Sudoku may be described:

sudoku_grid([_,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,_]).

solve_sudoku :-

	sudoku_grid([A1,A2,A3,A4,A5,A6,A7,A8,A9],
		    [B1,B2,B3,B4,B5,B6,B7,B8,B9],
		    [C1,C2,C3,C4,C5,C6,C7,C8,C9],
		    [D1,D2,D3,D4,D5,D6,D7,D8,D9],
		    [E1,E2,E3,E4,E5,E6,E7,E8,E9],
		    [F1,F2,F3,F4,F5,F6,F7,F8,F9],
		    [G1,G2,G3,G4,G5,G6,G7,G8,G9],
		    [H1,H2,H3,H4,H5,H6,H7,H8,H9],
		    [I1,I2,I3,I4,I5,I6,I7,I8,I9]),

	Row1 = [A1,A2,A3,A4,A5,A6,A7,A8,A9],
	Row2 = [B1,B2,B3,B4,B5,B6,B7,B8,B9],
	Row3 = [C1,C2,C3,C4,C5,C6,C7,C8,C9],
	Row4 = [D1,D2,D3,D4,D5,D6,D7,D8,D9],
	Row5 = [E1,E2,E3,E4,E5,E6,E7,E8,E9],
	Row6 = [F1,F2,F3,F4,F5,F6,F7,F8,F9],
	Row7 = [G1,G2,G3,G4,G5,G6,G7,G8,G9],
	Row8 = [H1,H2,H3,H4,H5,H6,H7,H8,H9],
	Row9 = [I1,I2,I3,I4,I5,I6,I7,I8,I9],

	% each row must contain all numbers 1-9
	permutation(Row1, [1,2,3,4,5,6,7,8,9]),
	permutation(Row2, [1,2,3,4,5,6,7,8,9]),
	permutation(Row3, [1,2,3,4,5,6,7,8,9]),
	permutation(Row4, [1,2,3,4,5,6,7,8,9]),
	permutation(Row5, [1,2,3,4,5,6,7,8,9]),
	permutation(Row6, [1,2,3,4,5,6,7,8,9]),
	permutation(Row7, [1,2,3,4,5,6,7,8,9]),
	permutation(Row8, [1,2,3,4,5,6,7,8,9]),
	permutation(Row9, [1,2,3,4,5,6,7,8,9]),

	Column1 = [A1,B1,C1,D1,E1,F1,G1,H1,I1],
	Column2 = [A2,B2,C2,D2,E2,F2,G2,H2,I2],
	Column3 = [A3,B3,C3,D3,E3,F3,G3,H3,I3],
	Column4 = [A4,B4,C4,D4,E4,F4,G4,H4,I4],
	Column5 = [A5,B5,C5,D5,E5,F5,G5,H5,I5],
	Column6 = [A6,B6,C6,D6,E6,F6,G6,H6,I6],
	Column7 = [A7,B7,C7,D7,E7,F7,G7,H7,I7],
	Column8 = [A8,B8,C8,D8,E8,F8,G8,H8,I8],
	Column9 = [A9,B9,C9,D9,E9,F9,G9,H9,I9],

	% each column must contain all numbers 1-9
	permutation(Column1, [1,2,3,4,5,6,7,8,9]),
	permutation(Column2, [1,2,3,4,5,6,7,8,9]),
	permutation(Column3, [1,2,3,4,5,6,7,8,9]),
	permutation(Column4, [1,2,3,4,5,6,7,8,9]),
	permutation(Column5, [1,2,3,4,5,6,7,8,9]),
	permutation(Column6, [1,2,3,4,5,6,7,8,9]),
	permutation(Column7, [1,2,3,4,5,6,7,8,9]),
	permutation(Column8, [1,2,3,4,5,6,7,8,9]),
	permutation(Column9, [1,2,3,4,5,6,7,8,9]),

	Square1 = [A1,A2,A3,B1,B2,B3,C1,C2,C3],
	Square2 = [A4,A5,A6,B4,B5,B6,C4,C5,C6],
	Square3 = [A7,A8,A9,B7,B8,B9,C7,C8,C9],
	Square4 = [D1,D2,D3,E1,E2,E3,F1,F2,F3],
	Square5 = [D4,D5,D6,E4,E5,E6,F4,F5,F6],
	Square6 = [D7,D8,D9,E7,E8,E9,F7,F8,F9],
	Square7 = [G1,G2,G3,H1,H2,H3,I1,I2,I3],
	Square8 = [G4,G5,G6,H4,H5,H6,I4,I5,I6],
	Square9 = [G7,G8,G9,H7,H8,H9,I7,I8,I9],

	% each 3x3 square must contain all numbers 1-9
	permutation(Square1, [1,2,3,4,5,6,7,8,9]),
	permutation(Square2, [1,2,3,4,5,6,7,8,9]),
	permutation(Square3, [1,2,3,4,5,6,7,8,9]),
	permutation(Square4, [1,2,3,4,5,6,7,8,9]),
	permutation(Square5, [1,2,3,4,5,6,7,8,9]),
	permutation(Square6, [1,2,3,4,5,6,7,8,9]),
	permutation(Square7, [1,2,3,4,5,6,7,8,9]),
	permutation(Square8, [1,2,3,4,5,6,7,8,9]),
	permutation(Square9, [1,2,3,4,5,6,7,8,9]),

	% print out solution
	format(Row1),
	format(Row2),
	format(Row3),
	format(Row4),
	format(Row5),
	format(Row6),
	format(Row7),
	format(Row8),
	format(Row9).

Having described the problem, Prolog is now in a position to solve the problem, all without us having to write more code:

?- solve_sudoku.

[8, 4, 6, 1, 5, 7, 9, 2, 3]
[9, 2, 1, 8, 6, 3, 4, 7, 5]
[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]
[4, 5, 2, 7, 1, 9, 3, 8, 6]

Ok, sudoku experts, help me solve the following. This is as far as I got with this particular one.4 2 0 | 0 6 0 | 3 1 7
0 1 8 | 7 0 2 | 0 4 0
0 0 0 | 4 0 1 | 8 2 9
-------------------------
1 0 2 | 3 8 0 | 0 7 4
0 8 0 | 0 2 4 | 1 3 0
5 3 4 | 1 7 6 | 2 9 8
-------------------------
2 0 0 | 6 0 3 | 7 8 1
8 0 1 | 2 0 7 | 9 6 3
6 7 3 | 0 1 0 | 4 5 2Can't seem to go anywhere from here.Added by edit.Nevermind, I got it. It just required one more logical step that I never considered: guess and check!Edited by Tazmanian Devil, : No reason given.Edited by Tazmanian Devil, : No reason given.

From two summers ago, but no one brought it up.http://scienceblogs.com/.../2012/07/01/worlds-hardest-sudokuwhich leads to404On the conventional 1 to 5 star, easy to hard scale, they rate this one at 11 stars. None of the conventional methodology is going to do you any good.Good luck. One commenter at the science blog page said he solved it in 6 hours.Moose Edited by Minnemooseus, : Replace "last summer" with "two summers ago". Also fixed 2 typos/brain farts.