Diskuze: Sudoku - Algoritmus

Petr Nymsa

Tvůrce

Petr Nymsa:14.11.2012 19:34

Ahoj, řeším algoritmus pro "blbé" sudoku.Nejedná se oklasické sudoku, tedy nemá 9 čtverců o 9 políčkách. Ale je to pouze čtverec 9x9, kde v každém sloupci resp. řádku musí být každé číslo pouze jednou. Založil jsem si výchozí šablonu, kde už jsou čísla mírně proházená

{1,2,3,4,5,6,7,8,9},
      {9,1,2,3,4,5,6,7,8},
      {8,9,1,2,3,4,5,6,7},
      {7,8,9,1,2,3,4,5,6},
      {6,7,8,9,1,2,3,4,5},
      {5,6,7,8,9,1,2,3,4},
      {4,5,6,7,8,9,1,2,3},
      {3,4,5,6,7,8,9,1,2},
      {2,3,4,5,6,7,8,9,1}};

Nyní nějakým způsobem budu muset čísla ještě proházet. Ovšem nenapadá mě nijak velmi dobré řešení. Prosím o nějaký popostrknutí jakým způsobem. Nežádám kód, pouze nějaký tip. Díky.

Editováno 14.11.2012 19:35

Odpovědět

14.11.2012 19:34

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

David Hartinger

Vlastník

David Hartinger:14.11.2012 20:01

A čeho chceš docílit? Chceš jen naplnit prázdné pole tak, aby to bylo tohle sudoku?

Nahoru Odpovědět

14.11.2012 20:01

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

Petr Nymsa

Tvůrce

Petr Nymsa:14.11.2012 20:16

Pardon, špatně jsme vyjádřil co požaduji. Program vygnereuje pole 9x9, kde v každém řádků budou čísla od 1-9. Zároveň se nesmí opakovat ve sloupcích dvě stejná čísla. Poté některá čísla zakryje a uživatel bude muset dořešit. Jedná se tedy o zjednodušené sudoku.

Nahoru Odpovědět

14.11.2012 20:16

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

matesax

Tvůrce

matesax:14.11.2012 20:38

Google?

http://en.wikipedia.org/…u_algorithms

http://www.algoritmy.net/…/1351/Sudoku

Nahoru Odpovědět

14.11.2012 20:38

Petr Nymsa

Tvůrce

Petr Nymsa:14.11.2012 20:45

Ano google jsem použít mohl, v tom případě by devbook neměl smysl . Většina problémů se dá prakticky "vygůglit". Co tu ale nechat i komentáře pro jiné ? Každopádně jsem už možná přišel jak to vyřešit. Ještě sem psát nebudu ani nápad, nejsem si jistý jestli je vůbec použitelný.

Nahoru Odpovědět

14.11.2012 20:45

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

matesax

Tvůrce

matesax:14.11.2012 20:48

Přijde mi lepší napsat o nějakém algoritmu článek, než se na něj ptát - jak jsi napsal - vygooglit to dokáže každý... Problém je, že mnoho alogritmů jen těžko seženeš Česky popsané, a nebo jsou hodně složité - což tento rozhodně není nejjednodušší - takže si článek zaslouží... Čily až jej pochopíš, tak jej můžeš pěkně popsat - aby jej mohl pochopit i nějaký začátečník...

Editováno 14.11.2012 20:49

Nahoru Odpovědět

14.11.2012 20:48

Petr Nymsa

Tvůrce

Petr Nymsa:14.11.2012 20:51

To je pravda . Každopdáně nehledám algoritmus na to pravé sudoku. Hledám na to velmi zjednodušené. Stačí "nějak lehce" proházet několik čísel. Jak jsem psal, nápad už mám. Pokud budu úspěšný, určitě nezapomenu informovat.

Nahoru Odpovědět

14.11.2012 20:51

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

Kit

Tvůrce

Kit:14.11.2012 20:56

