You are viewing kristiannielsen

Kristian Nielsen - Sudoku solver
June 4th, 2006
10:03 pm

[Link]

Previous Entry Share Next Entry
Sudoku solver

Sudoku solver

There are probably tons of these already available, but here is a quick sudoku solver (in Perl):

#! /usr/bin/perl

# Example:
#
# echo $'      2  \n  1 9  4 \n 2 1 5  9\n3     6  \n  68 41 5\n  427 8  \n   51    \n     7 3 \n79    5  '| perl sudoku-solve.pl
#

use strict;
use warnings;

my $s = read_sudoku();

my $res= solve($s);

if($res) {
  print_sudoku($res);
  print "Got it!\n";
} else {
  print "Failed :-(\n";
}

exit 0;

sub solve {
  my ($s)= @_;

  my $res= try_solve($s);

  return $s if $res eq 'SOLVED';

  return undef if $res eq 'FAIL';

  # Make a guess, backtracking if we were wrong.
  # Try to find some field where there are only two possibilities.
  my ($a, $b);

 OUTER:
  for my $i (0..8) {
  INNER:
    for my $j (0..8) {
      next INNER if keys(%{$s->[$i][$j]}) == 1;
      if(keys(%{$s->[$i][$j]}) == 2) {
        ($a,$b)= ($i,$j);
        last OUTER;
      } elsif(!defined($a)) {
        ($a,$b)= ($i,$j);
      }
    }
  }

  die "Internal?!?" unless defined($a);

  for my $choice (keys %{$s->[$a][$b]}) {
    my $s_copy = [ map { [ map { { %$_ } } @$_ ] } @$s ];
    $s_copy->[$a][$b] = { $choice => 1 };
    my $res= solve($s_copy);
    return $res if defined($res); # Got it!
  }
  return undef;                 # Failed.
}

sub read_sudoku {
  my $s= [ ];

  for(my $i = 0; $i < 9; $i++) {
    my $x = <STDIN>;
    chomp($x);
    if(length($x) < 9) {
      print STDERR "Short line: '$x'\n";
      redo;
    }
    for(my $j = 0; $j < 9; $j++) {
      my $entry= substr($x, $j, 1);
      $s->[$i][$j] = { map(($_ => 1), ($entry eq ' ' ? (1..9) : ($entry))) };
    }
  }

  return $s;
}

sub print_sudoku {
  my ($s) = @_;
  for(my $i = 0; $i < 9; $i++) {
    print "---------------------\n" unless $i % 3;
    for(my $j= 0; $j < 9; $j++) {
      print "|" unless $j % 3;
      print((keys(%{$s->[$i][$j]}) > 1 ? ' ' : keys(%{$s->[$i][$j]})),
            ($j == 8 ? "|\n" : " "));
    }
  }
  print "---------------------\n";
}

sub try_solve {
  my ($s)= @_;

  my $done;
  my $progress;

  do {
    $done = 1;                 # Set false when non-determined field found
    $progress= undef;

    for(my $i = 0; $i < 9; $i++) {
      for(my $j = 0; $j < 9; $j++) {
        my $x = $s->[$i][$j];
        return 'FAIL' if keys(%$x) == 0;
        $done = undef if keys(%$x) > 1;
        my $h1= { %$x };
        my $h2= { %$x };
        my $h3= { %$x };
        for(my $a = 0; $a < 9; $a++) {
          if($a != $i) {
            my $y = $s->[$a][$j];
            delete $h1->{$_} for keys(%$y);
            if(keys %$y == 1) {
              $progress = 1 if delete $x->{(keys(%$y))[0]};
            }
          }
          if($a != $j) {
            my $y = $s->[$i][$a];
            delete $h2->{$_} for keys(%$y);
            if(keys %$y == 1) {
              $progress = 1 if delete $x->{(keys(%$y))[0]};
            }
          }
          my $b = 3*int($i/3) + int($a / 3);
          my $c = 3*int($j/3) + $a % 3;
          if($b != $i || $c != $j) {
            my $y = $s->[$b][$c];
            delete $h3->{$_} for keys(%$y);
            if(keys %$y == 1) {
              $progress = 1 if delete $x->{(keys(%$y))[0]};
            }
          }
        }
        return 'FAIL' if keys(%$h1) > 1 || keys(%$h2) > 1 || keys(%$h3) > 1;
        if(keys(%$h1) == 1) {
          delete($x->{$_}) for grep(!$h1->{$_}, keys %$x);
        } elsif(keys(%$h2) == 1) {
          delete($x->{$_}) for grep(!$h2->{$_}, keys %$x);
        } elsif(keys(%$h3) == 1) {
          delete($x->{$_}) for grep(!$h3->{$_}, keys %$x);
        }
      }
    }
  } while(!$done && $progress);

  return $done ? 'SOLVED' : 'UNSOLVED';
}

I wanted to use strategy rather than brute force (not sure what the complexity of that would be; the above seems to solve puzzles in a split second). Strategies are

  • If a digit is already in a row/column/square, it cannot occur a second time.
  • A digit is known to occur in a field if it cannot occur in any of the 8 other fields of a row/column/square.
These are not sufficient to solve (all) puzzles. Here is another example strategy: If we know in some 3x3 square that some particular digit can only occur in a particular row/column, then that digit can not occur in that digit/column in any other square.

However, at this point I just added a quick backtracking step. It seems the implemented strategies are sufficiently close to a full solution that only very little backtracking is needed, and a solution is usually arrived at instantly.

This example took perhaps an hour to put together. It is a nice example of the usefulness of learning Perl. Because Perl is well suited for a very wide range of programming tasks, the investment needed to learn the language pays off very well. Perl can be used for 2-minute one-liners like this to massage a .h file:

perl -nle 'print "#define prefix_$1 $1" if /^\s*[a-zA-z0-9_ ]+\s+([_a-zA-Z0-9]+)\s*\(/ ' *.h
It can be used for quick hacks like this sudoku solver. And it can be used for full-scale application development.

If I were to use different languages for these different tasks, I would have less time to spend on learning each one, and thus would work less efficiently at all of them.

Tags: ,

(6 comments | Leave a comment)

Comments
 
From:(Anonymous)
Date:June 8th, 2007 04:26 pm (UTC)

Give me link to XRumer 3.0 software

(Link)
Who know some info about xrumer? Or website with description...

It's very interesting program, but I forgot url :(

help me!!!

P.S. Hmmm... this forum category is interesting....



From:(Anonymous)
Date:June 17th, 2007 06:14 am (UTC)

c

(Link)

.Good luck!





From:(Anonymous)
Date:April 14th, 2008 02:23 pm (UTC)

a nick is required with bbcode does not alter out to set pictures

(Link)
Hay
take delight to conceive of with BBcode :( for me does not revolt out to manufacture references to the absorbing pictures and video on the topic. Or heave up b abandon down affiliation on this topic
From:sudoku_girl
Date:January 9th, 2010 07:03 am (UTC)

sudoku solver

(Link)
hmm interesting, I just finished my sudoku solver site sudoku solver using an open source, It does work and solves sudoku, but it's not very visually appealing.

Would you mind if I played around with your sudoku solver code?
From:kristiannielsen
Date:January 9th, 2010 08:12 am (UTC)

Re: sudoku solver

(Link)
Feel free! I hereby release the source code for the sudoku solver under the GPL, either version 2 or, at your option, any later version of the GPL license.
From:(Anonymous)
Date:May 11th, 2010 01:13 am (UTC)

Thanks

(Link)
Thanks For sharing

Sudoku Strategies (http://sudokustrategies.net)
Powered by LiveJournal.com