Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

Ahoj, narazil jsem na zajímavý řešič sudoku, který jsem si upravil a pošlu ho sem jako ukázkový program. Co mě ale zajímá je, jak z řešiče udělat generátor. Ví někdo?

Není problém nechat si vegenerovat všechna sudoku, ale jak vygenerovat náhodné a jak z něj udělat zadání?

Odpovědět 12.5.2013 11:47
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

Zatím sem hodím co mám:

static bool ZkontrolujRadek(int radek, int hodnota, int[,] pole)
        {

            for (int i = 0; i < 9; i++)
            {
                if (pole[i, radek] == hodnota) return false;
            }
            return true;
        }

        static bool ZkontrolujSloupec(int sloupec, int hodnota, int[,] pole)
        {

            for (int i = 0; i < 9; i++)
            {
                if (pole[sloupec, i] == hodnota) return false;
            }
            return true;
        }

        static bool ZkontrolujCtverec(int radek, int sloupec, int hodnota, int[,] pole)
        {
                for (int i = 0; i < 3; i++)
                {
                        for (int j = 0; j < 3; j++)
                        {
                                if (pole[sloupec - (sloupec % 3) + i, radek - (radek % 3) + j] == hodnota)
                                        return false;
                        }
                }
                return true;
        }

        static bool Zkontroluj(int radek, int sloupec, int hodnota, int[,] pole)
        {
            if (!ZkontrolujRadek(radek, hodnota, pole)) return false;
            if (!ZkontrolujSloupec(sloupec, hodnota, pole)) return false;
            if (!ZkontrolujCtverec(radek, sloupec, hodnota, pole)) return false;
            return true;
        }

        static int[,] Vyres(int hodnota, int px, int py, int[,] pole)
        {
            int[,] pPole = new int[9, 9];
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    pPole[j, i] = pole[j, i];
                }
            }
            pPole[px, py] = hodnota;
            for (int x = 0; x < 9; x++)
            {
                for (int y = 0; y < 9; y++)
                {
                    if (pPole[x, y] == 0)
                    {
                        for (int val = 1; val <= 9; val++)
                        {
                            if (Zkontroluj(y, x, val, pPole))
                            {
                                Vyres(val, x, y, pPole);
                            }
                        }
                        return null;
                    }
                }
            }

            Vypis(pPole);
            return pPole;
        }

        static void Vypis(int[,] pole)
        {
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    Console.Write(pole[j, i]);
                }
                Console.WriteLine();
            }
            Console.WriteLine("-----------------");
        }

        static void Main(string[] args)
        {
            int[,] pole = new int[9, 9];


            pole[0,0] = 3;
                    pole[3,0] = 4;
                    pole[8,0] = 9;

                    pole[7,1] = 2;
                    pole[8,1] = 6;

                    pole[0,2] = 4;
                    pole[3,2] = 1;
                    pole[4,2] = 8;

                    pole[1,3] = 9;
                    pole[7,3] = 4;
                    pole[8,3] = 3;

                    pole[4,4] = 6;
                    pole[5,4] = 2;

                    pole[1,5] = 5;
                    pole[2,5] = 8;

                    pole[2,6] = 4;
                    pole[3,6] = 6;
                    pole[5,6] = 3;
                    pole[6,6] = 2;

                    pole[1,7] = 8;
                    pole[2,7] = 7;
                    pole[5,7] = 5;
                    pole[6,7] = 1;

                    pole[5,8] = 1;
                    pole[6,8] = 7;

            Vypis(pole);

            Vyres(pole[0,0], 0, 0, pole);

            Console.ReadKey();
        }
Editováno 12.5.2013 11:50
Nahoru Odpovědět 12.5.2013 11:49
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Robert Zemánek (bobánek):