Některé algoritmy na http://www.algoritmy.net/ jsou skutečně hezky česky popsané. Dokonce jsem tam našel i pár algoritmů pro řazení.

Nahoru Odpovědět

14.11.2012 20:56

Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.

Petr Nymsa

Tvůrce

Petr Nymsa:14.11.2012 20:58

Ano, algoritmy.net nejsou špatné. Také jsem už tam našel jednou co jsem hledal a pomohlo to.

Nahoru Odpovědět

14.11.2012 20:58

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

matesax

Tvůrce

matesax:14.11.2012 21:22

Nechápu, co chceš na tom zjednodušovat - dělá to, to co popisuješ... Zjednodušením to spíš ztížíš řekl bych - spíše bych si s tím dal tu práci a právě se snažil pochopit ten algoritmus...

Nahoru Odpovědět

14.11.2012 21:22

Petr Nymsa

Tvůrce

Petr Nymsa:14.11.2012 21:28

Sudoku bude ulehčený, že nemusíš řešit čtverce, tedy řešíš pouze sloupce a řádky, tudíž podle mě bude i jednodušší algoritmus. Ano, až naleznu čas podvám se na ten "složitější". Bohužel teď kvůli škole moc nestíhám, mám dělat aplikaci pro Windows 8 -> Prvouka 1,2 třída pro základní školy a další. No málo času, mnoho věcí

Nahoru Odpovědět

14.11.2012 21:28

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

matesax

Tvůrce

matesax:14.11.2012 22:45

Zplodil jsem toto:

List<int[]> sudokuArea = new List<int[]>() { new int[9], new int[9], new int[9], new int[9], new int[9], new int[9], new int[9], new int[9], new int[9] };

for (int x = 0; x < 9; x++)
{
    List<int> column = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }.OrderBy(emp => Guid.NewGuid()).ToList();

    for (int y = 0; y < 9; y++)
        foreach (int i in column)
            if (!sudokuArea[y].Contains(i))
            {
                sudokuArea[y][x] = i;
                column.Remove(i);
                break;
            }
}

Má to ale nějakou díru - zítra ji opravím - nepředběhneš-li mne...

Nahoru Odpovědět

14.11.2012 22:45

Kit

Tvůrce

Kit:15.11.2012 6:39

Možná jsem šťoura, ale sudoku mi nepřipadá jako seznam, ale spíš jako pole. Dokonce dvojrozměrné.

Nahoru Odpovědět

15.11.2012 6:39

Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.

David Hartinger

Vlastník

David Hartinger:15.11.2012 11:53

Matesax zásadně používá seznamy místo dvourozměrného pole, dělal přes ně i šachovnici, už jsem mu to říkal asi stokrát

Nahoru Odpovědět

15.11.2012 11:53

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

matesax

Tvůrce

matesax:15.11.2012 13:48

int[][] sudokuArea = new int[9][] { new int[9], new int[9], new int[9], new int[9], new int[9], new int[9], new int[9], new int[9], new int[9] };
Random r = new Random();

for (int x = 0; x < 9; x++)
{
    int[] column = new int[9];

    for (int y = 0; y < 9; y++)
    {
        List<int> rough = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }.OrderBy(emp => Guid.NewGuid()).ToList();

        rough.RemoveAll(t => sudokuArea[y].Contains(t) || column.Contains(t));
        column[y] = rough[r.Next(rough.Count - 1)];
        sudokuArea[y][x] = column[y];
    }
}

Nahoru Odpovědět

15.11.2012 13:48

Kit

Tvůrce

Kit:15.11.2012 14:04

Myslel jsem si, že v C# se dvourozměrné pole deklaruje jednodušeji:

int[,] sudokuArea = new int[9,9];

Nahoru Odpovědět

15.11.2012 14:04

Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.

matesax

Tvůrce

matesax:15.11.2012 14:07

Právě proto jsem měl list - jak se dostanu k jednotlivým řádkům? Snížil jsem to na pole polí, ale jak dostat z více dimenzí řádek jsem nikde nenašel - a další cyklus opravdu nechci...

