Matematické Fórum

Mythic · 13. 11. 2012 12:08

Ahoj,
snažím se vytvořit program, který bude generovat sudoku. Prozatím řeším, jak rozmístit čísla do čtverce 9x9 aby se v žádném řádku, sloupci ani menších polích 3x3 neopakovali dvě čísla (předpokládám, že všichni vědí jak vypadá sudoku).

Nějak nemůžu přijít na to, jaký zvolit efektivní postup. Můj první návrh měl fungovat asi takto:

1. vygeneruju dvourozměrné pole a každý ř'ádek vyplním čísly 1-9, následně je promíchám.
2. zjistím jestli se ve sloupečkách neopakují dvě čísla a pokud ano, promíchám to znovu (a tady už narážím na problém).
3. zajistit aby se neopakovala čísla na souřadnicích [1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3] a pak i v dalších čtverečcích 3x3. (ale to už mi začíná připadat strašně komplikované a vůbec nevím jak bych to naprogramoval).

Neexistuje nějaký snazší způsob jak generovat sudoku ? Díky :)

LukasM · 15. 11. 2012 14:12

↑ Mythic:
Nepřemýšlel jsem o tom moc do hloubky, ale dělal bych to jinak. Náhodně umístím čísla 1-9 do prvního řádku. Pak jdu na druhý řádek, a půjdu po číslech. Nejdřív jednička. V prvním řádku už jedna je, a určitě padla do jednoho z těch devíti bloků. Takže ji mohu umístit už jen na šest políček. Umístím ji náhodně na jedno z nich. Totéž 2-9. Totéž třetí řádek, tam už pro každé číslo budu mít jen tři možnosti.

Čtvrtý řádek. Tam mi na chvíli vypadne kontrola těch bloků, ale zase se budu muset dívat jestli náhodou už dané číslo není někde nad aktuálním políčkem. Atd. Atd.

Jak to udělat efektivně, to rozmyšlené nemám. Ale vzhledem k šílenosti tvého návrhu ti o to asi nejde, takže klidně hrubou silou. V každém kroku vybrat index políčka na daném řádku, zkusmo tam číslici umístit, a zkusit jestli porušuje nějakou podmínku. Pokud ano, umístím ji na jinou pozici. Pokud ne, jdu na další číslici.

To by mělo fungovat, myslím.

mountdoom

Zdravím,

tady jsem ti naprogramoval generátor plného pole sudoku v Pythonu. Funguje to v pohodě, jedno sudoku je vygenerovano cca za 7 ms. Funkci "tisk" ignoruj, ta pouze vypise sudoku na obrazovku.

Sudoku:

Autor skryl část textu. Zobrazit/skrýt!

Skrytý text:

Code:

import random


#vytvori seznam hodnot, ktere se nachazeji na stejnem radku
#jako cislo na souradnicich [x][y]

def row(y):
    radek = zadani[y]
    return radek

#vytvori seznam hodnot, ktere se nachazeji ve stejnem sloupci
#jako cislo na souradnicich [x][y]

def col(x):
    sloupec = []
    i = 0    
    while i<9:
        sloupec.append(zadani[i][x])
        i+=1
    return sloupec

#vytvori seznam hodnot, ktere se nachazeji ve stejnem ctverci
#(dle pravidel sudoku) jako cislo na souradnicich [x][y]

def box(x,y):
    #k=kolikaty horizontalni ctverec, l=kolikaty vertikalni ctverec
    k = x/3
    l = y/3
    ctverec=[]
    for x in range(l*3,l*3+3):
        for y in range(k*3,k*3+3):
            ctverec.append(zadani[x][y])
    return ctverec

