Technologies: MATLAB
Skills & Methodologies: Linear Programming
GitHub Repository
Sudoku, the classic puzzle game, can be viewed as an optimization problem. The rules governing where numbers can be placed in each row, column, and block can be expressed as linear constraints. The Simplex algorithm can then be used to find a feasible solution. My implmentation accepts as input a 9x9 matrix representing a Sudoku game. If the game is valid then it outputs a 9x9 matrix representing the solution. However, if the game is invalid, that is if no feasible solution exists, then the program changes the minimum amount of numbers required to make the game the feasible and then outputs the solution. This alteration of infeasible games is acheived through the objective function which penalizes every alteration.