Editováno 15.11.2012 14:08

Nahoru Odpovědět

15.11.2012 14:07

Kit

Tvůrce

Kit:15.11.2012 14:18

S vícerozměrným polem se obvykle pracuje s vícenásobným cyklem. Tedy pokud neděláš ve Fortranu nebo Octave.

Nahoru Odpovědět

15.11.2012 14:18

Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.

matesax

Tvůrce

matesax:15.11.2012 14:43

A ten já nechci ("a další cyklus opravdu nechci") - přeci je lepší toto, než další cyklus - ne?

Nahoru Odpovědět

15.11.2012 14:43

Petr Nymsa

Tvůrce

Petr Nymsa:15.11.2012 16:21

Popravdě mi opravdu přijde lepší dvourozěmrné pole. Přistupuje se k němu přes dva for cykly, tedy ve stylu

int[,]pole=new int[9,9];
for(int x=0;x<pole.GetLength(0);x++)
{
  for(int y=0;y<pole.GetLength(1);y++)
  {
    pole[x,y]=1;
  }
}

Editováno 15.11.2012 16:22

Nahoru Odpovědět

15.11.2012 16:21

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

matesax

Tvůrce

matesax:15.11.2012 16:25

OK - 4 cykly lepší, než 2? Proč ze mě oba děláte blbce - vím, jak pracovat s xrozměrnými poli - a mnohem lépe to jde přes LINQ - ovšem jak jsem napsal - dostaň mi z toho bez cyklu řádek - u toho pole polí jen zadám index...

Editováno 15.11.2012 16:26

Nahoru Odpovědět

15.11.2012 16:25

Kit

Tvůrce

Kit:15.11.2012 16:28

Máš ještě další možnost: Udělat 81 objektů, které naskládáš do 18 seznamů (9 vodorovně a 9 svisle) a těchto 18 seznamů (případně ještě dalších 9 pro čtverce 3×3 v úplném sudoku) si dáš do jednoho nadřazeného seznamu. Vystačíš si pak i bez cyklů.

To by také mohla být odpověď na tvou otázku kolem "jak dostat z více dimenzí řádek". Navíc můžeš získat i sloupec.

Editováno 15.11.2012 16:30

Nahoru Odpovědět

15.11.2012 16:28

Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.

matesax

Tvůrce

matesax:15.11.2012 16:30

OK - čím více cyklů, tím více programátor? - OK...

Prostě proč bych jako idiot zadával jen index, když mohu použít 2 cykly (ještě k tomu druhý je vnořený) - že?

Editováno 15.11.2012 16:32

Nahoru Odpovědět

15.11.2012 16:30

Kit

Tvůrce

Kit:15.11.2012 16:39

Však jsem ti napsal řešení bez cyklů.

Nahoru Odpovědět

15.11.2012 16:39

Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.

Petr Nymsa

Tvůrce

Petr Nymsa:15.11.2012 16:41

Momentálně přesně nevím pointu dohadování. Jak je to s rychlostmi, v tom zkušený nejsem, ale pro mě je přehlednější použít dva cykly, a tím pádem napsat dva indexy.

Nahoru Odpovědět

15.11.2012 16:41

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

matesax

Tvůrce

matesax:15.11.2012 16:42

A co tím tvým získám? Já jsem to pochopil - je mnohem lepší si celý řádek postavit 2 cykly, než ho rovnou mít pod indexem v poli... Vůbec nejlepší by bylo, mít takových 10 cyklů a 120 vnořených - aby se mi ta aplikace vůbec nespustila...

Jasně - čím více cyklů, tím bude větší přehlednost - můj kód je absolutně nepřehledný - vůbec není jasné, co dělá... Takže si to celé roztahej nejlépe ještě tak do 10 souborů...

Editováno 15.11.2012 16:45

Nahoru Odpovědět

15.11.2012 16:42

Petr Nymsa

