Внедрить Солку Судоку Солвер

20

Реализуйте самый короткий решатель судоку, используя догадки. Поскольку я получил несколько запросов, я добавил этот вопрос в качестве альтернативного вопроса для тех, кто желает внедрить решение для грубой силы судоку.

Головоломка Судоку:

 | 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

Ответ:

 | 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

Правила:

  1. Предположим, что все лабиринты разрешимы только логикой.
  2. Весь ввод будет длиной 81 символ. Недостающие символы будут 0.
  3. Выведите решение в виде одной строки.
  4. «Сетка» может храниться внутри, как вы пожелаете.
  5. Решение должно быть с использованием метода угадывания грубой силы.
  6. Решения должны быть решены в разумные сроки.

Пример ввода / вывода:

>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137
snmcdonald
источник
Как длина ввода может быть 27 символов? Это должно быть 81 символов длиной - 9 строк х 9 столбцов. Это то, что делает ваш пример тоже. Также я предполагаю, что «пропущенные символы будут равны 0» означает, что если количество символов меньше 81, то нули заканчиваются?
Джонатан М Дэвис
Ой, подожди. Я получаю, недостающие символы будут 0 бит. Duh. Это те, которые нужно угадать. В любом случае количество символов должно быть 81, а не 27.
Джонатан М. Дэвис
8
кажется, правила 5 и 6 своего рода конфликт ....
псевдоним117

Ответы:

11

к (72 байта)

Кредит на это идет Артуру Уитни, создателю языка K.

p,:3/:_(p:9\:!81)%3
s:{*(,x)(,/{@[x;y;:;]'&21=x[&|/p[;y]=p]?!10}')/&~x}
skeevey
источник
классика! Я собирался опубликовать это тоже!
nightTrevors
9

Python, 188 байт

Это еще одна сокращенная версия моего выигравшего представления для CodeSprint Sudoku , модифицированного для ввода в командной строке вместо стандартного ввода (согласно ОП):

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

Если вы используете Python 2, '%d'%5**18можно заменить на, `5**18`чтобы сохранить 3 байта.

Чтобы он работал быстрее, вы можете заменить его '%d'%5**18любой перестановкой '123456789'со стоимостью 1 байт.

Если вы хотите , чтобы принять ввод на стандартный ввод вместо этого, вы можете заменить import sys;f(sys.argv[1])с f(raw_input()), доведя его до 177 байт .

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

РЕДАКТИРОВАТЬ: Вот ссылка на более подробное руководство.

Cyphase
источник
Очень хорошее решение.
Примо
8

Питон, 197 символов

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())
Кит Рэндалл
источник
6

Ответ в 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;
}

При вводе сэмпла на моем Phenom II X6 1090T требуется 0,03 с при компиляции dmd -w(т.е. без оптимизации), и 0,011 с при компиляции dmd -w -O -inline -release(с оптимизацией).

Джонатан М Дэвис
источник
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

ожидаемое время выполнения: O (млрд миллиардов лет)

Eelvex
источник
1
И почему ожидаемое время выполнения "O (млрд миллиардов лет)"? (разве это не должно быть просто «миллиард миллиардов лет» без О?
Джастин,
1
Когда я увидел этот вопрос, я сразу понял, что J собирается его раздавить. Должен быть способ сделать это короче, чем K.
koko
1
@ Quincunx, строго говоря, это неправильное использование big-O; «Шутка» должна была звучать как «постоянное время выполнения, асимптотически миллиарды миллиардов лет».
Eelvex
@koko, я не мог найти что-то лучшее, но я все еще работаю над этим.
Eelvex
4

Perl, 120 байт

О, я помню игру в гольф еще в 2008 году ... И она фактически перестала работать в Perl 5.12, так как тогда неявная установка @_ через split была удалена. Так что попробуйте только на достаточно старом Perl.

Запустите с помощью ввода на 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
Тон Хоспел
источник
2
Это третий закон Кларка , но наоборот!
Конор О'Брайен
3

Perl, 235 символов

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

Это версия игры в гольф, которую я опубликовал много лет назад в списке рассылки Fun With Perl : регулярное выражение для решения судоку.

По сути, он разбивает входные данные на 81 строку, каждая из которых содержит все числа, которые могут встречаться в соответствующем квадрате. Затем он создает регулярное выражение для соответствия одному числу из каждой строки, используя обратные ссылки и отрицательные косвенные утверждения, чтобы отклонить решения, которые нарушают ограничения строки, столбца или области. Затем он сопоставляет строку с регулярным выражением, позволяя механизму регулярного выражения Perl выполнять тяжелую работу проб и возврата.

Удивительно, но можно создать одно регулярное выражение, которое работает для любого ввода, как моя оригинальная программа. К сожалению, он довольно медленный, поэтому я основал здесь гольф-код на версии hardcoded-givens ( найденной позже в потоке FWP ), которая настраивает регулярное выражение для раннего отклонения любых решений, которые, как ему известно, позже нарушат ограничение. Это делает его достаточно быстрым для легкого и умеренного уровня судоку, хотя особенно тяжелые могут по-прежнему занимать довольно много времени.

Запустите код, perl -M5.010чтобы включить функцию Perl 5.10+ say. Ввод должен быть дан на стандартном вводе, и решение будет напечатано на стандартный вывод; пример:

$ perl -M5.010 golf/sudoku.pl
030001000006000050500000983080006302000050000903800060714000009020000800000400030
832591674496387251571264983185746392267953418943812765714638529329175846658429137
Илмари Каронен
источник
2

1-лайнер кофе-скрипт

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

Вот увеличенная версия с примером использования :

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
источник
1
Можно сократить путем сокращения solve, удалив много пробелов (я знаю, что это важно, но во многих местах его можно удалить), используя символы вместо слов (например, !=вместо isnt), используя отступ вместо thenключевого слова, заменяя [0...9]на [0..8].
Конрад Боровски
1

Clojure - 480 байт

Размер взорвался, но, по крайней мере, это довольно много. Я думаю, что это можно улучшить, используя только 1D-вектор. В любом случае, тестовый пример занимает чуть меньше четырех секунд на моем ноутбуке. Я думал, что было бы уместно определить функцию, так как в конце концов это функциональный язык.

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

Примеры:

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

Слегка разглаженная (и более симпатичная) версия:

(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
источник
1

PowerShell , 244 242 218 215 байт

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

Попробуйте онлайн!

Скрипт находит все решения для судоку.

раскатали:

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

}

Тестовые случаи:

@(
    # 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
источник
0

D (322 символа)

Для каждого нерешенного квадрата он строит массив доступных опций, а затем перебирает его.

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

с пробелами:

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
источник
0

Perl (195 символов)

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

Вся заслуга принадлежит создателю здесь , и объяснение можно найти там же.

Qwix
источник
1
Если вы не написали это сами, то вам нужно нажать кнопку «Сообщество вики».
Кайл Канос
После некоторого исследования, что это такое, для меня это не выглядит возможным. Видимо, мне нужно 100 повторений, чтобы увидеть этот флажок (см. Раздел дополнения под # 2 этого поста )
Qwix
Хм, не знал об этом требовании.
Кайл Канос
0

J, 94 байта

Работает точно так же, как версия K, а именно с BFS (поэтому он должен выводить все решения). Он печатает пробелы между выходными цифрами, но также и программа K. Я не считаю «s =:», так как это просто название функции (точно так же, как я не буду считать имя файла на другом языке).

   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
Олиус
источник