Semi-Team
GPU610/DPS915 | Student List | Group and Project Index | Student Resources | Glossary
Contents
Semi-Team
Team Members
- Michael Fainshtein, Research, Development, Presentation
Progress
Assignment 1
Rules to play Sudoku
Sudoku is a logic puzzle where a grid composed of mini grids is presented to the player to fill each cell with a number unique to its column, row and mini-grid.
Sudoku Backtrack Algorithm
Find row, col of an unassigned cell If there is none, return true For digits from 1 to 9 a) If there is no conflict for digit at row,col assign digit to row,col and recursively try fill in rest of grid b) If recursion successful, return true c) Else, remove digit and try another If all digits have been tried and nothing worked, return false
Sudoku Backtrack Function
/* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ bool SolveSudoku(int grid[N]) { int row, col; // If there is no unassigned location, we are done if (!FindUnassignedLocation(grid, row, col)) return true; // success! // consider digits 1 to 16 for (int num = 1; num <= n; num++) { // if looks promising if (isSafe(grid, row, col, num)) { // make tentative assignment grid[(row)+(col*n)] = num; // return, if success, yay! if (SolveSudoku(grid)) return true; // failure, unmake & try again grid[(row)+(col*n)] = UNASSIGNED; } } return false; // this triggers backtracking }
Source
http://www.geeksforgeeks.org/backtracking-set-7-suduku/