zajímavý kód. já jednou řešil že máš v texťáku čísla jako v sudoku a chceš zjistit, zda je to správně vyřešené.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace Sudoku
{
    class Program
    {
        static void Main()
        {
            string path = "C:/Sudoku/Sudoku/sudoku.txt";

            int[,] sudoku = FileProcessor.GetLines("X:/PRG/Visual Studio/Sudoku/Sudoku/sudoku.txt");

            int[] section = SudokuParser.GetSection(sudoku, Type.Square, 8);

            bool right_solution = true;

            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    if (!SudokuParser.IsRightSolution(SudokuParser.GetSection(FileProcessor.GetLines(path), (Type)j, i)))
                        right_solution = false;
                }
            }

            if (right_solution)
                Console.WriteLine("Sudoku je správně vyřešené.");

            else
                Console.WriteLine("Sudoku je špatně vyřešené.");

            Console.ReadKey();
        }
    }

    public static class SudokuParser
    {
        public static int[] GetSection(int[,] sudoku, Type type, int number)
        {
            int[] result = new int[9];

            if (type == Type.Column)
            {
                for (int i = 0; i < 9; i++)
                {
                    result[i] = sudoku[i, number];
                }
            }

            else if (type == Type.Row)
            {
                for (int i = 0; i < 9; i++)
                {
                    result[i] = sudoku[number, i];
                }
            }

            else if (type == Type.Square)
            {
                int i = 0;

                for (int a = 0; a < 3; a++)
                {
                    for (int b = 0; b < 3; b++)
                    {
                        result[i] = sudoku[(3 * (number % 3)) + a, (3 * (int)(number / 3)) + b];
                        i++;
                    }
                }
            }

            return result;
        }

        public static bool IsRightSolution(int[] section)
        {
            bool result = true;

            for (int i = 1; i <= 9; i++)
            {
                if(!section.Contains(i))
                    result = false;

                if (section.Count(n => n == i) > 1)
                    result = false;
            }

            return result;
        }
    }

    public static class FileProcessor
    {
        public static int[,] GetLines(string path)
        {
            int[,] sudoku = new int[9,9];
            string[] aux = new string[9];

            StreamReader sr = File.OpenText(path);

            for (int x = 0; x < 9; x++)
            {
                aux = sr.ReadLine().Split(' ');

                for (int y = 0; y < 9; y++)
                {
                    int a;

                    if (int.TryParse(aux[y], out a))
                        sudoku[x, y] = a;

                    else
                        throw new Exception("Chyba, znaky v souboru nejsou čísla.");
                }
            }

            sr.Close();

            return sudoku;
        }
    }

    public enum Type { Row, Column, Square }
}
Editováno 12.5.2013 11:59
Nahoru Odpovědět 12.5.2013 11:59
Jsem jako holub.
Avatar
Petr Nymsa
Redaktor
Avatar
Odpovídá na David Čápka
Petr Nymsa:

Zajímavá věcička, kdysi jsem toto zde řešil, ale nevyřešil :D. Každopádně na generování jsem třeba našel že se využívá backtracking http://www.algoritmy.net/…/1351/Sudoku. Dál jsem nezkoumal jestli je to funkční, ale asi ano :)

Nahoru Odpovědět 12.5.2013 12:03
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Petr Nymsa
David Čápka:

Backtracking tu využívám taky. Ono by to šlo udělat tak, že náhodně vygeneruji pár čísel a nechám ho to vyřešit a jestli to zvládne, tak je to řešitelné, ale jestli není lepší způsob :)

Nahoru Odpovědět 12.5.2013 14:32
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Petr Nymsa
Redaktor
Avatar
Odpovídá na David Čápka
Petr Nymsa:

No tohle mi přijde moc složitý, resp. pomalý. Uděláš dejem tomu 17 náhodných čísel (prý nejmenší možný počet pro vyřešení), necháš ho to zkusit vyřešit, když nevyřeší, musíš nahodit jiná čísla a to klidně stejná ale rozmístit jinak, takže mi přijde že to bude sakra pomalý. Netrdím že rychlost yb měla být, kliknu a mám sudoku.. až budu mít čas , zkusím si to napsat :)

Nahoru Odpovědět 12.5.2013 14:40
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Petr Nymsa
David Čápka:

Druhý způsob je nechat si vyřešit sudoku kde bude třeba jen 1 nebo 2 náhodná čísla (to by mělo jít vždycky) a potom odmazat náhodný počet čísel v rozmezí aby tam zbylo 17-25 třeba. To by mohlo už jít.

Nahoru Odpovědět 12.5.2013 14:52
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Petr Nymsa
Redaktor
Avatar
Nahoru Odpovědět 12.5.2013 15:00
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Petr Nymsa
David Čápka:

Jenže to zas nebude náhodné, ale pořád to 1234 atd. jak to zkouší ten backtracking. Sakra. Tak upravím backtracking aby si čísla vybral náhodně, to bude jednoduché. Myslím, že to mám, až se k tomu zas dostanu, tak to zkusím a hodím to sem :)

Nahoru Odpovědět 12.5.2013 15:02
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Petr Nymsa
Redaktor
Avatar
Odpovídá na David Čápka
Petr Nymsa:

Každopádně máš už lepší řešení , než jsem měl kdysi dávno já ! :D

Nahoru Odpovědět 12.5.2013 15:08
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
Odpovídá na David Čápka
Lukáš Hruda (Luckin):

Když budete pouze generovat náhodná čísla, tak to sudoku bude mít spoustu řešení. Sudoku má pouze jedno správné řešení.

 
Nahoru Odpovědět 12.5.2013 15:19
Avatar
Petr Nymsa
Redaktor
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Petr Nymsa:

Když budeme generovat čísla, musí se najít jedno správné řešení, proto říkám že to bude pomalý.

Nahoru Odpovědět 12.5.2013 15:23
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
Odpovídá na Petr Nymsa
Lukáš Hruda (Luckin):

Já bych to udělal obráceně... Vygenerovat plné vyřešené sudoku a potom odebírat čísla z takových míst, aby vždy šlo na to místo vrátit pouze to konkrétní číslo.

 
Nahoru Odpovědět 12.5.2013 15:28
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Lukáš Hruda (Luckin)
David Čápka:

