Sudoku - optymalizacja

IP: *.wroclaw.dialog.net.pl 20.08.05, 22:57
Sudoku, sudoku, sudoku rzygac chce sie juz od tego sudoku :)
Tak samo jak ko-pytko :)
Szala sie przelała jak zobaczyłem "Chwila dla Ciebie" z sudoku na okładce i
jeszcze kilka innych zeszytów z sudoku.
Kiedys myslalem, ze lamiglowki, to kultura wyzsza. Rewiduje swoj poglad. To
popkultura. Wszystko oczywiscie za sprawa jednej lamiglowki

Ale nie o to, nie o to, nie o to... :)
Moze, czlonkowie forum pokusza sie o cos ambitniejszego.

Zadanie 1.
Prosze znalezc sudoku (klasyczne, symetryczne) z minimalna iloscia
podpowiedzi.

Zadanie 2.
Prosze znalezc sudoku (klasyczne, symetryczne) z minimalna suma podpowiedzi.

Zadanie 3.
Rozwiazac zadanie 1 i 2 bez warunku symetrycznosci.

Moje dotychczasowe rekordy to:
- minimalna ilosc podpowiedzi 20
- minimalna suma podpowidzi 82
Moja oba rekordy oparte sa na tym samym dagramie. Bo w pewnym sensie to sa
podobne zadania. Ale oczywiscie nie musi tak byc, ze najlepsze odpowiedzi
beda oparte na tym samym diagramie. I pewnie nie beda.
Jezeli ktos jeszcze ma ochote patrzec na diagramy sudoku, to zapraszam do
rozwazan. Uzycie solverow, programow jak najbardziej dozwolone :)

