Last active
March 31, 2020 07:12
-
-
Save kristopherjohnson/81fd9d4bfe951690b74b to your computer and use it in GitHub Desktop.
Sudoku solver in TypeScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// A Sudoku puzzle is a 9x9 matrix of marks 1...9, with 0 denoting an empty square | |
class Sudoku | |
{ | |
constructor(public matrix: Array<Array<number>>) {} | |
// Return the value at the specified (row, column) | |
markAt(row: number, col: number): number { | |
return this.matrix[row][col] | |
} | |
// Display the contents of the board | |
print() { | |
for (var row = 0; row < 9; ++row) { | |
var rowString = "" | |
for (var col = 0; col < 9; ++col) { | |
var mark = this.markAt(row, col) | |
if (1 <= mark && mark <= 9) { | |
rowString = rowString + mark | |
} | |
else { | |
rowString = rowString + "." | |
} | |
} | |
console.log(rowString) | |
} | |
} | |
// Create a copy of a Sudoku with an additional mark | |
copyWithMark(mark: number, row: number, col: number): Sudoku { | |
var result = new Array<Array<number>>() | |
// Copy existing rows | |
for (var r = 0; r < 9; ++r) { | |
result[r] = this.matrix[r] | |
} | |
// Replace marked row | |
var newRow = new Array<number>() | |
for (var c = 0; c < 9; ++c) { | |
if (c == col) { | |
newRow[c] = mark | |
} | |
else { | |
newRow[c] = this.matrix[row][c] | |
} | |
} | |
result[row] = newRow | |
return new Sudoku(result) | |
} | |
} | |
// A (row, column) tuple | |
class RowCol | |
{ | |
constructor(public row: number, public col: number) {} | |
} | |
// Find a solution for a sudoku puzzle | |
// | |
// Returns null if there is no solution | |
function solveSudoku(s: Sudoku): Sudoku { | |
var emptySquare = findEmptySquare(s) | |
if (emptySquare != null) { | |
var row = emptySquare.row | |
var col = emptySquare.col | |
for (var mark = 1; mark <= 9; ++mark) { | |
if (canTryMark(mark, row, col, s)) { | |
var candidate = s.copyWithMark(mark, row, col) | |
var solution = solveSudoku(candidate) | |
if (solution != null) { | |
return solution | |
} | |
} | |
} | |
// No solution | |
return null | |
} | |
else { | |
// No empty squares, so it's solved | |
return s | |
} | |
} | |
// Find an empty square in a Sudoku board | |
// | |
// Returns (row, column), or null if there are no empty squares | |
function findEmptySquare(s: Sudoku): RowCol { | |
for (var row = 0; row < 9; ++row) | |
for (var col = 0; col < 9; ++col) | |
if (s.markAt(row, col) == 0) | |
return new RowCol(row, col) | |
return null | |
} | |
// Determine whether putting the specified mark at the specified square would violate uniqueness constrains | |
function canTryMark(mark: number, row: number, col: number, s: Sudoku): boolean { | |
return !doesSudokuContainMarkInRow(s, mark, row) | |
&& !doesSudokuContainMarkInColumn(s, mark, col) | |
&& !doesSudokuContainMarkIn3x3Box(s, mark, row, col) | |
} | |
// Determine whether a specified mark already exists in a specified row | |
function doesSudokuContainMarkInRow(s: Sudoku, mark: number, row: number): boolean { | |
for (var col = 0; col < 9; ++col) | |
if (s.markAt(row, col) == mark) | |
return true | |
return false | |
} | |
// Determine whether a specified mark already exists in a specified column | |
function doesSudokuContainMarkInColumn(s: Sudoku, mark: number, col: number): boolean { | |
for (var row = 0; row < 9; ++row) | |
if (s.markAt(row, col) == mark) | |
return true | |
return false | |
} | |
/// Determine whether a specified mark already exists in a specified 3x3 subgrid | |
function doesSudokuContainMarkIn3x3Box(s: Sudoku, mark: number, row: number, col: number): boolean { | |
var boxMinRow = Math.floor(row / 3) * 3 | |
var boxMaxRow = boxMinRow + 2 | |
var boxMinCol = Math.floor(col / 3) * 3 | |
var boxMaxCol = boxMinCol + 2 | |
for (var row = boxMinRow; row <= boxMaxRow; ++row) | |
for (var col = boxMinCol; col <= boxMaxCol; ++col) | |
if (s.markAt(row, col) == mark) | |
return true | |
return false | |
} | |
// Example puzzle from http://en.wikipedia.org/wiki/Sudoku | |
var example = new Sudoku([ | |
[5, 3, 0, 0, 7, 0, 0, 0, 0], | |
[6, 0, 0, 1, 9, 5, 0, 0, 0], | |
[0, 9, 8, 0, 0, 0, 0, 6, 0], | |
[8, 0, 0, 0, 6, 0, 0, 0, 3], | |
[4, 0, 0, 8, 0, 3, 0, 0, 1], | |
[7, 0, 0, 0, 2, 0, 0, 0, 6], | |
[0, 6, 0, 0, 0, 0, 2, 8, 0], | |
[0, 0, 0, 4, 1, 9, 0, 0, 5], | |
[0, 0, 0, 0, 8, 0, 0, 7, 0] | |
]) | |
console.log("Puzzle:") | |
example.print() | |
var solution = solveSudoku(example) | |
if (solution != null) { | |
console.log("\nSolution:") | |
solution.print() | |
} | |
else { | |
console.log("No solution") | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Equivalent code in Swift: https://gist.github.com/kristopherjohnson/c49448aad37e766b4fd1