Development of an Android-Based Visual Sudoku Solver Using Contour Finding and Backtracking Algorithm

Abstract

This study developed an Android application that automatically solves Sudoku puzzle. An image of the Sudoku puzzle is either captured by the built-in camera or loaded directly from the media gallery. Contour finding algorithm and Hough transform would detect the game board. The givens (i.e. number that exist in a Sudoku board) are acquired by dividing the entire game board by 81 cells with the contour finding algorithm extracting the particular given. Identification is done using the Tesseract – Optical Character Recognition (OCR). Backtracking algorithm calculated the solution and displayed it back in the form of an image. After testing 30 Sudoku images, a 74.47% detection percentage and 13.09% branching factor with a Receiver Operating Characteristic - Area Under the Curve (AUC) of 0.684 was obtained when identifying the givens indicating that the system is effective.