Mettre en œuvre un solveur Brute Force Sudoku

20

Implémentez le solveur Sudoku le plus court en utilisant la devinette. Depuis que j'ai reçu quelques demandes, j'ai ajouté ceci comme une question alternative pour ceux qui souhaitent implémenter un solveur de sudoku par force brute.

Puzzle Sudoku:

 | 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A|   3   |     1 |
B|     6 |       |   5
C| 5     |       | 9 8 3
-+-----------------------
D|   8   |     6 | 3   2
E|       |   5   |
F| 9   3 | 8     |   6
-+-----------------------
G| 7 1 4 |       |     9
H|   2   |       | 8
I|       | 4     |   3

Répondre:

 | 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A| 8 3 2 | 5 9 1 | 6 7 4
B| 4 9 6 | 3 8 7 | 2 5 1
C| 5 7 1 | 2 6 4 | 9 8 3
-+-----------------------
D| 1 8 5 | 7 4 6 | 3 9 2
E| 2 6 7 | 9 5 3 | 4 1 8
F| 9 4 3 | 8 1 2 | 7 6 5
-+-----------------------
G| 7 1 4 | 6 3 8 | 5 2 9
H| 3 2 9 | 1 7 5 | 8 4 6
I| 6 5 8 | 4 2 9 | 1 3 7

Règles:

  1. Supposons que tous les labyrinthes ne peuvent être résolus que par logique.
  2. Toutes les entrées comporteront 81 caractères. Les caractères manquants seront 0.
  3. Générez la solution sous forme de chaîne unique.
  4. La "grille" peut être stockée en interne comme vous le souhaitez.
  5. La solution doit utiliser une solution de devinette par force brute.
  6. Les solutions doivent être résolues dans un délai raisonnable.

Exemple d'E / S:

>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137
snmcdonald
la source
Comment l'entrée peut-elle contenir 27 caractères? Il doit comporter 81 caractères - 9 lignes x 9 colonnes. C'est aussi ce que fait votre exemple. De plus, je suppose que "les caractères manquants seront 0" signifie que si le nombre de caractères est inférieur à 81, alors les zéros vont à la fin?
Jonathan M Davis
Oh, attendez. Je reçois les caractères manquants seront 0 bit. Duh. Ce sont ceux-là qu'il faut deviner. Dans tous les cas, le nombre de caractères doit être de 81, pas de 27.
Jonathan M Davis
8
il semble que les règles 5 et 6 soient un peu en conflit ....
pseudonym117

Réponses:

11

k (72 octets)

Le mérite en revient à Arthur Whitney, créateur de la langue k.

p,:3/:_(p:9\:!81)%3
s:{*(,x)(,/{@[x;y;:;]'&21=x[&|/p[;y]=p]?!10}')/&~x}
skeevey
la source
classique! J'allais poster ça aussi!
nightTrevors
9

Python, 188 octets

Il s'agit d'une autre version raccourcie de ma soumission gagnante pour CodeSprint Sudoku , modifiée pour l'entrée en ligne de commande au lieu de stdin (selon l'OP):

def f(s):
 x=s.find('0')
 if x<0:print s;exit()
 [c in[(x-y)%9*(x/9^y/9)*(x/27^y/27|x%9/3^y%9/3)or s[y]for y in range(81)]or f(s[:x]+c+s[x+1:])for c in'%d'%5**18]
import sys
f(sys.argv[1])

Si vous utilisez Python 2, '%d'%5**18peut être remplacé par `5**18`pour économiser 3 octets.

Pour le faire fonctionner plus rapidement, vous pouvez le remplacer '%d'%5**18par n'importe quelle permutation de '123456789'au coût de 1 octet.

Si vous souhaitez qu'il accepte l'entrée sur stdin à la place, vous pouvez le remplacer import sys;f(sys.argv[1])par f(raw_input()), le ramenant à 177 octets .

def f(s):
 x=s.find('0')
 if x<0:print s;exit()
 [c in[(x-y)%9*(x/9^y/9)*(x/27^y/27|x%9/3^y%9/3)or s[y]for y in range(81)]or f(s[:x]+c+s[x+1:])for c in'%d'%5**18]
f(raw_input())

EDIT: voici un lien vers une procédure pas à pas plus détaillée.

Cyphase
la source
Très belle solution.
primo
8

Python, 197 caractères

def S(s):
 i=s.find('0')
 if i<0:print s;return
 for v in'123456789':
  if sum(v==s[j]and(i/9==j/9or i%9==j%9or(i%9/3==j%9/3and i/27==j/27))for j in range(81))==0:S(s[:i]+v+s[i+1:])
