Diskuze: Generátor sudoku

David Hartinger

Vlastník

David Hartinger:12.5.2013 11:47

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

New kid back on the block with a R.I.P

David Hartinger

Vlastník

David Hartinger:12.5.2013 11:49

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

New kid back on the block with a R.I.P

Robert Zemánek (bobánek)

Člen

Robert Zemánek (bobánek):12.5.2013 11:59

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.

Petr Nymsa

Tvůrce

Petr Nymsa:12.5.2013 12:03

Zajímavá věcička, kdysi jsem toto zde řešil, ale nevyřešil . 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

David Hartinger

Vlastník

David Hartinger:12.5.2013 14:32

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

New kid back on the block with a R.I.P

Petr Nymsa

Tvůrce

Petr Nymsa:12.5.2013 14:40

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

David Hartinger

Vlastník

David Hartinger:12.5.2013 14:52

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

New kid back on the block with a R.I.P

Petr Nymsa

Tvůrce

Petr Nymsa:12.5.2013 15:00

To už by šlo

Nahoru Odpovědět

12.5.2013 15:00

Pokrok nezastavíš, neusni a jdi s ním vpřed

David Hartinger

Vlastník

David Hartinger:12.5.2013 15:02

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

New kid back on the block with a R.I.P

Petr Nymsa

Tvůrce

Petr Nymsa:12.5.2013 15:08

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

Nahoru Odpovědět

12.5.2013 15:08

Pokrok nezastavíš, neusni a jdi s ním vpřed

Lukáš Hruda

Tvůrce

Lukáš Hruda:12.5.2013 15:19

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

Petr Nymsa

Tvůrce

Petr Nymsa:12.5.2013 15:23

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

Lukáš Hruda

Tvůrce

Lukáš Hruda:12.5.2013 15:28

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

David Hartinger

Vlastník

David Hartinger:12.5.2013 15:32

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

Nahoru Odpovědět

12.5.2013 15:32

New kid back on the block with a R.I.P

David Hartinger

Vlastník

David Hartinger:12.5.2013 15:32

A už jsem měl hodnotit

Nahoru Odpovědět

12.5.2013 15:32

New kid back on the block with a R.I.P

Lukáš Hruda

Tvůrce

Lukáš Hruda:12.5.2013 15:40

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

Nahoru Odpovědět

12.5.2013 15:40

Petr Nymsa

Tvůrce

Petr Nymsa:12.5.2013 15:51

Koukám že to je asi všude stejný .. 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

Nahoru Odpovědět

12.5.2013 15:51

Pokrok nezastavíš, neusni a jdi s ním vpřed

Lukáš Hruda

Tvůrce

Lukáš Hruda:12.5.2013 16:00

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

Petr Nymsa

Tvůrce

Petr Nymsa:12.5.2013 16:10

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

Nahoru Odpovědět

12.5.2013 16:10

Pokrok nezastavíš, neusni a jdi s ním vpřed

Зайчик

Člen

Зайчик:12.5.2013 16:14

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. asi jako půlka z nás

Nahoru Odpovědět

12.5.2013 16:14

Коммунизм для нашего будущего!

Petr Nymsa

Tvůrce

Petr Nymsa:12.5.2013 16:17

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 ! 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

Зайчик

Člen

Зайчик:12.5.2013 16:18

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í

Nahoru Odpovědět

12.5.2013 16:18

Коммунизм для нашего будущего!

Lukáš Hruda

Tvůrce

Lukáš Hruda:12.5.2013 16:23

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

Petr Nymsa

Tvůrce

Petr Nymsa:12.5.2013 16:24

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

Nahoru Odpovědět

12.5.2013 16:24

Pokrok nezastavíš, neusni a jdi s ním vpřed

Kit

Tvůrce

Kit:12.5.2013 16:29

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ů.

Petr Nymsa

Tvůrce

Petr Nymsa:12.5.2013 16:31

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

Nahoru Odpovědět

12.5.2013 16:31

Pokrok nezastavíš, neusni a jdi s ním vpřed

Kit

Tvůrce

Kit:12.5.2013 16:32

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ů.

Petr Nymsa

Tvůrce

Petr Nymsa:12.5.2013 16:35

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