Zaimplementuj Brute Force Sudoku Solver

20

Zaimplementuj najkrótszy solver Sudoku za pomocą zgadywania. Ponieważ otrzymałem kilka próśb, dodałem to jako alternatywne pytanie dla osób pragnących wdrożyć solute sudoku z brutalną siłą.

Sudoku Puzzle:

 | 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

Odpowiedź:

 | 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

Zasady:

  1. Załóżmy, że wszystkie labirynty można rozwiązać tylko za pomocą logiki.
  2. Wszystkie dane wejściowe będą miały 81 znaków. Brakujące znaki będą wynosić 0.
  3. Wyjście rozwiązania jako pojedynczy ciąg.
  4. „Siatka” może być przechowywana wewnętrznie, jak chcesz.
  5. Rozwiązanie musi zawierać rozwiązanie zgadywania brutalnej siły.
  6. Rozwiązania powinny zostać rozwiązane w rozsądnym terminie.

Przykład I / O:

>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137
snmcdonald
źródło
Jak dane wejściowe mogą mieć długość 27 znaków? Musi mieć 81 znaków - 9 wierszy x 9 kolumn. Tak też robi twój przykład. Zakładam również, że „brakujące znaki będą wynosić 0” oznacza, że ​​jeśli liczba znaków jest mniejsza niż 81, to zera kończą się na końcu?
Jonathan M Davis
Zaczekaj. Dostaję brakujące znaki będą 0 bitów. Duh. Tych trzeba zgadnąć. W każdym razie liczba znaków musi wynosić 81, a nie 27.
Jonathan M Davis
8
wygląda na to, że reguły 5 i 6 są trochę konfliktowe ...
pseudonim117

Odpowiedzi:

11

k (72 bajty)

Podziękowania należą się Arthurowi Whitneyowi, twórcy języka K.

p,:3/:_(p:9\:!81)%3
s:{*(,x)(,/{@[x;y;:;]'&21=x[&|/p[;y]=p]?!10}')/&~x}
skeevey
źródło
klasyczny! Też zamierzałem to opublikować!
nightTrevors
9

Python, 188 bajtów

To jest kolejna skrócona wersja mojego zwycięskiego zgłoszenia do CodeSprint Sudoku , zmodyfikowanego do wprowadzania z wiersza poleceń zamiast standardowego wejścia (zgodnie z 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])

Jeśli używasz języka Python 2, '%d'%5**18możesz go zastąpić, `5**18`aby zaoszczędzić 3 bajty.

Aby przyspieszyć działanie, możesz zastąpić '%d'%5**18dowolną permutacją '123456789'za cenę 1 bajtu.

Jeśli chcesz, aby zaakceptować wejście na stdin zamiast można zastąpić import sys;f(sys.argv[1])z f(raw_input()), obniżając ją do 177 bajtów .

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())

EDYCJA: Oto link do bardziej szczegółowego przewodnika.

Cyphase
źródło
Bardzo fajne rozwiązanie.
primo,
8

Python, 197 znaków

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
źródło
6

Odpowiedź w 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;
}

Z przykładowym wejściem pobiera .033s na moim Phenom II X6 1090T po kompilacji dmd -w(tj. Bez optymalizacji), i zajmuje .011s po kompilacji dmd -w -O -inline -release(tj. Z optymalizacjami).

Jonathan M. Davis
źródło
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

przewidywany czas pracy: O (miliard miliardów lat)