def tisk():           
    
    print " _________________"     
    print "|%i %i %i|%i %i %i|%i %i %i|"%(zadani[0][0],zadani[0][1],zadani[0][2],zadani[0][3],zadani[0][4],zadani[0][5],zadani[0][6],zadani[0][7],zadani[0][8],) 
    print "|%i %i %i|%i %i %i|%i %i %i|"%(zadani[1][0],zadani[1][1],zadani[1][2],zadani[1][3],zadani[1][4],zadani[1][5],zadani[1][6],zadani[1][7],zadani[1][8],)     
    print "|%i %i %i|%i %i %i|%i %i %i|"%(zadani[2][0],zadani[2][1],zadani[2][2],zadani[2][3],zadani[2][4],zadani[2][5],zadani[2][6],zadani[2][7],zadani[2][8],) 
    print "|-----+-----+-----|" 
    print "|%i %i %i|%i %i %i|%i %i %i|"%(zadani[3][0],zadani[3][1],zadani[3][2],zadani[3][3],zadani[3][4],zadani[3][5],zadani[3][6],zadani[3][7],zadani[3][8],) 
    print "|%i %i %i|%i %i %i|%i %i %i|"%(zadani[4][0],zadani[4][1],zadani[4][2],zadani[4][3],zadani[4][4],zadani[4][5],zadani[4][6],zadani[4][7],zadani[4][8],)     
    print "|%i %i %i|%i %i %i|%i %i %i|"%(zadani[5][0],zadani[5][1],zadani[5][2],zadani[5][3],zadani[5][4],zadani[5][5],zadani[5][6],zadani[5][7],zadani[5][8],) 
    print "|-----+-----+-----|" 
    print "|%i %i %i|%i %i %i|%i %i %i|"%(zadani[6][0],zadani[6][1],zadani[6][2],zadani[6][3],zadani[6][4],zadani[6][5],zadani[6][6],zadani[6][7],zadani[6][8],) 
    print "|%i %i %i|%i %i %i|%i %i %i|"%(zadani[7][0],zadani[7][1],zadani[7][2],zadani[7][3],zadani[7][4],zadani[7][5],zadani[7][6],zadani[7][7],zadani[7][8],)     
    print "|%i %i %i|%i %i %i|%i %i %i|"%(zadani[8][0],zadani[8][1],zadani[8][2],zadani[8][3],zadani[8][4],zadani[8][5],zadani[8][6],zadani[8][7],zadani[8][8],) 
    print " _________________"


   
zadani=[[0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,0,0,0]]


historie = [[],[],[],[],[],[],[],[],[],
            [],[],[],[],[],[],[],[],[],
            [],[],[],[],[],[],[],[],[],
            [],[],[],[],[],[],[],[],[],
            [],[],[],[],[],[],[],[],[],
            [],[],[],[],[],[],[],[],[],
            [],[],[],[],[],[],[],[],[],
            [],[],[],[],[],[],[],[],[],
            [],[],[],[],[],[],[],[],[]]

#cislo bunky, ve ktere se nachazim. p tedy nabyva hodnot 0-80.   
 
p = 0   
while p < 81:        
                               
    #prepocet 
    x = p%9
    y = p/9
    zadani[y][x] = 0    
    kandidat=random.randint(1,9)
    
    #pokud byla pouzita vsechna cisla, historie pro danou bunku
    #se vycisti a vratime se o policko zpatky - tzv. backtracking    
    
    if len(historie[p]) == 9:
        historie[p] = []
        p -= 1
        continue
    
    #jestlize vygenerovane cislo uz bylo pro danou bunku pouzito,
    #vratime se na zacatek cislo a vygenerujeme dalsi    
   
     if kandidat in historie[p]:
        continue
    
    #Splnuje cislo podminky sudoku? Ne - pridame cislo do historie
    #                                     a vratime se na zacatek cyklu
    #                               Ano  - dosadime cislo do bunky, pridame
    #                                     do historie a posuneme se o 1 dopredu.
    
    if kandidat in row(y) or kandidat in col(x) or kandidat in box(x,y):
        historie[p].append(kandidat)
        continue
    zadani[y][x] = kandidat
    historie[p].append(kandidat)
    p += 1
    
tisk()

Matematické Fórum

#1 13. 11. 2012 12:08

Generator sudoku

#2 15. 11. 2012 14:12

Re: Generator sudoku

#3 25. 11. 2012 13:44 — Editoval mountdoom (25. 11. 2012 13:53)

Re: Generator sudoku

Code:

Zápatí