pozdrawiam,
slawek

    • Gość: Romek Re: Sudoku - optymalizacja IP: *.chello.pl 21.08.05, 15:58
      Święte słowa Panie Sławku. Mnie też się już robi niedobrze na sam dźwięk słowa,
      którego nie wymienię. Tylko że ja niestety nie chcem a muszem siedzieć w tem
      temacie. Ciekawe czy tylko my dwaj tacy uczuleni.
      Ale poglądu bym nie rewidował, bo to nie wina łamigłówki, która sama w sobie
      nie jest głupia. Wszystko przez prasę, która wmawia czytelnikom modę, serwując
      towar w ilościach powodujących obrzydzenie. Co gorsza w kolorowych pisemkach są
      zwykle straszne bzdety. W Wyborczej wygląda to lepiej, ale ile można robić to
      samo! W dodatku organizowanie mistrzostw w sytuacji, gdy w internecie roi sie
      od programów rozwiązujących jest kompletna paranoją - chodzi wyłącznie o zbicie
      kasy na sms-ach. Ale zostawmy to bagienko.
      Mam wrażenie, że zadania, ktore Pan proponuje są ciutek za ambitne jak na to
      forum. No i zostały już sporo lat temu rozgryzione w Japonii, ale nie pamiętam
      źródeł ,w których można by je znaleźć. Wiem tylko, ze minimalna liczba
      podpowiedzi, niesymetrycznie rozmieszczonych, wynosi 17. Pod ręką mam
      symetryczne z 19, ale nie mam pewności,czy to jest minimum z symetrią.
      Jeśli znajdę coś bliższego na ten temat, napiszę.
      Pozdrawiam
      • Gość: tomek Re: Sudoku - optymalizacja IP: *.acn.waw.pl 21.08.05, 22:10
        sudoku jest ostatnio za dużo w prasie, to fakt. Ale...
        > W dodatku organizowanie mistrzostw w sytuacji, gdy w internecie roi sie
        > od programów rozwiązujących jest kompletna paranoją - chodzi wyłącznie o
        zbicie
        > kasy na sms-ach ...
        co ma piernik...? po pierwsze: mistrzostwa nie mają być rozgrywane za pomocą
        smsów. chyba że o innych mistrzostwach myślimy.
        po drugie: tylko jeden etap będzie internetowy, finał będzie na żywo więc
        programy nic tu nie zmieniają.
        po trzecie: etap internetowy będzie tak zorganizowany aby wyeliminować
        (zminimalizować?) możliwość korzystania z różnych pomocy, w tym programów

        > Mam wrażenie, że zadania, ktore Pan proponuje są ciutek za ambitne jak na to
        > forum
        :))
        zastanawiam się jak mam to rozumieć.

        > No i zostały już sporo lat temu rozgryzione w Japonii...
        Tzn. że nie można już się nad tym zastanawiać?
        • Gość: Romek Re: Sudoku - optymalizacja IP: *.chello.pl 21.08.05, 23:33
          Gość portalu: tomek napisał(a):

          >...chyba że o innych mistrzostwach myślimy.

          O innych. Pisałem o mistrzostwach Gazetowych, a Panu zapewne chodzi o
          Politykowe, do których - jak na razie - nic nie mam.

          > > Mam wrażenie, że zadania, które Pan proponuje są ciutek za ambitne jak na
          > > to forum
          > :) zastanawiam się jak mam to rozumieć.

          Delikatna sprawa, więc przemilczę, albo lepiej odwołam to zdanie.

          > > No i zostały już sporo lat temu rozgryzione w Japonii...
          > Tzn. że nie można już się nad tym zastanawiać?

          To była tylko wzmianka gwoli uświadomienia, że odkrywamy Amerykę. Zawsze to
          przyjemniej podążać dziewiczym szlakiem. Jednak ani mi w głowie zniechęcać do
          zastanawiania się, jeśli to komuś sprawia przyjemność, a z pewnością jest
          pożyteczne.
          R.
    • Gość: Tytus Re: Sudoku - optymalizacja IP: *.chello.pl 22.08.05, 11:44
      Temat minimum informacji wstępnych w sudoku jest krótko opisany w Wikipedii
      en.wikipedia.org/wiki/Sudoku
      w końcówce działu Mathematics of Sudoku.
      Tamże są odnośniki do przykładów, m. in. do kolekcji 17273 sudoku z 17
      podpowiedziami.
      Przy symetrycznym rozmieszczeniu cyfr minimum wynosi 18.
      Ale dowodu, że są to minima, jak na razie podobno brak.
      • Gość: slawek Re: Sudoku - optymalizacja IP: *.wroclaw.dialog.net.pl 22.08.05, 23:25
        Rzeczywiscie, jezeli chodzi o minimalna ilosc informacji wstepnych, to dosc
        latwo mozna znalezc /w sieci oczywiscie/, ze chodzi o liczby 17 bez symetrii i
        18 z symetria.
        Choc dowodu nie znalazlem.

        Ciekawy jest link z 17273 sudoku z 17, bo mozna przeanalizowac je pod kątem
        sumy informacji (zadanie 3). Choc w tym przypadku chodzi tak naprawde o
        strukture tych informacji.
        Sposrod podanych przykladow najlepszy wynik daja uklady
        (3,3,3,3,2,1,1,1,0) - (w diagramie 4 cyfry wystepuja potrojnie, jedna podwojnie
        i trzy pojedynczo)
        (4,3,2,2,2,2,1,1,0) - (w diagramie jedna cyfra wystepuje czterokrotnie, jedna
        potrojnie, cztery podwojnie i dwie pojedynczo)

        Oba daja minimalna sume 61. Nie wiem jadnak czy to minimalna suma. Raczej nie.

        Przyklad digramu dla (3,3,3,3,2,1,1,1,0)

        8 0 0 | 0 9 0 | 3 0 1
        2 0 0 | 8 0 0 | 0 0 0
        0 0 0 | 0 0 0 | 0 0 0
        ---------------------
        4 0 0 | 0 0 0 | 0 2 8
        0 0 0 | 0 1 3 | 0 0 0
        0 0 0 | 0 0 0 | 0 6 0
        ---------------------
        0 9 3 | 0 0 0 | 5 0 0
        0 0 0 | 2 0 0 | 0 0 0
        0 1 0 | 0 0 0 | 0 0 0

        /ciekawe jak sie sformatuje/
        W zyciu nie chacialbym czegos takiego rozwiazywac :)

        pozdrawiam,
        slawek
        • pstosia Re: Sudoku - optymalizacja 26.08.05, 12:42
          8 0 0 | 0 9 0 | 3 0 1
          2 0 0 | 8 0 0 | 0 0 0
          0 0 0 | 0 0 0 | 0 0 0
          ---------------------
          4 0 0 | 0 0 0 | 0 2 8
          0 0 0 | 0 1 3 | 0 0 0
          0 0 0 | 0 0 0 | 0 6 0
          ---------------------
          0 9 3 | 0 0 0 | 5 0 0
          0 0 0 | 2 0 0 | 0 0 0
          0 1 0 | 0 0 0 | 0 0 0



          to bylo spoko
    • tororo Re: Sudoku - podwątek o mistrzostwach 24.08.05, 15:41
      Słów parę o obu mistrzostwach.

      Wielka chwała i Gazecie i Polityce za popularyzację sudoku, a co za tym idzie
      za popularyzację łamigłówek.
      Jednak organizując mistrzostwa oba tytuły mogły się troszkę bardziej postarać.

      Po pierwsze - w necie jest masa solverów - programów rozwiązujących sudoku -
      także takie 16 x 16. Zadanie z Polityki 16 x 16 - jest trudne do rozwiązywania
      ręcznego. Jednak rozwiązanie za pomocą solvera zajmuje tyle co wklepanie liczb
      do diagramu. W tym momencie szanse są nierówne - jedni poświęcą na to 10 minut
      inni wiele godzin a jeszcze inni zrezygnują z braku czasu. Na szczęście, w
      przeciwieństwie do Gazety - Polityka organizuje finały "na żywo" - i tam już
      nie będzie można korzystać z programów. Spośród tych co się dostaną do finału
      wygrają ci, który najsprawniej poradzą sobie z zadaniami finałowymi. Ciekaw
      jestem proporcji finalistów - ilu z nich rozwiąże zadanie eliminacyjne ręcznie
      bez wspomagania solverami a ilu przy pomocy programów.

      W przypadku Gazety - jest dużo gorzej - tego samego dnia kiedy ogłaszane są
      diagramy konkursowe można z witryny producenta sudoku publikowanych w Gazecie
      (pappocom - www.sudoku.com) ściągnąć rozwiązania. Nie mam wątpliwości żeby ten
      adres tu podawać. Po pierwsze był już podany w jednym z wątków, po drugie – nie
      ma to już większego wpływu na przebieg konkursu, który się właśnie kończy. Na
      dodatek nie ma żadnych finałów - bezpośredniego zmierzenia się z zadaniami.
      Faworytami będą więc te osoby, które znają wspomnianą witrynę. A ponieważ są
      nagrody pieniężne - więc myślę, że część osób nie będzie miała skrupułów w
      wyścigu o kasę. Po prostu plama.

      A przecież wystarczyło ułożyć nietypowe sudoku (w necie jest masa przykładów,
      różne kształty diagramów i „subdiagramów”, różne wielkości itp ) – takie na
      które nie ma solverów – i oczywiście nie publikować. I byłoby ciekawie,
      elegancko i sprawiedliwie.

      Pozdr

      tororo
      www.sfinks.org.pl
      • tororo Re: Sudoku - podwątek o mistrzostwach - 24.08.05, 15:45
        Drobna errata
        W przedostatnim zdaniu zamiast "nie publikować" powinno być "nie publikować
        rozwiązań przed upływem ich terminu losowania".

        Pozdr
        tororo
        • Gość: tomek Re: Sudoku - podwątek o mistrzostwach - IP: *.acn.waw.pl 24.08.05, 18:40

          nie martwiłbym się o internetowe zawody organizowane przez Politykę. Solvery
          będą tam wyeliminowane na tyle aby nie namieszać za bardzo uczciwym finalistom
Pełna wersja