Tvůrce

Petr Nymsa:15.11.2012 16:48

No, už jen chci dodat , to řešení na sudoku. Jak jsem psal, hledal jsem řešení pro zjednodušenou variantu. Nakonec, jsem tedy náhodně vybral dva sloupce v poli a ty mezi sebou prohodil. Takto se to prohodí několiklikrát. Poté náhodně zakryju několik polí a ejhle máme tu jednoduché sudoku. Pokud jich zakryju mnohem více, dokonce už se u toho musí začít i přemýšlet . Ale ano, není to řešení algoritmu pro tvorbu Sudoku jako takového.

Nahoru Odpovědět

15.11.2012 16:48

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

Kit

Tvůrce

Kit:15.11.2012 16:53

Pointa dohadování je v tom, že matesax nechce vnořené cykly. Tak jsem mu navrhl řešení bez cyklů, ale myslí si, že si jen z něho dělám srandu. Přitom jsem to myslel vážně, v Lispu bych to tak určitě udělal.

Z hlediska sudoku jsou totiž řádky a sloupce (příp. i čtverce 3×3) z hlediska kontroly jedinečnosti symbolu rovnocenné.

Nahoru Odpovědět

15.11.2012 16:53

Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.

matesax

Tvůrce

matesax:15.11.2012 16:55

Co je na tom k nepochoení?

int[][] sudokuArea = new int[9][] { new int[9], new int[9], new int[9], new int[9], new int[9], new int[9], new int[9], new int[9], new int[9] };
Random r = new Random();

for (int x = 0; x < 9; x++)
{
    int[] column = new int[9];

    for (int y = 0; y < 9; y++)
    {
        List<int> rough = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }.OrderBy(emp => Guid.NewGuid()).ToList();

        rough.RemoveAll(t => sudokuArea[y].Contains(t) || column.Contains(t));
        column[y] = rough[r.Next(rough.Count - 1)];
        sudokuArea[y][x] = column[y];
    }
}

Jen to musíš dotáhnout do konce - chybí tomu nějaké(á) pravidlo(a) - na to už by jsis musel přijít sám... (Nějaké modely kombinací - zde nejsou a algoritmus brzy dojde do místa, kde nic neprojde přes podmínku...)

Kit:

To už je lepší napsat to do TXT - a randomizovat přesouváním bloků...

Editováno 15.11.2012 16:56

Nahoru Odpovědět

15.11.2012 16:55

Kit

Tvůrce

Kit:15.11.2012 16:58

A proč tam máš ten dvojitý cyklus? Myslel jsem si, že ho nechceš.

Nahoru Odpovědět

15.11.2012 16:58

Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.

Petr Nymsa

Tvůrce

Petr Nymsa:15.11.2012 17:01

Já neřekl, že tam není nic k nepochopení . Ale dělat pole polí a potom ještě list, mi přijde horší způsob. Holt, asi kažý jsme zvyklí psát programy jinak. Neříkám, že se v tom vyznám extra. C# se věnuju přes rok.

Nahoru Odpovědět

15.11.2012 17:01

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

matesax

Tvůrce

matesax:15.11.2012 17:01

Nechci - ale myslel jsem, že mě s mým hlavním nápadem pošlete do pryč. Takže jsem jej napsal - vytvoř sudoku model do TXT. A vytvoř model bloků - tak, aby se jejich přesouváním nenarušily stanovené vztahy - jejich mícháním pak budeš randomizovat...

Nahoru Odpovědět

15.11.2012 17:01

Kit

Tvůrce

Kit:15.11.2012 17:55

Jenže Petr Nymsa potřebuje míchat řádky i sloupce.

Nahoru Odpovědět

15.11.2012 17:55

Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.

matesax

Tvůrce

matesax:15.11.2012 17:59

Bloky myslím předem navolené skupiny...

Nahoru Odpovědět

15.11.2012 17:59

Nejčastěji vyhledáváné

Diskuze: Sudoku - Algoritmus