Eelvex
źródło
1
I dlaczego oczekiwany czas pracy to „O (miliard miliardów lat)”? (czy nie powinno to być po prostu „miliardem miliardów lat” bez O?
Justin
1
Kiedy zobaczyłem to pytanie, od razu wiedziałem, że J to zmiażdży. Musi istnieć sposób, aby był krótszy niż K.
koko
1
@Quincunx, ściśle mówiąc, jest to niewłaściwe użycie big-O; „żart” miał odczytywać „stały czas działania, asymptotycznie miliard lat”.
Eelvex
@ koko, nie mogłem znaleźć czegoś lepszego, ale wciąż nad tym pracuję.
Eelvex
4

Perl, 120 bajtów

Och, pamiętam grę w golfa w 2008 roku ... I tak naprawdę przestał działać w perlu 5.12, ponieważ usunięto wtedy ukryte ustawienie @_ przez podział. Więc wypróbuj to tylko na wystarczająco starym perlu.

Uruchom z wejściem na 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
źródło
2
To trzecie prawo Clarke'a , ale na odwrót!
Conor O'Brien
3

Perl, 235 znaków

$_=$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/

To jest wersja gry w golfa, którą zamieściłem wiele lat temu na liście dyskusyjnej Fun With Perl : regexp rozwiązujący sudoku.

Zasadniczo porządkuje dane wejściowe w 81 liniach, z których każda zawiera wszystkie liczby, które mogą wystąpić w odpowiednim kwadracie. Następnie konstruuje wyrażenie regularne w celu dopasowania jednej liczby z każdej linii, wykorzystując odwołania wsteczne i negatywne twierdzenia dotyczące przyszłości, aby odrzucić rozwiązania naruszające ograniczenia wiersza, kolumny lub regionu. Następnie dopasowuje ciąg do wyrażenia regularnego, pozwalając silnikowi wyrażeń regularnych Perla wykonać ciężką pracę próbną i cofanie się.

O dziwo, możliwe jest utworzenie jednego wyrażenia regularnego, który będzie działał dla dowolnego wejścia, tak jak robi to mój oryginalny program. Niestety jest dość powolny, więc oparłem tutaj kod do gry w golfa na wersji hardcoded-givens ( znalezionej później w wątku FWP ), która poprawia wyrażenie regularne, aby odrzucić wcześniej wszelkie rozwiązania, o których wie, że później naruszą ograniczenie. To sprawia, że ​​jest dość szybki dla łatwych do umiarkowanych poziomów sudokus, chociaż szczególnie trudne mogą jeszcze zająć dość dużo czasu.

Uruchom kod za pomocą, perl -M5.010aby włączyć funkcję Perl 5.10+ say. Dane wejściowe należy podać na standardowym wejściu, a rozwiązanie zostanie wydrukowane na standardowym wyjściu; przykład:

$ perl -M5.010 golf/sudoku.pl
030001000006000050500000983080006302000050000903800060714000009020000800000400030
832591674496387251571264983185746392267953418943812765714638529329175846658429137
Ilmari Karonen
źródło
2

1-liniowy skrypt do kawy

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

Oto większa wersja z przykładowym użyciem :

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
źródło
1
Można go skrócić, skracając solve, usuwając wiele białych znaków (wiem, że jest to znaczące, ale w wielu miejscach można go usunąć), używając symboli zamiast słów (jak !=zamiast isnt), używając wcięcia zamiast thensłowa kluczowego, zastępując [0...9]je [0..8].
Konrad Borowski
1

Clojure - 480 bajtów

Rozmiar eksplodował, ale przynajmniej to ładna liczba. Myślę, że można by to znacznie poprawić, używając tylko wektora 1D. W każdym razie przypadek testowy na moim laptopie zajmuje niecałe cztery sekundy. Pomyślałem, że dobrze byłoby zdefiniować funkcję, ponieważ jest to w końcu język funkcjonalny.

(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)))

Przykłady:

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

Nieco golfowa (i ładniejsza) wersja:

(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)))
patrz
źródło
1

PowerShell , 244 242 218 215 bajtów

$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}}

Wypróbuj online!

Skrypt znajduje wszystkie rozwiązania dla sudoku.

Rozwinięty:

$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
    }

}

Przypadki testowe:

@(
    # 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
źródło
0

D (322 znaki)

Dla każdego nierozwiązanego kwadratu buduje tablicę dostępnych opcji, a następnie zapętla nad nim.

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;}

z białymi znakami:

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
źródło
0

Perl (195 znaków)

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

Całe uznanie należy do twórcy tutaj , a wyjaśnienie można również tam znaleźć.

Qwix
źródło
1
Jeśli nie napisałeś tego sam, powinieneś sprawdzić przycisk „Społeczność Wiki”.
Kyle Kanos
Po kilku badaniach, co to jest, nie wydaje mi się to możliwe. Najwyraźniej potrzebuję 100 powtórzeń, aby zobaczyć pole wyboru (patrz sekcja uzupełnienia pod nr 2 tego postu )
Qwix
Hmm, nie wiedziałem o tym wymaganiu.
Kyle Kanos,
0

J, 94 bajty

Działa dokładnie tak samo, jak wersja K, a mianowicie z BFS (więc wyświetli wszystkie rozwiązania). Drukuje spacje między cyframi wyjściowymi, ale robi to również program K. Nie liczę „s =:”, ponieważ jest to po prostu nazwa funkcji (tak jak nie liczyłbym nazwy pliku w innym języku).

   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
źródło