C++ Educational Content Creator | 20 years of Software Engineering experience distilled into digestible daily posts
Sunday common C++ interview problem: Sudoku solver. Given a sudoku puzzle as a std::vector<std::vector<char>>, where empty spaces are represented using a space, solve the puzzle. Sudoku rules: - each of the nine rows, columns and 3x3 boxes must contain all the digits 1..9 Solve it yourself: https://lnkd.in/epuCABUn Solution: https://lnkd.in/eb8auAU7 #cpp #cplusplus #coding #programming #dailybiteofcpp
Doing it in a decent language is easy... I did it in the worst language ever: JavaScript: https://github.com/LucidioK/sudoku
One of our assignments for the operating research course. https://github.com/bhattacharjee/mtu-decision-analytics-assignment/blob/main/assignment1/sudoku.py
For each 9-element square list missing numbers. For each missing number in that big square, list possible locations intersecting with rows and columns. If number has only one possible location then fix it to that location. If there is only one vacant space in big square, use for missing number. Walk through all big squares in whichever order, as many times until all fields have a value. When there is no more missing values, the puzzle is solved 😉
A few years ago, I had implemented a sudoku solver, with some techniques I use in real world sudoku puzzles. Basically this solver uses a possibility matrix to reduce each cells possible numbers. If all possibilities calculated, a recursive bruteforce function takes control to solve puzzle. https://github.com/devomer05/SudokuSolver
Thanks for this push-up to my new project idea 💡
I guess the best algorithm to solve this is dancing links which is a backtracking method with huge optimization. I had this problem as part of my interview for the company that I am working at now.