To udělám, ale nevím jak zajistit, aby tam šlo vrátit jen to jedno, to bude zas hrozně pomalé ověřit to pro další. Něco naprogramuji a nechám program aby se pak sám ověřil a uvidíme, třeba to bude fungovat :D

Nahoru Odpovědět 12.5.2013 15:32
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

A už jsem měl hodnotit :`

Nahoru Odpovědět 12.5.2013 15:32
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na David Čápka
Lukáš Hruda (Luckin):

Zkusím pak něco vymyslet, ale teď musím koukat na filmy k povinné četbě k maturitě.

 
Nahoru Odpovědět  +1 12.5.2013 15:40
Avatar
Petr Nymsa
Redaktor
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Petr Nymsa:

Koukám že to je asi všude stejný :D.. kolik máš přečteno a kolik nakoukáno ? Já jsem tedy zatím ve druháku ale nevidím že bych do 4 stihl řpřečíst všechny knížky :D

Nahoru Odpovědět 12.5.2013 15:51
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
Odpovídá na Petr Nymsa
Lukáš Hruda (Luckin):

Já mám do maturity 2 týdny a nepřečetl jsem nic. Z mého seznamu 20 knih je jich 13 zfilmovaných, viděl jsem jich 7, do pondělí chci dokoukat ten zbytek.
Je to strašná otrava, zatím bezkonkurenčně nejhorší byla Kytice od Erbena.

 
Nahoru Odpovědět 12.5.2013 16:00
Avatar
Petr Nymsa
Redaktor
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Petr Nymsa:

No tak já na tom jsem ještě dobře :D Dřív jsem četl hodně, mám přečtených asi 7 knížek, nejhorší zážitek Faust :X

Nahoru Odpovědět 12.5.2013 16:10
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
Зайчик
Člen
Avatar
Odpovídá na Petr Nymsa
Зайчик:

Učitelé jsou věční optimisti. Nám už od prváku říká ať ty knihy průběžně čteme. Každopádně nevím které, nemám sešit, nemám učebnici. Takže tak nějak doufám že mí 10min před maturou z literatury někdo řekne hrubý základ a zbytek si domyslím. :D asi jako půlka z nás

Nahoru Odpovědět 12.5.2013 16:14
Коммунизм для нашего будущего!
Avatar
Petr Nymsa
Redaktor
Avatar
Odpovídá na Зайчик
Petr Nymsa:

Tak u nás je také minimálně 20 knih povinnýh. Například Hobit nebo My děti ze stanice ZOO ještě byly dobrý. Počkat křivdím, Hobit a Tolkienův svět totálně žeru ! :D Mám načteny všechny Pány prstenů, Hobita a i z půlky Silmalirion, bohužel jsem ho vrátil a nějak jsem nenašel čas ho dočíst :(

Nahoru Odpovědět 12.5.2013 16:17
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
Зайчик
Člen
Avatar
Odpovídá na Petr Nymsa
Зайчик:

Já mám přečteny dva díly jazyka C, rozumíme C++, 2 knížky o jave a 1 o C#. Tak snad mi to uznají :D

Nahoru Odpovědět  +1 12.5.2013 16:18
Коммунизм для нашего будущего!
Avatar
Odpovídá na Petr Nymsa
Lukáš Hruda (Luckin):

Já si přečtu jenom Torzo naděje, to má asi 50 stran. U zbytku budu doufat, že mi postačí filmy a informace, které jsem si o těch knihách našel na netu.

 
Nahoru Odpovědět 12.5.2013 16:23
Avatar
Petr Nymsa
Redaktor
Avatar
Odpovídá na Зайчик
Petr Nymsa:

Mám načtené 2 knížky o HTML / CSS, C#, trocha PHP a Adobe Photoshop CS5, také bych rád kdyby uznali, když jsem na té odborné škole, ale asi ne :D

Nahoru Odpovědět 12.5.2013 16:24
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
Kit
Redaktor
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Kit:

Tuším, že jsem v povinné četbě zahlédl i Starý zákon. To na jeden večer není ani náhodou :)

Nahoru Odpovědět 12.5.2013 16:29
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Petr Nymsa
Redaktor
Avatar
Odpovídá na Kit
Petr Nymsa:

No my máme v povinné četbě třeba 5 knih Mojžíšovích, opravud přemýšlím že si je přečtu :D ]:>

Nahoru Odpovědět 12.5.2013 16:31
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
Kit
Redaktor
Avatar
Odpovídá na Petr Nymsa
Kit:

Ty Mojžíšovy knihy jsou v pohodě, to se číst dá, ale Žalmy...

Nahoru Odpovědět 12.5.2013 16:32
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Petr Nymsa
Redaktor
Avatar
Odpovídá na Kit
Petr Nymsa:

Ne to si opravdu nepřečtu, jelikož máme i spousty jiných na výběr, tuto knihu směle vynechám :)

Nahoru Odpovědět 12.5.2013 16:35
Pokrok nezastavíš, neusni a jdi s ním vpřed
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 28 zpráv z 28.