S(raw_input())
Keith Randall
la source
6

Réponse en D:

import std.algorithm;
import std.conv;
import std.ascii;
import std.exception;
import std.stdio;

void main(string[] args)
{
    enforce(args.length == 2, new Exception("Missing argument."));
    enforce(args[1].length == 81, new Exception("Invalid argument."));
    enforce(!canFind!((a){return !isDigit(to!dchar(a));})
                     (args[1]),
                      new Exception("Entire argument must be digits."));

    auto sudoku = new Sudoku(args[1]);
    sudoku.fillIn();

    writeln(sudoku);
}

class Sudoku
{
public:

    this(string str) nothrow
    {
        normal = new int[][](9, 9);

        for(size_t i = 0, k =0; i < 9; ++i)
        {
            for(size_t j = 0; j < 9; ++j)
                normal[i][j] = to!int(str[k++]) - '0';
        }

        reversed = new int*[][](9, 9);

        for(size_t i = 0; i < 9; ++i)
        {
            for(size_t j = 0; j < 9; ++j)
                reversed[j][i] = &normal[i][j];
        }

        boxes = new int*[][](9, 9);
        indexedBoxes = new int*[][][](9, 9);

        for(size_t boxRow = 0, boxNum = 0; boxRow < 3; ++boxRow)
        {
            for(size_t boxCol = 0; boxCol < 3; ++boxCol, ++boxNum)
            {
                for(size_t i = 3 * boxRow, square = 0; i < 3 * (boxRow + 1); ++i)
                {
                    for(size_t j = 3 * boxCol; j < 3 * (boxCol + 1); ++j)
                    {
                        boxes[boxNum][square++] = &normal[i][j];
                        indexedBoxes[i][j] = boxes[boxNum];
                    }
                }
            }
        }
    }

    void fillIn()
    {
        fillIn(0, 0);
    }

    @property bool valid()
    {
        assert(full);

        for(size_t i = 0; i < 9; ++i)
        {
            for(int n = 1; n < 10; ++n)
            {
                if(!canFind(normal[i], n) ||
                   !canFind!"*a == b"(reversed[i], n) ||
                   !canFind!"*a == b"(boxes[i], n))
                {
                    return false;
                }
            }
        }

        return true;
    }

    override string toString() const
    {
        char[81] retval;

        for(size_t i = 0, k =0; i < 9; ++i)
        {
            for(size_t j = 0; j < 9; ++j)
                retval[k++] = to!char(normal[i][j] + '0');
        }

        return to!string(retval);
    }

private:

    @property bool full()
    {
        for(size_t i = 0; i < 9; ++i)
        {
            if(canFind(normal[i], 0))
                return false;
        }

        return true;
    }

    bool fillIn(size_t row, size_t col)
    {
        if(row == 9)
            return valid;

        size_t nextRow = row;
        size_t nextCol = col + 1;

        if(nextCol == 9)
        {
            nextRow = row + 1;
            nextCol = 0;
        }

        if(normal[row][col] == 0)
        {
            for(int n = 1; n < 10; ++n)
            {
                if(canFind(normal[row], n) ||
                   canFind!"*a == b"(reversed[col], n) ||
                   canFind!"*a == b"(indexedBoxes[row][col], n))
                {
                    continue;
                }

                normal[row][col] = n;

                if(fillIn(nextRow, nextCol))
                    return true;
            }

            normal[row][col] = 0;

            return false;
        }
        else
            return fillIn(nextRow, nextCol);
    }

    int[][] normal;
    int*[][] reversed;
    int*[][] boxes;
    int*[][][] indexedBoxes;
}

Avec l'exemple d'entrée, cela prend .033s sur mon Phenom II X6 1090T lorsqu'il est compilé avec dmd -w(c'est-à-dire sans optimisations), et il prend .011s lorsqu'il est compilé avec dmd -w -O -inline -release(c'est-à-dire avec optimisations).

Jonathan M Davis
la source
4

J, 103

