Implementation of Matrix Elimination and A*
Search Algorithm In Solving Sudoku Puzzle Game
Total View This Week14
Total View This Week14
Institusion
Universitas Katolik Soegijapranata
Author
Chan, Novi
Subject
005 Computer programming, programs & data
Datestamp
2016-01-27 02:17:34
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.
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.
Download
book
BibTex
Latex, Jabref
cloud_download
Original Resource
url resource Institution
