123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220 |
- #!/usr/bin/ruby
- # Author: Trizen
- # Date: 12 February 2024
- # https://github.com/trizen
- # Fast algorithm to solve a Sudoku puzzle (iterative solution).
- func is_valid(board, row, col, num) {
- # Check if the number is not present in the current row and column
- for i in ^9 {
- if ((board[row][i] == num) || (board[i][col] == num)) {
- return false
- }
- }
- # Check if the number is not present in the current 3x3 subgrid
- var (start_row, start_col) = (3*idiv(row, 3), 3*idiv(col, 3))
- for i in ^3, j in ^3 {
- if (board[start_row + i][start_col + j] == num) {
- return false
- }
- }
- return true
- }
- func find_empty_locations(board) {
- var locations = []
- # Find all empty positions (cells with 0)
- for i in ^9, j in ^9 {
- if (board[i][j] == 0) {
- locations << [i, j]
- }
- }
- return locations
- }
- func find_empty_location(board) {
- # Find an empty position (cell with 0)
- for i in ^9, j in ^9 {
- if (board[i][j] == 0) {
- return (i, j)
- }
- }
- return (nil, nil) # If the board is filled
- }
- func solve_sudoku_fallback(board) {
- var (row, col) = find_empty_location(board)
- if (!defined(row) && !defined(col)) {
- return true # Puzzle is solved
- }
- for num in (1..9) {
- if (is_valid(board, row, col, num)) {
- # Try placing the number
- board[row][col] = num
- # Recursively try to solve the rest of the puzzle
- if (__FUNC__(board)) {
- return true
- }
- # If placing the current number doesn't lead to a solution, backtrack
- board[row][col] = 0
- }
- }
- return false # No solution found
- }
- func solve_sudoku(board) {
- loop {
- var empty_locations = find_empty_locations(board) || break
- var found = false
- # Solve easy cases
- for i,j in empty_locations {
- var(count=0, value=0)
- for n in (1..9) {
- is_valid(board, i, j, n) || next
- break if (++count > 1)
- value = n
- }
- if (count == 1) {
- board[i][j] = value
- found ||= true
- }
- }
- next if found
- # Solve more complex cases
- var stats = []
- for i,j in empty_locations {
- stats[i][j] = (1..9 -> grep{|n| is_valid(board, i, j, n) })
- }
- var cols = []
- var rows = []
- var subgrid = []
- for i,j in empty_locations {
- stats[i][j].each {|v|
- cols[j][v] := 0 ++
- rows[i][v] := 0 ++
- subgrid[3*idiv(i,3)][3*idiv(j,3)][v] := 0 ++
- }
- }
- for i,j in empty_locations {
- stats[i][j].each {|v|
- if ((cols[j][v] == 1) ||
- (rows[i][v] == 1) ||
- (subgrid[3*idiv(i,3)][3*idiv(j,3)][v] == 1)
- ) {
- board[i][j] = v
- found ||= true
- }
- }
- }
- next if found
- # Give up and try brute-force
- solve_sudoku_fallback(board)
- return board
- }
- return board
- }
- # Example usage:
- # Define the Sudoku puzzle as a 9x9 list with 0 representing empty cells
- var sudoku_board = %n(
- 2 0 0 0 7 0 0 0 3
- 1 0 0 0 0 0 0 8 0
- 0 0 4 2 0 9 0 0 5
- 9 4 0 0 0 0 6 0 8
- 0 0 0 8 0 0 0 9 0
- 0 0 0 0 0 0 0 7 0
- 7 2 1 9 0 8 0 6 0
- 0 3 0 0 2 7 1 0 0
- 4 0 0 0 0 3 0 0 0
- ).slices(9)
- sudoku_board = %n(
- 0 0 0 8 0 1 0 0 0
- 0 0 0 0 0 0 0 4 3
- 5 0 0 0 0 0 0 0 0
- 0 0 0 0 7 0 8 0 0
- 0 0 0 0 0 0 1 0 0
- 0 2 0 0 3 0 0 0 0
- 6 0 0 0 0 0 0 7 5
- 0 0 3 4 0 0 0 0 0
- 0 0 0 2 0 0 6 0 0
- ).slices(9) if true
- sudoku_board = %n(
- 8 0 0 0 0 0 0 0 0
- 0 0 3 6 0 0 0 0 0
- 0 7 0 0 9 0 2 0 0
- 0 5 0 0 0 7 0 0 0
- 0 0 0 0 4 5 7 0 0
- 0 0 0 1 0 0 0 3 0
- 0 0 1 0 0 0 0 6 8
- 0 0 8 5 0 0 0 1 0
- 0 9 0 0 0 0 4 0 0
- ).slices(9) if false
- sudoku_board = %n(
- 0 0 1 0 6 0 0 5 9
- 0 0 0 0 0 3 0 2 0
- 0 6 0 0 8 0 0 0 0
- 4 0 0 0 0 0 5 0 0
- 0 2 0 0 0 0 0 0 0
- 0 7 0 2 0 0 4 8 0
- 8 0 0 0 0 0 9 0 5
- 7 0 0 6 0 9 0 3 0
- 0 0 5 0 0 0 0 4 0
- ).slices(9) if false
- func display_grid(grid) {
- for i in ^grid {
- print "#{grid[i]} "
- print " " if ( 3 -> divides(i+1))
- print "\n" if ( 9 -> divides(i+1))
- print "\n" if (27 -> divides(i+1))
- }
- }
- var solution = solve_sudoku(sudoku_board)
- if (solution) {
- display_grid(solution.flat)
- }
- else {
- warn "No unique solution exists."
- }
|