Rätsel der Woche 2007/7

Aufgabe

         Schreibe ein Programm, das ein gegebenes, unvollständig
         gelöstest, Sudoku-Rätsel vollständig löst, sofern das möglich ist
         und mit einer passenden Warnung abbricht, wenn in der Angabe
         Widersprüche sind. Das zu lösende Sudokurätsel wird dem
         Program als erster Parameter übergeben, als fortlaufender
         String von 81 Zeichen, wobei noch nicht belegte Felder durch
         einen Punkt dargestellt werden. Die 81 Zeichen sind so zu
         verstehen, daß das Sudoku-Quadrat damit Zeilenweise aufgefüllt wird.

Hintegrundinformationen

Forumsdiskussion

Teilnehmer alphabetisch nach Nickname

1. docsnyder (2 Lösungen)
2. ishka (1 Lösung)
3. murphy (1 Lösung)
4. taulmarill (1 Lösung)

Überblick über die Lösungen

• einfach:

  .5.....4.31..6..98...1.8.....3.9.6...2.8.6.7...5.1.2.....3.7...97..2..31.3.....6.

• kompliziert:

  ........1.....2.3...4..5..........5......46...17.8........1...7.2.9.....5.....4..

Die Lösungen im Detail

docsnyder-1

• sudoku-docsnyder.tar.gz: Docsnyders Lösungen im Quellcode

#!/bin/perl

use strict;
use warnings;

my(@board, $cnt);

