Implementation of Matrix Elimination and A* Search Algorithm In Solving Sudoku Puzzle Game

Chan, Novi (2008) Implementation of Matrix Elimination and A* Search Algorithm In Solving Sudoku Puzzle Game. Other thesis, Fakultas Ilmu Komputer, UNIKA Soegijapranata.

[img]
Preview
Text (COVER)
04.02.0048 Novi Chan COVER.pdf

Download (163kB) | Preview
[img] Text (BAB I)
04.02.0048 Novi Chan BAB I.pdf
Restricted to Registered users only

Download (141kB)
[img] Text (BAB II available document only in library of Soegijapranata Catholic University)
04.02.0048 Novi Chan BAB II.pdf
Restricted to Repository staff only

Download (121kB)
[img] Text (BAB III available document only in library of Soegijapranata Catholic University)
04.02.0048 Novi Chan BAB III.pdf
Restricted to Repository staff only

Download (112kB)
[img] Text (BAB IV available document only in library of Soegijapranata Catholic University)
04.02.0048 Novi Chan BAB IV.pdf
Restricted to Repository staff only

Download (124kB)
[img] Text (BAB V available document only in library of Soegijapranata Catholic University)
04.02.0048 Novi Chan BAB V.pdf
Restricted to Repository staff only

Download (474kB)
[img] Text (BAB VI)
04.02.0048 Novi Chan BAB VI.pdf
Restricted to Registered users only

Download (134kB)
[img]
Preview
Text (DAFTAR PUSTAKA)
04.02.0048 Novi Chan DAFTAR PUSTAKA.pdf

Download (106kB) | Preview
[img]
Preview
Text (LAMPIRAN)
04.02.0048 Novi Chan LAMPIRAN.pdf

Download (102kB) | Preview

Abstract

Sudoku is a puzzle game that could train people to think fast and carefully. It has simple rule to play, but it’s difficult to be solved. The puzzle contains matrix 9 x 9 and 9 sub matrix measure 3 x 3 that called sub grids. The goal of this game is filling all cells with number 1 to 9 where each row, column, and sub grid haven’t the same number. There are have several scopes in this program. This project just create for solving the sudoku problem. It just show the best one answer for one problem, although for some case, it have another answer. This project would be created using Java Programming. The layout of this project using GUI ( Graphical User Interface ) programming that contains board 9 x 9 where user can input the problem to solved with this sudoku solver. And some buttons with certain action, there are button save, solve it, reset, rule, and exit. A* ( A Star ) algorithm and user define object data structure will be used to solve the problem. By using A* algorithm, a puzzle game with many possibilities could be solved faster. As it only explores possibility with the biggest value, not explore per level like BFS or DFS and another blind search algorithm, also it’s no need much memory as BFS. Before using A* algorithm, the program would be eliminate the possible numbers with matrix elimination. Matrix elimination is a method to eliminate numbers in vertical, horizontal and sub grid. After using matrix elimination, A* is used heuristic function to get the biggest value to expand. The heuristic function that is used is Σsub grid + Σ horizontal + Σ vertical that has complete or open up. And then it will explore the biggest value with A* algorithm. In conclusion, Sudoku can be solved faster with combination of Matrix Elimination and A* Algorithm.

Item Type: Thesis (Other)
Subjects: 000 Computer Science, Information and General Works > 005 Computer programming, programs & data
Divisions: Faculty of Computer Science
Depositing User: Mr Ign. Setya Dwiana
Date Deposited: 27 Jan 2016 02:17
Last Modified: 27 Jan 2016 02:17
URI: http://repository.unika.ac.id/id/eprint/7471

Actions (login required)

View Item View Item