Ariel Safiya Taylor April 30, 2012 Robotics: Final Report
The objective of a sudoku puzzle is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid contain digits 1-9. The goal is to complete the puzzle without repeating any digits 1-9 in each row, column and 3×3 sub grid. The algorithm used for solving this puzzle is referred to as a backtracking algorithm and can be applied to other puzzles such crossword. The focus of this project is to apply this particular algorithm for the robot to correctly solve a given sudoku puzzle.
The procedure for the backtracking algorithm is quite simple. The algorithm basically works by making a choice, if it works then proceed to next problem, else repeat the first step by using an alternative value. Some of the cells in the puzzle can have more than one possible value so it is best to keep track in case the first one does not work. As you continue to fill in values for other rows and columns, the possibility of certain can change and reduce the amount of backtracking needed to complete the puzzle. This procedure is very similar to trial-and error in that they both try particular values until it gives the preferred results.
First, I created a set of movements for the robot to follow to navigate around the grid. It uses a 4-point connectivity to move around between the individual cells. Next, create a 2-D array that represents the puzzle and its values. The empty cells of the puzzle are represented by the value of 0 so that the robot can identify which cells to add digits to. From here, the backtracking algorithm can be applied so that the robot can determine missing values based on the given digits and the location of the empty cells with value of 0. All possible values can be stored in an array in case it needs to go back and change any digits. The backtracking algorithm first looked at individual rows and compared the missing values to the set values. The same approach was used in determining values for the individual columns and the sub grids.
After running the program, the robot should navigate to empty cells of puzzle and display the corresponding digit for that cell until it has completed the entire puzzle. The starting cell is located at (0,0) and ends at (9,9) of the grid. Unfortunately I could not demonstrate these results due to technical difficulties. My code was corrupted by a virus and I could retrieve the final code I was using to produce the desired results.
The use of backtracking algorithm in solving sudoku puzzles makes it possible to complete even the most difficult puzzles. It shows how trial and error can be implemented and used to get the optimal results. This type of puzzle requires simple logic and can be enjoyable once you understand the rules. The difficulty level depends primarily on how many digits are predefined. It is a great way to stimulate your brain and apply thinking skills. In general, people of all ages can take pleasure in solving sudoku, even robots.
“Sudoku Algorithms.” Wikipedia. Wikimedia Foundation, 04 Apr. 2012. Web. 11 Apr. 2012. <http://en.wikipedia.org/wiki/Sudoku_algorithms>.
“SUDOKU Solver.” BOtskOOl. Web. 16 Apr. 2012. <http://www.botskool.com/programming-tutorials/cpp-tutorials/sudoku>.