20.500.12556/RUL-99496 Sestavljanje in reševanje igre Sudoku Constructing and solving of Sudoku V diplomski nalogi bomo predstavili reševanje in ustvarjanje uganke sudoku. Spoznali bomo osnovne gradnike vsake sudoku uganke. Obravnavali bomo problem natančnega pokritja množice in kako se sudoku uganka preslika na problem natančnega pokritja. Razložili bomo prevedbo zapisa sudoku uganke v računalniški zapis (matriko pokritja), nad katero se izvaja naš program. Pri reševanju sudokuja smo uporabili algoritem X, ki je implementiran v jeziku Java. Spoznali bomo drugi način implementacije algoritma X, metodo plesočih povezav, ki je žal nismo implementirali. Primerjali bomo oba načina reševanja sudoku mrež s pomočjo časovne in prostorske analize ter si podrobneje ogledali omejitve naše implementacije. Sledi predstavitev postopka sestavljanja poljubne sudoku mreže iz več sudokujev ter težave, s katerimi se srečamo, ko sestavljamo poljuben sudoku. Na koncu si bomo ogledali še primer vmesnika, ki nam omogoča sestavljanje poljubnih sudokujev. Za vmesnik smo uporabili tehnologiji HTML in javascript. The goal of the thesis is to study how to create and solve a sudoku puzzle. We will look into the individual components which every sudoku puzzle contains. Furthermore, we will take a closer look into the exact set cover problem and how sudoku puzzle can be represented as one. We will present how to represent a sudoku puzzle so that our program can use it for solving. Sudoku solver was created using "Algorithm X'', using Java programming language. We will get better acquainted with an alternative way to implement "Algorithm X'', the "Dancing Links'' method which unfortunately was not implemented. With the help of time and space complexity analysis we will compare both implementations and also have a closer look at the limitations of our implementation. After that, we will have a look at how to create a custom sudoku grid which consists of multiple other sudoku grids. We also mention problems which we can encounter during the creation. Lastly, a simple user interface proposal will be introduced, using HTML and javascript, which enables users to create any kind of sudoku they wish. Algoritem Java NP-polnost problem natančnega pokritja. Algorithm Java NP-completeness complete coverage problem. true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2018-01-29 12:10:02 2018-01-29 12:10:06 2022-08-24 16:55:12 0000-00-00 00:00:00 2018 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 20781 Bukovec_Tadej_-_Sestavljanje_in_resevanje_igre_Sudoku.pdf Bukovec_Tadej_-_Sestavljanje_in_resevanje_igre_Sudoku.pdf 1 1B3848DC4DBB07DAF54D4E21B00846F5 a018d103e3661387e60ed824ed052e8899a42480eb8d2fea2d1b10c39b91d1f7 94464752-a1b4-11eb-a523-00155dcfd717 20.500.12556/rul/5758426e-5a47-4108-a0f4-2cd9e152d5f0 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=108969 Fakulteta za računalništvo in informatiko 0 0 0