sub initBoard {
  if ( $#ARGV || (length($ARGV[0]) != 81) ) {
    printf("ERROR: invalid input (need %s)\n", $#ARGV ? "argument" : "81 characters");
    exit(-1);
  }

  map { my $row=$_; map { $board[$row][$_] = 0 } ( 0..8 ) } ( 0..8 );

  for my $row ( 0..8 ) {
    for my $col ( 0..8 ) {
      my($val) = substr($ARGV[0], $row*9 + $col, 1);

      if ( ($val ne '.') && (existsInRow($row, $val) || existsInCol($col, $val) || existsInSquare($row, $col, $val)) ) {
        printf("ERROR: invalid input '$val' (row: %d, col: %d)\n", $row+1, $col+1);
        exit(-1);
      }

      $board[$row][$col] = ($val eq '.') ? 0 : $val;
    }
  }
}

sub nextCell {
  my($row, $col) = @_;

  $row++ unless ( ($col = ($col + 1) % 9) );

  return($row, $col);
}

sub existsInRow {
  my($row, $val) = @_;

  map { return(1) if ( $board[$_[0]][$_] == $_[1] ) } ( 0..8 );

  return(0);
}

sub existsInCol {
  map { return(1) if ( $board[$_][$_[0]] == $_[1] ) } ( 0..8 );

  return(0);
}

sub existsInSquare {
  my($row, $col, $val) = ( 3 * int($_[0] / 3), 3 * int($_[1] / 3), $_[2] );

  return(($val == $board[$row  ][$col]) || ($val == $board[$row  ][$col+1]) || ($val == $board[$row  ][$col+2]) ||
         ($val == $board[$row+1][$col]) || ($val == $board[$row+1][$col+1]) || ($val == $board[$row+1][$col+2]) ||
         ($val == $board[$row+2][$col]) || ($val == $board[$row+2][$col+1]) || ($val == $board[$row+2][$col+2]));
}

sub setCell {
  my($row, $col) = @_;

  return(showBoard("solution ".++$cnt)) if ( $row == 9 );

  if ( $board[$row][$col] ) {
    setCell(nextCell($row, $col));
  }
  else {
    for ( 1..9 ) {
      if ( ! existsInRow($row, $_) && ! existsInCol($col, $_) && ! existsInSquare($row, $col, $_) ) {
        $board[$row][$col] = $_;
        setCell(nextCell($row, $col));
        $board[$row][$col] = 0;
      }
    }
  }
}

sub showBoard {
  printf("======================== $_[0] =========================\n");

  for ( 0..8 ) {
    printf("------+-------+------\n") if ( $_ && ! (($_ + 0) % 3) );
    printf("%s %s %s | %s %s %s | %s %s %s\n", @{$board[$_]});
  }
}

initBoard();
showBoard("initial");
setCell(0, 0);

docsnyder-2

• sudoku-docsnyder.tar.gz: Docsnyders Lösungen im Quellcode

#!/bin/perl

use strict;
use warnings;

my(@board, @marks, @squCnt);

#---------------------------- initBoard() ------------------------------------#
sub initBoard {
  if ( $#ARGV || (length($ARGV[0]) != 81) ) {
    printf("ERROR: invalid input (need %s)\n", $#ARGV ? "argument" : "81 characters");
    exit(-1);
  }

  map { my $row=$_; map { $board[$row][$_] = 0 } ( 0..8 ) } ( 0..8 );
  map { my $row=$_; map { my $col=$_; map { $marks[$row][$col][$_] = 0 } ( 1..9 ) } ( 0..8 ) } ( 0..8 );
  map { my $squ=$_; map { $squCnt[$squ][$_] = 9 } ( 1..9 ) } ( 0..8 );

  for my $row ( 0..8 ) {
    for my $col ( 0..8 ) {
      my($val) = substr($ARGV[0], $row*9 + $col, 1);

      if ( ($val ne '.') && (existsInRow($row, $val) || existsInCol($col, $val) || existsInSqu($row, $col, $val)) ) {
        printf("ERROR: invalid input '$val' (row: %d, col: %d)\n", $row+1, $col+1);
        exit(-1);
      }

      setCell($row, $col, ($val eq '.') ? 0 : $val);
    }
  }
}

#---------------------------- nextCell() -------------------------------------#
sub nextCell {
  my($row, $col) = @_;

  $row++ unless ( ($col = ($col + 1) % 9) );

  return($row, $col);
}

#---------------------------- existsInRow() ----------------------------------#
sub existsInRow {
  my($row, $val) = @_;

  map { return(1) if ( $board[$row][$_] == $val ) } ( 0..8 );

  return(0);
}

#---------------------------- existsInCol() ----------------------------------#
sub existsInCol {
  my($col, $val) = @_;

  map { return(1) if ( $board[$_][$col] == $val ) } ( 0..8 );

  return(0);
}

#---------------------------- existsInSqu() ----------------------------------#
sub existsInSqu {
  my($row, $col, $val) = ( 3 * int($_[0] / 3), 3 * int($_[1] / 3), $_[2] );

  return(($val == $board[$row]  [$col]) || ($val == $board[$row]  [$col+1]) || ($val == $board[$row]  [$col+2]) ||
         ($val == $board[$row+1][$col]) || ($val == $board[$row+1][$col+1]) || ($val == $board[$row+1][$col+2]) ||
         ($val == $board[$row+2][$col]) || ($val == $board[$row+2][$col+1]) || ($val == $board[$row+2][$col+2]));
}

#---------------------------- markCell() -------------------------------------#
sub markCell {
  my($row, $col, $val) = @_;
  my($squIdx)          = 3*int($row/3)+int($col/3);

  if ( $val ) {
    for my $tmpVal ( 1..9 ) {
      $squCnt[$squIdx][$tmpVal]-- if ( ! $marks[$row][$col][$tmpVal] );

      $marks[$row][$col][$tmpVal] = 1;
    }
  }
}

#---------------------------- markRow() --------------------------------------#
sub markRow {
  my($row, $col, $val) = @_;
  my($squRow) = 3*int($row/3);
  my($cnt) = 0;

  if ( $val ) {
    for my $tmpCol ( 0..8 ) {
      my($squIdx) = $squRow+int($tmpCol/3);

      if ( ! $marks[$row][$tmpCol][$val] ) {
        $squCnt[$squIdx][$val]--;
        $cnt++;
      }

      $marks[$row][$tmpCol][$val] = 1;
    }
  }

  return($cnt);
}

#---------------------------- markRowExceptTwo() -----------------------------#
sub markRowExceptTwo {
  my($row, $col, $col2, $val) = @_;
  my($squRow) = 3*int($row/3);
  my($cnt) = 0;

  if ( $val ) {
    for my $tmpCol ( 0..8 ) {
      next if ( ($tmpCol == $col) || ($tmpCol == $col2) );

      my($squIdx) = $squRow+int($tmpCol/3);

      if ( ! $marks[$row][$tmpCol][$val] ) {
        $squCnt[$squIdx][$val]--;
        $cnt++;
      }

      $marks[$row][$tmpCol][$val] = 1;
    }
  }

  return($cnt);
}

#---------------------------- markCol() --------------------------------------#
sub markCol {
  my($row, $col, $val) = @_;
  my($squCol) = int($col/3);
  my($cnt) = 0;

  if ( $val ) {
    for my $tmpRow ( 0..8 ) {
      my($squIdx) = 3*int($tmpRow/3)+$squCol;

      if ( ! $marks[$tmpRow][$col][$val] ) {
        $squCnt[$squIdx][$val]--;
        $cnt++;
      }

      $marks[$tmpRow][$col][$val] = 1;
    }
  }

  return($cnt);
}

#---------------------------- markColExceptTwo() -----------------------------#
sub markColExceptTwo {
  my($row, $col, $row2, $val) = @_;
  my($squCol) = int($col/3);
  my($cnt) = 0;

  if ( $val ) {
    for my $tmpRow ( 0..8 ) {
      next if ( ($tmpRow == $row) || ($tmpRow == $row2) );

      my($squIdx) = 3*int($tmpRow/3)+$squCol;

      if ( ! $marks[$tmpRow][$col][$val] ) {
        $squCnt[$squIdx][$val]--;
        $cnt++;
      }

      $marks[$tmpRow][$col][$val] = 1;
    }
  }

  return($cnt);
}

#---------------------------- markSqu() --------------------------------------#
sub markSqu {
  my($row, $col, $val)   = @_;
  my($snapRow, $snapCol) = ( 3*int($row/3) , 3*int($col/3) );
  my($cnt) = 0;

  if ( $ val ) {
    for my $subRow ( 0..2 ) {
      for my $subCol ( 0..2 ) {
        my($tmpRow, $tmpCol) = ( $snapRow+$subRow, $snapCol+$subCol);
        my($squIdx)          = 3*int($tmpRow/3)+int($tmpCol/3);

        if ( ! $marks[$tmpRow][$tmpCol][$val] ) {
          $squCnt[$squIdx][$val]--;
          $cnt++;
        }

        $marks[$tmpRow][$tmpCol][$val] = 1;
      }
    }
  }

  return($cnt);
}

#---------------------------- setCell() --------------------------------------#
sub setCell {
  my($row, $col, $val) = @_;

  if ( ! $board[$row][$col] ) {
    markCell($row, $col, $val);
    markRow($row, $col, $val);
    markCol($row, $col, $val);
    markSqu($row, $col, $val);
    $board[$row][$col] = $val;

    return(1);
  }

  return(0);
}

#---------------------------- unsetCell() ------------------------------------#
sub unsetCell {
  my($row, $col, $val) = @_;

  if ( $board[$row][$col] ) {
    $board[$row][$col] = 0;

#    unmarkRow($row, $val);
#    unmarkCol($col, $val);
#    unmarkSqu($row, $col, $val);

    return(1);
  }

  return(0);
}

#---------------------------- findSingles() ----------------------------------#
sub findSingles {
  my($gotSingles) = 0;
  my($hitRow, $hitCol);

  for my $val ( 1..9 ) {
    for my $squIdx ( 0..8 ) {
      my($row, $col) = ( 3*int($squIdx/3), 3*($squIdx%3) );
      my($cnt) = 0;

      for my $subRow ( 0..2 ) {
        for my $subCol ( 0..2 ) {
          my($tmpRow, $tmpCol) = ( $row+$subRow, $col+$subCol );

          if ( ! $marks[$tmpRow][$tmpCol][$val] ) {
            $hitRow = $tmpRow;
            $hitCol = $tmpCol;
            $cnt++;
          }
        }
      }

      if ( $cnt == 1 ) {
        $gotSingles++;
        setCell($hitRow, $hitCol, $val);
      }
    }
  }

  return($gotSingles);
}

#---------------------------- getZeroSubCoords() -----------------------------#
sub getZeroSubCoords {
  my($snapRow, $snapCol, $val, $n) = @_;
  my(@rows, @cols);

  for my $subRow ( 0..2 ) {
    for my $subCol ( 0..2 ) {
      my($row, $col) = ( $snapRow+$subRow, $snapCol+$subCol );

      if ( ! $marks[$row][$col][$val] ) {
        push(@rows, $row);
        push(@cols, $col);

        return(@rows, @cols) if ( @rows == $n );
      }
    }
  }
}

#---------------------------- matchDoublePairs() -----------------------------#
sub matchDoublePairs {
  my($snapRowA, $snapColA, $squIdxB, $val) = @_;
  my($snapRowB, $snapColB) = ( 3*int($squIdxB/3), 3*($squIdxB%3) );
  my(@tmpRowB, @tmpColB, @coordsA, @coordsB);
  my($gotMatch) = 0;

  return(0) if ( ($snapRowA != $snapRowB) && ($snapColA != $snapColB) );

  @coordsA = getZeroSubCoords($snapRowA, $snapColA, $val, 2);
  @coordsB = getZeroSubCoords($snapRowB, $snapColB, $val, 2);

  if ( $snapRowA == $snapRowB ) {
    if ( ($coordsA[0] == $coordsB[0]) && ($coordsA[1] == $coordsB[1]) &&
         ($coordsA[2] == $coordsA[3]) && ($coordsB[2] == $coordsB[3]) ) {
      $gotMatch++;
    }
  }
  else {
    if ( ($coordsA[0] == $coordsA[1]) && ($coordsB[0] == $coordsB[1]) &&
         ($coordsA[2] == $coordsB[2]) && ($coordsA[3] == $coordsB[3]) ) {
      $gotMatch++;
    }
  }

  if ( $gotMatch ) {
    $gotMatch = 0;

    $gotMatch += markRowExceptTwo($coordsA[0], $coordsA[2], $coordsB[3], $val);
    $gotMatch += markRowExceptTwo($coordsB[1], $coordsB[3], $coordsA[2], $val);
    $gotMatch += markColExceptTwo($coordsA[0], $coordsA[2], $coordsB[1], $val);
    $gotMatch += markColExceptTwo($coordsB[1], $coordsB[3], $coordsA[0], $val);
  }

  return($gotMatch);
}

#---------------------------- findDoublePairs() ------------------------------#
sub findDoublePairs {
  my($gotMatch) = 0;

  for my $val ( 1..9 ) {
    for my $squIdxA ( 0..7 ) {
      next if ( $squCnt[$squIdxA][$val] != 2 );

      my($snapRowA, $snapColA) = ( 3*int($squIdxA/3), 3*($squIdxA%3) );

      for my $squIdxB ( ($squIdxA+1)..8 ) {
        next if ( $squCnt[$squIdxB][$val] != 2 );

        $gotMatch += matchDoublePairs($snapRowA, $snapColA, $squIdxB, $val);
      }
    }
  }

  return($gotMatch);
}

#---------------------------- excludeColumn() --------------------------------#
sub excludeColumn {
  my($squIdx, $val, $subCol) = @_;
  my($col) = 3*($squIdx%3) + $subCol;
  my($snapRow) = 3*int($squIdx/3);
  my($gotMatch) = 0;

  for my $row ( 0..8 ) {
    next if ( ($row >= $snapRow) && ($row < ($snapRow + 3)) );

    my($tmpSquIdx) = 3*int($row/3)+int($col/3);

    if ( ! $marks[$row][$col][$val] ) {
      $squCnt[$tmpSquIdx][$val]--;
      $gotMatch++;
    }

    $marks[$row][$col][$val] = 1;
  }

  return($gotMatch);
}

#---------------------------- excludeRow() -----------------------------------#
sub excludeRow {
  my($squIdx, $val, $subRow) = @_;
  my($row) = 3*int($squIdx/3) + $subRow;
  my($snapCol) = 3*($squIdx%3);
  my($gotMatch) = 0;

  for my $col ( 0..8 ) {
    next if ( ($col >= $snapCol) && ($col < ($snapCol + 3)) );

    my($tmpSquIdx) = 3*int($row/3)+int($col/3);

    if ( ! $marks[$row][$col][$val] ) {
      $squCnt[$tmpSquIdx][$val]--;
      $gotMatch++;
    }

    $marks[$row][$col][$val] = 1;
  }

  return($gotMatch);
}

#---------------------------- findStripeInSquare() ---------------------------#
sub findStripeInSquare {
  my($squIdx, $val) = @_;
  my($snapRow, $snapCol) = ( 3*int($squIdx/3), 3*($squIdx%3) );
  my($gotMatch) = 0;

  #--- SEARCH FOR COLUMNS ! --------------------------------------------------#
  for my $subCol ( 0..2 ) {
    my($cnt) = 0;

    for my $subRow ( 0..2 ) {
      $cnt++ if ( ! $marks[$snapRow+$subRow][$snapCol+$subCol][$val] );
    }
    if ( $cnt && ($cnt == $squCnt[$squIdx][$val]) ) {
      $gotMatch += excludeColumn($squIdx, $val, $subCol);
    }
  }

  #--- SEARCH FOR ROWS ! -----------------------------------------------------#
  for my $subRow ( 0..2 ) {
    my($cnt) = 0;

    for my $subCol ( 0..2 ) {
      $cnt++ if ( ! $marks[$snapRow+$subRow][$snapCol+$subCol][$val] );
    }

    if ( $cnt && ($cnt == $squCnt[$squIdx][$val]) ) {
      $gotMatch += excludeRow($squIdx, $val, $subRow);
    }
  }

  return($gotMatch);
}

#---------------------------- findIsolatedStripes() --------------------------#
sub findIsolatedStripes {
  my($gotMatch) = 0;

  for my $val ( 1..9 ) {
    for my $squIdx ( 0..8 ) {
      my($cnt) = $squCnt[$squIdx][$val];

      next if ( ! $cnt || ($cnt > 3) );

      $gotMatch += findStripeInSquare($squIdx, $val);
    }
  }

  return($gotMatch);
}

#---------------------------- walkCell() -------------------------------------#
sub walkCell {
  my($row, $col, $val) = @_;

  if ( $row == 9 ) {
    my $theTime = time() - $^T;
    printf("TIME: %d:%d \n", int($theTime/60), $theTime%60);
    showBoard("SOLVED");
    exit;
  }

  if ( $board[$row][$col] ) {
    walkCell(nextCell($row, $col));
  }
  else {
    for $val ( 1..9 ) {
      if ( ! existsInRow($row, $val) && ! existsInCol($col, $val) && ! existsInSqu($row, $col, $val) ) {
           setCell($row, $col, $val);

           walkCell(nextCell($row, $col));

           unsetCell($row, $col, $val);
      }
    }
  }
}

#---------------------------- showBoard() ------------------------------------#
sub showBoard {
  my($title) = @_;

  printf("------------------------ BOARD $title -------------------------\n");

  for my $row ( 0..8 ) {
    printf("------+-------+------\n") if ( $row && ! ($row % 3) );
    printf("%s %s %s | %s %s %s | %s %s %s\n", @{$board[$row]});
  }
}

###############################################################################
initBoard();

my($gotMatch);

do {
  $gotMatch = 0;

  #----- FIND SINGLES QITHIN SUQARES ! ---------------------------------------#
  while ( my $cnt = findSingles() ) { $gotMatch += $cnt }

  #----- FIND CORRESPONDING DOUBLE PAIRES IN DIFFERENT SQUARES ! -------------#
  while ( my $cnt = findDoublePairs() ) { $gotMatch += $cnt }

  #----- FIND ROWS OF 2 OR 3 WITHIN A SQUARE AS THE ONLY HOLES ! -------------#
  while ( my $cnt = findIsolatedStripes() ) { $gotMatch += $cnt }

} while ( $gotMatch );

walkCell(0, 0);

exit;

#__EOF__

ishka

• sudoku-ishka.tar.gz: Ishkas Lösung im Quellcode

#!/usr/bin/perl

use strict;
use warnings;

my $kompakt=1; # Auf 0 setzen für eine schönere Ausgabe
my $ratsel=[split //,$ARGV[0]];
unless(81==@$ratsel)
  {
  die "Dies ist kein gültiges Sudoku-Rätsel (nicht 81 Zeichen lang)\n";
  }
for(@$ratsel)
 {
  if(!m#\A[0-9\.]\z#)
  {
  die "Dies ist kein gültiges Sudoku-Rätsel, da es das Zeichen $_ enthält.\n";
  }
 }

for(@$ratsel)
  {
  if('.' eq $_)
    {
    my %h=();
    for(1..9){$h{$_}=1}
    $_=\%h;
    }
  else
    {
    $_={$_=>1};
    }
  }

$ratsel=vollende($ratsel);

if(not defined $ratsel)
  {
  print "Diese Sudoku-Konfiguration ist nicht lösbar.\n";
  exit;
  }

for(0..80)
{
print $ratsel->[$_];
unless(($_+1) % 9)
  {
  print "\n";
  print "\n" unless $kompakt || ($_+1) % 27 || $_ > 79;
  next;
  }
print " " unless $kompakt || ($_+1) % 3;
}

sub vollende
{
my $ratsel=$_[0];
my $gefunden=1;
while($gefunden)
  {
  $gefunden=0;
  my $finde=0;
  while($finde<81)
    {
    if(ref($ratsel->[$finde]) && (1==((keys %{$ratsel->[$finde]}) || return undef)))
      # return undef, falls es für ein Feld keine Möglichkeit mehr
      # gibt, irgendetwas einzutragen.
      {
      $gefunden=1;
      last;
      }
    $finde++;
    }
  if($gefunden)
    {
    my $was=$ratsel->[$finde]=(keys %{$ratsel->[$finde]})[0];
    my $spalte=$finde % 9;
    my $zeile=$finde - $spalte;
    my $kasten=$finde - ($finde % 27) + ($finde % 9) - ($finde % 3);
    for(map {($zeile+$_,$spalte+9*$_,$kasten+($_ % 3)+int($_/3)*9)} 0..8)
      {
      delete ${$ratsel->[$_]}{$was} if ref $ratsel->[$_];
      }
    }
  }
my $weiter=0;
while($weiter < 81 && !ref $ratsel->[$weiter])
 {
 $weiter++;
 }
return $ratsel if 81 == $weiter;
my @was=keys %{$ratsel->[$weiter]};
for my $rate(@was)
 {
 my $teilratsel=[map {ref $_ ? {%$_} : $_} @$ratsel];
 $teilratsel->[$weiter]={$rate=>1};
 my $test=vollende($teilratsel);
 return $test if defined $test;
 }
return undef;
}

murphy

• ssv-1.1.2.tar.gz: Murphys komplette Lösung mit Buildsystem

ThomasChust - 04 Apr 2007 - Optimierte Lösung

• http://www.chust.org/projects/ssv-1.3.2.tar.gz

/*
 * @file   ssv.c
 * @author Thomas "Murphy" Chust <chust@web.de>
 *
 * Sudoku solver.
 */

#include <private.h>
#include <ssv.h>

#ifdef HAS_BUILTIN_FFS
#define ssv_cell_state_scan(state) \
  (__builtin_ffs((state)) - 1)
#else /* HAS_BUILTIN_FFS */
static inline G_GNUC_CONST gint ssv_cell_state_scan(
  register SSVCellState state
) {
  gint i;

  for (i = 0; i < 9; i++) {
    if (state & 1)
      return i;
    else
      state >>= 1;
  }

  return -1;
}
#endif /* HAS_BUILTIN_FFS */

#ifdef HAS_BUILTIN_POPCOUNT
#define ssv_cell_state_count(state) \
  (__builtin_popcount((state)))
#else /* HAS_BUILTIN_POPCOUNT */
static inline G_GNUC_CONST gint ssv_cell_state_count(
  register SSVCellState state
) {
  register gint c = 0;
  gint i;

  for (i = 0; i < 9; i++) {
    c += state & 1;
    state >>= 1;
  }

  return c;
}
#endif /* HAS_BUILTIN_POPCOUNT */

gboolean ssv_board_init(
  register SSVBoard *board, register const gchar *str
) {
  gint i, j;

  g_assert(board);
  g_assert(str);

  for (i = 0; i < 9; i++) {
    for (j = 0; j < 9; j++) {
      gchar c;

    RETRY:
      switch (c = *str++) {
      case 0:
        return FALSE;

      case '0':
      case '#':
        board->cells[i][j] = SSV_CELL_STATE_NONE;
        break;

      case '.':
      case '*':
      case '?':
        board->cells[i][j] = SSV_CELL_STATE_ANY;
        break;

      default:
        if (g_ascii_isdigit(c))
          board->cells[i][j] = SSV_CELL_STATE(c - '1');
        else
          goto RETRY;
        break;
      }
    }
  }

  return TRUE;
}

void ssv_board_print(
  register SSVBoard *board, gboolean pretty, gboolean verbose
) {
  gint i, j;

  g_assert(board);

  for (i = 0; i < 9; i++) {
    for (j = 0; j < 9; j++) {
      SSVCellState state = board->cells[i][j];
      
      if (verbose) {
        gint k;

        g_print("(");
        for (k = 0; k < 9; k++) {
          if (state & SSV_CELL_STATE(k))
            g_print("%c", '1' + k);
        }
        g_print(")");
      }
      else {
        switch (ssv_cell_state_count(state)) {
        case 0:
          g_print("#");
          break;

        case 1:
          g_print("%c", '1' + ssv_cell_state_scan(state));
          break;

        default:
          g_print(".");
          break;
        }
      }

      if (pretty) {
        if (j == 8) {
          g_print("\n");
          if (!verbose && i > 0 && i < 8 && (i + 1) % 3 == 0)
            g_print("---+---+---\n");
        }
        else if (j > 0 && (j + 1) % 3 == 0) {
          if (verbose)
            g_print(", ");
          else
            g_print("|");
        }
      }
    }
  }

  if (!pretty)
    g_print("\n");
}

static inline gint ssv_board_row_count(
  register SSVBoard *board, gint i, register SSVCellState state
) {
  register gint c = 0;
  gint j;

  for (j = 0; j < 9; j++) {
    if (board->cells[i][j] == state)
      c++;
  }

  return c;
}

static inline gint ssv_board_col_count(
  register SSVBoard *board, gint j, register SSVCellState state
) {
  register gint c = 0;
  gint i;

  for (i = 0; i < 9; i++) {
    if (board->cells[i][j] == state)
      c++;
  }

  return c;
}

static inline gint ssv_board_block_count(
  register SSVBoard *board, gint i, gint j, register SSVCellState state
) {
  register gint c = 0;
  gint k, l, m, n;

  m = i - (i % 3);
  n = j - (j % 3);
  for (k = m; k < m + 3; k++) {
    for (l = n; l < n + 3; l++) {
      if (board->cells[k][l] == state)
        c++;
    }
  }

  return c;
}

static inline gboolean ssv_board_row_clear(
  register SSVBoard *board, gint i, register SSVCellState state
) {
  register gboolean changed = FALSE;
  gint j;

  for (j = 0; j < 9; j++) {
    if (board->cells[i][j] != state && board->cells[i][j] & state) {
      board->cells[i][j] &= ~state;
      changed = TRUE;
    }
  }

  return changed;
}

static inline gboolean ssv_board_col_clear(
  register SSVBoard *board, gint j, register SSVCellState state
) {
  register gboolean changed = FALSE;
  gint i;

  for (i = 0; i < 9; i++) {
    if (board->cells[i][j] != state && board->cells[i][j] & state) {
      board->cells[i][j] &= ~state;
      changed = TRUE;
    }
  }

  return changed;
}

static inline gboolean ssv_board_block_clear(
  register SSVBoard *board, gint i, gint j, register SSVCellState state
) {
  register gboolean changed = FALSE;
  gint k, l, m, n;

  m = i - (i % 3);
  n = j - (j % 3);
  for (k = m; k < m + 3; k++) {
    for (l = n; l < n + 3; l++) {
      if (board->cells[k][l] != state && board->cells[k][l] & state) {
        board->cells[k][l] &= ~state;
        changed = TRUE;
      }
    }
  }

  return changed;
}

gboolean ssv_board_solve(
  register SSVBoard *board
) {
  register gboolean changed;
  gint i, j;

RETRY:
  do {
    changed = FALSE;

    for (i = 0; i < 9; i++) {
      for (j = 0; j < 9; j++) {
        SSVCellState state = board->cells[i][j];
        gint n = ssv_cell_state_count(state);
        gint d;

        switch (n) {
        case 0:
          return FALSE;

        case 9:
          continue;
        }
   
        if ((d = ssv_board_row_count(board, i, state) - n) == 0)
          changed |= ssv_board_row_clear(board, i, state);
        else if (d > 0)
          goto FAILURE;

        if ((d = ssv_board_col_count(board, j, state) - n) == 0)
          changed |= ssv_board_col_clear(board, j, state);
        else if (d > 0)
          goto FAILURE;

        if ((d = ssv_board_block_count(board, i, j, state) - n) == 0)
          changed |= ssv_board_block_clear(board, i, j, state);
        else if (d > 0)
          goto FAILURE;

        continue;

      FAILURE:
        board->cells[i][j] = SSV_CELL_STATE_NONE;
        return FALSE;
      }
    }
  } while (G_LIKELY(changed));

  changed = FALSE;

  for (i = 0; i < 9; i++) {
    for (j = 0; j < 9; j++) {
      SSVCellState state = board->cells[i][j];

      if (ssv_cell_state_count(state) > 1) {
        gint k;

        for (k = 0; k < 9; k++) {
          if (state & SSV_CELL_STATE(k)) {
            SSVBoard try_board;

            memcpy(&try_board, board, sizeof(SSVBoard));
            try_board.cells[i][j] = SSV_CELL_STATE(k);

            if (ssv_board_solve(&try_board)) {
              memcpy(board, &try_board, sizeof(SSVBoard));
              changed = TRUE;
              goto OK;
            }
          }
        }

        board->cells[i][j] = SSV_CELL_STATE_NONE;
        return FALSE;

      OK:
        continue;
      }
    }
  }

  if (G_LIKELY(changed))
    goto RETRY;
  
  return TRUE;
}

taulmarill

• sudoku-taulmarill.tar.gz: Taulmarills Lösung im Quelltext

my $fieldstring = $ARGV[0];
if ( ! $fieldstring or $fieldstring !~ /^[\d.]{81}$/ ) {
    die 'Fehlerhaftes Feld!';
}

my @block = (
    [ 1, 2 ], [ 0, 2 ], [ 0, 1 ],
    [ 4, 5 ], [ 3, 5 ], [ 3, 4 ],
    [ 7, 8 ], [ 6, 8 ], [ 6, 7 ],
);
my @fieldr = map{ [ split //, $_ ] } $fieldstring =~ /(.{9})/g;
my @fieldc = map{ my $x = $_; [ map{ $fieldr[$_]->[$x] } 0 .. 8 ] } 0 .. 8;
my ( @empty, $blacklist );
while ( grep{ grep{ $_ eq '.' } @$_ } @fieldr ) {
    my( $x, $y, $f ) = ( 0, 0, 0 );
    for my $xa ( 0 .. 8 ) {
        for my $ya ( 0 .. 8 ) {
            next unless $fieldr[$ya]->[$xa] eq '.';
            my $fa = grep{ $_ ne '.' }
                @{ $fieldr[$ya] },
                @{ $fieldc[$xa] },
                @{ $fieldr[$block[$ya]->[0]] }[@{ $block[$xa] }],
                @{ $fieldr[$block[$ya]->[1]] }[@{ $block[$xa] }];
            ( $x, $y, $f ) = ( $xa, $ya, $fa ) if $fa > $f;
        }
    }
    push @empty, [ $x, $y ];
    $fieldc[$x]->[$y] = $fieldr[$y]->[$x] = 0;
}
brute_force( @empty );

sub brute_force {
    unless ( @_ ) { print_solved(); exit; }
    my( $x, $y ) = @{ shift() };
    $blacklist = join( "",
        @{ $fieldr[$y] },
        @{ $fieldc[$x] },
        @{ $fieldr[$block[$y]->[0]] }[@{ $block[$x] }],
        @{ $fieldr[$block[$y]->[1]] }[@{ $block[$x] }],
    );
    for ( '123456789' =~ m/([^$blacklist])/g ) {
        $fieldc[$x]->[$y] = $fieldr[$y]->[$x] = $_;
        brute_force( @_ );
    }
    $fieldc[$x]->[$y] = $fieldr[$y]->[$x] = 0;
}

sub print_solved {
    print join( " ", @$_ ) . "\n" for @fieldr;
    print "\n";
}

Ergänzungen, Kommentare

---### Main.??? - 14 Jul 2003 - Betreff