'p n'=:(;#)I.0=a=:("."0)Y
((a p}~3 :'>:?n#9')^:([:(27~:[:+/[:(9=#@~.)"1[:,/(2 2$3),;.3],|:,])9 9$])^:_)a

durée d'exécution prévue: O (milliards de milliards d'années)

Eelvex
la source
1
Et pourquoi le temps d'exécution prévu est-il "O (milliards de milliards d'années)"? (cela ne devrait-il pas être juste "des milliards de milliards d'années" sans le O?
Justin
1
Quand j'ai vu cette question, j'ai immédiatement su que J allait écraser celle-ci. Il doit y avoir un moyen de rendre cela plus court que K.
koko
1
@Quincunx, à proprement parler, c'est une mauvaise utilisation de big-O; la "plaisanterie" était censée se lire "temps d'exécution constant, asymptotiquement des milliards de milliards d'années".
Eelvex
@koko, je n'ai pas pu trouver mieux, mais j'y travaille toujours.
Eelvex
4

Perl, 120 octets

Oh, je me souviens avoir joué au golf en 2008 ... Et en fait, cela a cessé de fonctionner en Perl 5.12 car le paramètre implicite de @_ by split a été supprimé. Essayez donc ceci uniquement sur un perl suffisamment ancien.

Exécutez avec l'entrée sur STDIN:

sudoku.pl <<< "030001000006000050500000983080006302000050000903800060714000009020000800000400030"

sudoku.pl:

${/[@_[map{$i-($i="@-")%9+$_,9*$_+$i%9,9*$_%26+$i-$i%3+$i%9-$i%27}0..8%split""]]/o||do$0}for$_=$`.$_.$'.<>,/0/||print..9
Ton Hospel
la source
2
C'est la troisième loi de Clarke , mais à l'envers!
Conor O'Brien
3

Perl, 235 caractères

$_=$s=<>;$r=join$/,map{$n=$_;'.*(?!'.(join'|',map+($_%9==$n%9||int($_/9)==int($n/9)||int($_/27)==int($n/27)&&int($_/3%3)==int($n/3%3)and$_<$n?'\\'.($_+1):$_>$n&&substr$s,$_,1)||X,@a).')(.).*'}@a=0..80;s!.!($&||123456789).$/!eg;say/^$r/

Il s'agit d'une version golfée de quelque chose que j'ai publié il y a de nombreuses années sur la liste de diffusion Fun With Perl : une expression rationnelle de résolution de sudoku.

Fondamentalement, il modifie l'entrée en 81 lignes, chacune contenant tous les nombres qui pourraient apparaître dans le carré correspondant. Il construit ensuite une expression rationnelle pour correspondre à un nombre de chaque ligne, en utilisant des références arrières et des assertions d'anticipation négatives pour rejeter les solutions qui violent les contraintes de ligne, de colonne ou de région. Ensuite, il fait correspondre la chaîne avec l'expression rationnelle, laissant le moteur d'expression rationnelle de Perl faire le travail difficile d'essai et de retour en arrière.

Étonnamment, il est possible de créer une seule expression rationnelle qui fonctionne pour n'importe quelle entrée, comme le fait mon programme d'origine. Malheureusement, c'est assez lent, j'ai donc basé le code de golf ici sur la version hardcoded-givens ( trouvée plus loin dans le thread FWP ), qui peaufine l'expression rationnelle pour rejeter tôt toutes les solutions dont il sait qu'elles violeront plus tard une contrainte. Cela le rend raisonnablement rapide pour les sudokus de niveau facile à modéré, bien que ceux particulièrement difficiles puissent encore prendre un temps assez long à résoudre.

Exécutez le code avec perl -M5.010pour activer la fonction Perl 5.10+ say. L'entrée doit être donnée sur l'entrée standard, et la solution sera imprimée sur la sortie standard; exemple:

$ perl -M5.010 golf/sudoku.pl
030001000006000050500000983080006302000050000903800060714000009020000800000400030
832591674496387251571264983185746392267953418943812765714638529329175846658429137
Ilmari Karonen
la source
2

Café-script 1 ligne

solve = (s, c = 0) -> if c is 81 then s else if s[x = c/9|0][y = c%9] isnt 0 then solve s, c+1 else (([1..9].filter (g) -> ![0...9].some (i) -> g in [s[x][i], s[i][y], s[3*(x/3|0) + i/3|0][3*(y/3|0) + i%3]]).some (g) -> s[x][y] = g; solve s, c+1) or s[x][y] = 0

Voici la version plus grande avec un exemple d'utilisation :

solve = (sudoku, cell = 0) ->
  if cell is 9*9 then return sudoku

  x = cell%9
  y = (cell - x)/9

  if sudoku[x][y] isnt 0 then return solve sudoku, cell+1

  row = (i) -> sudoku[x][i]
  col = (i) -> sudoku[i][y]
  box = (i) -> sudoku[x - x%3 + (i - i%3)/3][y - y%3 + i%3]

  good = (guess) -> [0...9].every (i) -> guess not in [row(i), col(i), box(i)]

  guesses = [1..9].filter good

  solves = (guess) -> sudoku[x][y] = guess; solve sudoku, cell+1

  (guesses.some solves) or sudoku[x][y] = 0

sudoku = [
  [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]
]
console.log if solve sudoku then sudoku else 'could not solve'
pathikrit
la source
1
Pourrait être raccourci en raccourcissant solve, en supprimant beaucoup d'espace (je sais que c'est important, mais dans de nombreux endroits, il pourrait être supprimé), en utilisant des symboles au lieu de mots (comme !=au lieu de isnt), en utilisant l'indentation au lieu d'un thenmot-clé, en remplaçant [0...9]par [0..8].
Konrad Borowski
1

Clojure - 480 octets

La taille a explosé, mais au moins c'est un joli chiffre. Je pense que cela pourrait être beaucoup amélioré en utilisant uniquement le vecteur 1D. Quoi qu'il en soit, le cas de test prend un peu moins de quatre secondes sur mon ordinateur portable. J'ai pensé qu'il serait approprié de définir une fonction, car c'est un langage fonctionnel après tout.

(defn f[o &[x y]](if x(if(> y 8)(apply str(map #(apply str %)o))(first(for[q[(o y)]v(if(=(q x)0)(range 1 10)[(q x)])d[(assoc o y(assoc(o y)x v))]s[(and(every? true?(concat(for[i(range 9)](and(or(not=((d y)i)v)(= i x))(or(not=((d i)x)v)(= i y))))(for[m[#(+ %2(- %(mod % 3)))]r[(range 3)]a r b r c[(m y b)]e[(m x a)]](or(and(= e x)(= c y))(not=((d y)x)((d c)e))))))(f d(mod(+ x 1)9)(if(= x 8)(+ 1 y)y)))]:when s]s)))(f(vec(for[a(partition 9 o)](vec(map #(Integer.(str %))a))))0 0)))

Exemples:

(f "030001000006000050500000983080006302000050000903800060714000009020000800000400030")
=> "832591674496387251571264983185746392267953418943812765714638529329175846658429137"
(f "004720900039008005001506004040010520028050170016030090400901300100300840007085600")
=> "654723981239148765871596234743819526928654173516237498482961357165372849397485612"

Une version légèrement non golfée (et plus jolie):

(defn check-place [o x y v]
  (and (every? true? (for [i (range 9)]
                       (and (or (not= ((o y) i) v) (= i x))
                            (or (not= ((o i) x) v) (= i y)))))
       (every? true?
         (for [r [(range 3)]
               a r
               b r
               c [(+ b (- y (mod y 3)))]
               d [(+ a (- x (mod x 3)))]]
           (or (and (= d x) (= c y)) (not= ((o y) x) ((o c) d)))))))

(defn solve-sudoku [board & [x y]]
  (if x
    (if (> y 8)
      (apply str (map #(apply str %) board))
      (first
        (for [v (if (= ((board y) x) 0) (range 1 10) [((board y) x)])
              :let [a (mod (+ x 1) 9)
                    b (if (= x 8) (+ 1 y) y)
                    d (assoc board y (assoc (board y) x v))
                    s (and (check-place d x y v) (solve-sudoku d a b))]
              :when s]
          s)))
    (solve-sudoku (vec (for [a (partition 9 board)]
                         (vec (map #(Integer. (str %)) a)))) 0 0)))
seequ
la source
1

PowerShell , 244 242 218 215 octets

$a=(24,24,6)*3|%{,(0..8|%{($r++)});,(0..8|%{$c%81;$c+=9});$c++;,((1,1,7)*3|%{+$q;$q+=$_});$q-=$_}
$f={param($s)$l,$r=$s-split0,2;if($p=$a|?{$l.length-in$_}){1..9|?{"$_"-notin($p|%{$s[$_]})}|%{&$f "$l$_$r"}}else{$s}}

Essayez-le en ligne!

Le script trouve toutes les solutions pour un sudoku.

Déroulé:

$a=(24,24,6)*3|%{                       # array of indexes for a sudoku...
    ,(0..8|%{($r++)})                   # rows
    ,(0..8|%{$c%81;$c+=9});$c++         # columns
    ,((1,1,7)*3|%{+$q;$q+=$_});$q-=$_   # and squares
}

$f = {
    param($s)

    # optional log. remove this statement in a release version.
    if($script:iter++ -lt 100 -or ($script:iter%100)-eq0){
        Write-Information ('{0}: {1,6}: {2}'-f (get-Date), $script:iter, ($s-replace0,' ')) -InformationAction Continue
    }

    $left,$right=$s-split0,2                # split by a first 0; $left.length is a position of this 0 if $s contains the 0
    if( $parts=$a|?{$left.length-in$_} ){   # get sudoku parts (rows, columns, squares) contain the position
        1..9|?{                             # try a digit
            "$_"-notin($parts|%{$s[$_]})    # all digits in these parts will be unique if parts do not contain the digit
        }|%{
            &$f "$left$_$right"             # recursive call with the digit
        } #|select -f 1                     # uncomment this to get a first result only
    }
    else{
        $s
    }

}

Cas de test:

@(
    # 5 iterations, my notebook: 00:00:00, all
    # 5 iterations, my notebook: 00:00:00, first only
    , ( "832591674496387251571264983185746392267953418943812765714638529329175846658400030",
        "832591674496387251571264983185746392267953418943812765714638529329175846658429137" )

    # ~29600 iterations, my notebook: 00:01:27, all
    #  ~2100 iterations, my notebook: 00:00:10, first only
    # , ( "830001000006000050500000983080006302000050000903800060714000009020000800000400030",
    #     "832591674496387251571264983185746392267953418943812765714638529329175846658429137" )

    # ~49900 iterations, my notebook: 00:02:39, all
    # ~22400 iterations, my notebook: 00:01:20, first only
    # , ( "030001000006000050500000983080006302000050000903800060714000009020000800000400030",
    #     "832591674496387251571264983185746392267953418943812765714638529329175846658429137" )

) | % {
    $sudoku, $expected = $_
    $time = Measure-Command {
        $result = &$f $sudoku
    }
    "$($result-contains$expected): $time"
    $result
}
mazzy
la source
0

D (322 caractères)

Pour chaque carré non résolu, il crée un tableau d'options disponibles, puis passe en boucle dessus.

import std.algorithm,std.range,std.stdio;void main(char[][]args){T s(T)(T p){foreach(i,ref c;p)if(c<49){foreach(o;"123456789".setDifference(chain(p[i/9*9..i/9*9+9],p[i%9..$].stride(9),p[i/27*27+i%9/3*3..$][0..21].chunks(3).stride(3).joiner).array.sort)){c=o&63;if(s(p))return p;}c=48;return[];}return p;}s(args[1]).write;}

avec espace:

import std.algorithm, std.range, std.stdio;

void main(char[][] args) {
    T s(T)(T p) {
        foreach (i, ref c; p) if (c < 49) {
            foreach (o; "123456789".setDifference(chain(
                    p[i/9*9..i/9*9+9],
                    p[i%9..$].stride(9),
                    p[i/27*27+i%9/3*3..$][0..21].chunks(3).stride(3).joiner
                ).array.sort))
            {
                c = o&63;
                if (s(p)) return p;
            }
            c=48;
            return [];
        }
        return p;
    }
    s(args[1]).write;
}
mleise
la source
0

Perl (195 caractères)

use integer;@A=split//,<>;sub R{for$i(0..80){next if$A[$i];my%t=map{$_/9==$/9||$_%9==$i%9||$_/27==$i/27&&$_%9/3==$i%9/3?$A[$_]:0=>1}0..80;R($A[$i]=$_)for grep{!$t{$_}}1..9;return$A[$i]=0}die@A}R

Tout le mérite revient au créateur ici , et l'explication peut également être trouvée là-bas.

Qwix
la source
1
Si vous ne l'avez pas écrit vous-même, alors vous devriez cocher le bouton "Community Wiki".
Kyle Kanos
Après quelques recherches sur ce que c'est, cela ne me semble pas possible. Apparemment, 100 répétitions sont nécessaires pour que je puisse voir la case à cocher (voir la section addenda sous # 2 de ce post )
Qwix
Hmm, n'était pas au courant de cette exigence.
Kyle Kanos
0

J, 94 octets

Fonctionne exactement de la même manière que la version K, à savoir avec un BFS (il doit donc afficher toutes les solutions). Il imprime des espaces entre les chiffres de sortie, mais le programme K aussi. Je ne compte pas «s =:» car il s'agit simplement de nommer la fonction (tout comme je ne compterais pas le nom de fichier dans une autre langue).

   s=: [:<@((]i.0:)}"0 _~(>:i.9)-.{&((+./ .=|:)3(],.[,@#.<.@%~)9 9#:i.81)@i.&0#])"1^:(0 e.,)@;^:_"."0

   s'030001000006000050500000983080006302000050000903800060714000009020000800000400030'
8 3 2 5 9 1 6 7 4 4 9 6 3 8 7 2 5 1 5 7 1 2 6 4 9 8 3 1 8 5 7 4 6 3 9 2 2 6 7 9 5 3 4 1 8 9 4 3 8 1 2 7 6 5 7 1 4 6 3 8 5 2 9 3 2 9 1 7 5 8 4 6 6 5 8 4 2 9 1 3 7
Olius
la source