Sudoku
Publish date: Sep 27, 2021
TL;DR
I’ve implemented a simple recursive algorithm to solve Sudoku puzzles and the results are here here.
The Idea
After watching the video in the Computerphile youtube channel about recursive algorithms that solves a Sudoku puzzle, I’ve decided to implement the same solution by myself.
A Problem to Test the Implementation
Following the video, I’ve tried the same puzzle in the video.
#!/usr/bin/env python
test_grid = [
[ 0, 0, 4, 0, 0, 0, 0, 6, 7 ],
[ 3, 0, 0, 4, 7, 0, 0, 0, 5 ],
[ 1, 5, 0, 8, 2, 0, 0, 0, 3 ],
[ 0, 0, 6, 0, 0, 0, 0, 3, 1 ],
[ 8, 0, 2, 1, 0, 5, 6, 0, 4 ],
[ 4, 1, 0, 0, 0, 0, 9, 0, 0 ],
[ 7, 0, 0, 0, 8, 0, 0, 4, 6 ],
[ 6, 0, 0, 0, 1, 2, 0, 0, 0 ],
[ 9, 3, 0, 0, 0, 0, 7, 1, 0 ],
]When its working, I can test if the algorithm is good by trying a harder problem.
#!/usr/bin/env python
grid = [
[ 0, 0, 2, 0, 0, 4, 0, 0, 0 ],
[ 0, 7, 0, 0, 0, 2, 0, 0, 0 ],
[ 0, 0, 6, 3, 0, 0, 0, 8, 0 ],
[ 0, 9, 0, 0, 0, 0, 0, 0, 0 ],
[ 5, 2, 7, 9, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 8, 0, 4, 0 ],
[ 0, 0, 0, 0, 0, 0, 4, 0, 5 ],
[ 0, 4, 0, 0, 0, 1, 0, 6, 0 ],
[ 0, 0, 1, 0, 7, 0, 9, 0, 0 ],
];Solutions
Following the videos idea, I’ve implemented the first version of the solution in python.
Python
This solution was written to be efficient, there are room for improvement.
Implementation
#!/usr/bin/env python
from numpy import matrix
test_grid = [
[ 0, 0, 4, 0, 0, 0, 0, 6, 7 ],
[ 3, 0, 0, 4, 7, 0, 0, 0, 5 ],
[ 1, 5, 0, 8, 2, 0, 0, 0, 3 ],
[ 0, 0, 6, 0, 0, 0, 0, 3, 1 ],
[ 8, 0, 2, 1, 0, 5, 6, 0, 4 ],
[ 4, 1, 0, 0, 0, 0, 9, 0, 0 ],
[ 7, 0, 0, 0, 8, 0, 0, 4, 6 ],
[ 6, 0, 0, 0, 1, 2, 0, 0, 0 ],
[ 9, 3, 0, 0, 0, 0, 7, 1, 0 ],
]
grid = [
[ 0, 0, 2, 0, 0, 4, 0, 0, 0 ],
[ 0, 7, 0, 0, 0, 2, 0, 0, 0 ],
[ 0, 0, 6, 3, 0, 0, 0, 8, 0 ],
[ 0, 9, 0, 0, 0, 0, 0, 0, 0 ],
[ 5, 2, 7, 9, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 8, 0, 4, 0 ],
[ 0, 0, 0, 0, 0, 0, 4, 0, 5 ],
[ 0, 4, 0, 0, 0, 1, 0, 6, 0 ],
[ 0, 0, 1, 0, 7, 0, 9, 0, 0 ],
];
def found_in_row(row, n):
""" (int, int) => boolean
Takes a row and a number and returns if the number can be placed in this row in the grid
>>> found_in_row(0, 2)
False
>>> found_in_row(0, 4)
True
"""
for column in range(0, 9):
if grid[row][column] == n:
return True
return False
def found_in_column(column, n):
""" (int, int) => boolean
Takes a column and a number and returns if the number can be placed in this column in the grid
>> found_in_column(0, 2)
False
>>> found_in_column(0, 4)
True
"""
for row in range(0, 9):
if grid[row][column] == n:
return True
return False
def found_in_subsquare(row, column, n):
""" (int, int) => boolean
Takes a row, a column and a number and returns if the number can be placed in this 3x3 subsquare in the grid
>>> found_in_subsquare(4, 4, 2)
False
>>> found_in_subsquare(4, 4, 1)
True
>>> found_in_subsquare(3, 3, 5)
True
>>> found_in_subsquare(3, 3, 8)
False
"""
ss_row = row // 3
ss_column = column // 3
for s_row in range (0, 3):
for s_column in range(0, 3):
if grid[3 * ss_row + s_row][3 * ss_column + s_column] == n:
return True
return False
def is_possible(row, column, n):
""" (int, int) => boolean
Takes a row, a column and a number and returns if the number can be placed in this 3x3 subsquare in the grid
>>> is_possible(4, 4, 3)
True
>>> is_possible(4, 4, 1)
False
>>> is_possible(4, 4, 9)
True
>>> is_possible(4, 4, 8)
False
"""
if found_in_row(row, n):
return False
if found_in_column(column, n):
return False
if found_in_subsquare(row, column, n):
return False
return True
def solve():
global grid
for row in range(0, 9):
for column in range(0, 9):
if grid[row][column] == 0:
for n in range(1, 10):
if is_possible(row, column, n):
grid[row][column] = n
solve()
grid[row][column] = 0
return
print(matrix(grid))
if __name__ == "__main__":
import doctest
tmp_grid = grid
grid = test_grid
doctest.testmod()
grid = tmp_grid
solve()Execution Time
time ./index.py
[[3 8 2 6 9 4 1 5 7]
[4 7 5 8 1 2 3 9 6]
[9 1 6 3 5 7 2 8 4]
[8 9 4 1 3 5 6 7 2]
[5 2 7 9 4 6 8 3 1]
[1 6 3 7 2 8 5 4 9]
[7 3 8 2 6 9 4 1 5]
[2 4 9 5 8 1 7 6 3]
[6 5 1 4 7 3 9 2 8]]
58.032 secsC++
Here I wanted to know what is possible using this algorithm, I’m looking for the fastest language I can use. I choose C++.
Implementation
#include <iostream>
#include <cmath>
#include <assert.h>
using namespace std;
int testGrid[9][9] = {
{ 0, 0, 4, 0, 0, 0, 0, 6, 7 },
{ 3, 0, 0, 4, 7, 0, 0, 0, 5 },
{ 1, 5, 0, 8, 2, 0, 0, 0, 3 },
{ 0, 0, 6, 0, 0, 0, 0, 3, 1 },
{ 8, 0, 2, 1, 0, 5, 6, 0, 4 },
{ 4, 1, 0, 0, 0, 0, 9, 0, 0 },
{ 7, 0, 0, 0, 8, 0, 0, 4, 6 },
{ 6, 0, 0, 0, 1, 2, 0, 0, 0 },
{ 9, 3, 0, 0, 0, 0, 7, 1, 0 }
};
int grid[9][9] = {
{ 0, 0, 2, 0, 0, 4, 0, 0, 0 },
{ 0, 7, 0, 0, 0, 2, 0, 0, 0 },
{ 0, 0, 6, 3, 0, 0, 0, 8, 0 },
{ 0, 9, 0, 0, 0, 0, 0, 0, 0 },
{ 5, 2, 7, 9, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 8, 0, 4, 0 },
{ 0, 0, 0, 0, 0, 0, 4, 0, 5 },
{ 0, 4, 0, 0, 0, 1, 0, 6, 0 },
{ 0, 0, 1, 0, 7, 0, 9, 0, 0 }
};
bool foundInRow(int row, int number)
{
for (int column = 0; column < 9; column++)
if (grid[row][column] == number) return true;
return false;
}
bool foundInColumn(int column, int number)
{
for (int row = 0; row < 9; row++)
if (grid[row][column] == number) return true;
return false;
}
bool foundInSubsquare(int row, int column, int number)
{
int ssRow = floor(row / 3);
int ssColumn = floor(column / 3);
for (int r = 0; r < 3; r++)
for (int c = 0; c < 3; c++)
if (grid[ssRow * 3 + r][ssColumn * 3 + c] == number) return true;
return false;
}
bool isPossible(int row, int column, int number)
{
if (foundInRow(row, number))
{
return false;
}
if (foundInColumn(column, number))
{
return false;
}
if (foundInSubsquare(row, column, number))
{
return false;
}
return true;
}
void printGrid()
{
for(int row = 0; row < 9; row++)
{
cout << "[ ";
for(int column = 0; column < 9; column++)
{
cout << grid[row][column] << " ";
}
cout << "]" << endl;
}
}
void test()
{
int tempGrid[9][9];
copy(&grid[0][0], &grid[0][0] + 81, &tempGrid[0][0]);
copy(&testGrid[0][0], &testGrid[0][0] + 81, &grid[0][0]);
assert(foundInRow(0, 2)==false);
assert(foundInRow(0, 4)==true);
assert(foundInColumn(0, 2)==false);
assert(foundInColumn(0, 4)==true);
assert(foundInSubsquare(4, 4, 2)==false);
assert(foundInSubsquare(4, 4, 1)==true);
assert(foundInSubsquare(3, 3, 5)==true);
assert(foundInSubsquare(3, 3, 8)==false);
assert(isPossible(4, 4, 3)==true);
assert(isPossible(4, 4, 1)==false);
assert(isPossible(4, 4, 9)==true);
assert(isPossible(4, 4, 8)==false);
copy(&tempGrid[0][0], &tempGrid[0][0] + 81, &grid[0][0]);
}
void solve()
{
for(int row = 0; row < 9; row++)
for(int column = 0; column < 9; column++)
if(grid[row][column] == 0)
{
for(int number = 1; number < 10; number++)
if(isPossible(row, column, number))
{
grid[row][column] = number;
solve();
grid[row][column] = 0;
}
return;
}
printGrid();
}
int main(int argc, char *argv[])
{
test();
solve();
return 0;
}
Execution Time
g++ main.cpp -o main -O3 && time ./main
[ 3 8 2 6 9 4 1 5 7 ]
[ 4 7 5 8 1 2 3 9 6 ]
[ 9 1 6 3 5 7 2 8 4 ]
[ 8 9 4 1 3 5 6 7 2 ]
[ 5 2 7 9 4 6 8 3 1 ]
[ 1 6 3 7 2 8 5 4 9 ]
[ 7 3 8 2 6 9 4 1 5 ]
[ 2 4 9 5 8 1 7 6 3 ]
[ 6 5 1 4 7 3 9 2 8 ]
0.281 secsWithout optimizations:
g++ main.cpp -o main && time ./main
[ 3 8 2 6 9 4 1 5 7 ]
[ 4 7 5 8 1 2 3 9 6 ]
[ 9 1 6 3 5 7 2 8 4 ]
[ 8 9 4 1 3 5 6 7 2 ]
[ 5 2 7 9 4 6 8 3 1 ]
[ 1 6 3 7 2 8 5 4 9 ]
[ 7 3 8 2 6 9 4 1 5 ]
[ 2 4 9 5 8 1 7 6 3 ]
[ 6 5 1 4 7 3 9 2 8 ]
1.307 secsRust
Another language designed for high performance. I was curious about what it can do.
Implementation
fn print_grid(grid: [[u8; 9]; 9]) -> () {
for row in 0..9 {
print!("[ ");
for column in 0..9 {
print!("{} ", grid[row][column]);
}
println!("]");
}
}
fn found_in_row(grid: [[u8; 9]; 9], row: usize, number: u8) -> bool {
for column in 0..9 {
if grid[row][column] == number {
return true;
}
}
return false;
}
fn found_in_column(grid: [[u8; 9]; 9], column: usize, number: u8) -> bool {
for row in 0..9 {
if grid[row][column] == number {
return true;
}
}
return false;
}
fn found_in_subsquare(grid: [[u8; 9]; 9], row: usize, column: usize, number: u8) -> bool {
let ss_row: usize = row / 3;
let ss_column: usize = column / 3;
for r in 0..3 {
for c in 0..3 {
if grid[ss_row * 3 + r][ss_column * 3 + c] == number {
return true;
}
}
}
return false;
}
fn is_possible(grid: [[u8; 9]; 9], row: usize, column: usize, number: u8) -> bool {
if found_in_row(grid, row, number) {
return false;
}
if found_in_column(grid, column, number) {
return false;
}
if found_in_subsquare(grid, row, column, number) {
return false;
}
return true;
}
fn solve(mut grid: [[u8; 9]; 9]) -> [[u8; 9]; 9] {
for row in 0..9 {
for column in 0..9 {
if grid[row][column] == 0 {
for number in 1..10 {
if is_possible(grid, row, column, number) {
grid[row][column] = number;
grid = solve(grid);
grid[row][column] = 0;
}
}
return grid;
}
}
}
print_grid(grid);
return grid;
}
fn main() {
let test: bool = true;
if test {
run_tests();
}
let grid: [[u8; 9]; 9] = [
[ 0, 0, 2, 0, 0, 4, 0, 0, 0 ],
[ 0, 7, 0, 0, 0, 2, 0, 0, 0 ],
[ 0, 0, 6, 3, 0, 0, 0, 8, 0 ],
[ 0, 9, 0, 0, 0, 0, 0, 0, 0 ],
[ 5, 2, 7, 9, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 8, 0, 4, 0 ],
[ 0, 0, 0, 0, 0, 0, 4, 0, 5 ],
[ 0, 4, 0, 0, 0, 1, 0, 6, 0 ],
[ 0, 0, 1, 0, 7, 0, 9, 0, 0 ]
];
solve(grid);
}
fn run_tests() -> () {
let test_grid: [[u8; 9]; 9] = [
[ 0, 0, 4, 0, 0, 0, 0, 6, 7 ],
[ 3, 0, 0, 4, 7, 0, 0, 0, 5 ],
[ 1, 5, 0, 8, 2, 0, 0, 0, 3 ],
[ 0, 0, 6, 0, 0, 0, 0, 3, 1 ],
[ 8, 0, 2, 1, 0, 5, 6, 0, 4 ],
[ 4, 1, 0, 0, 0, 0, 9, 0, 0 ],
[ 7, 0, 0, 0, 8, 0, 0, 4, 6 ],
[ 6, 0, 0, 0, 1, 2, 0, 0, 0 ],
[ 9, 3, 0, 0, 0, 0, 7, 1, 0 ],
];
println!("Running tests:");
test_found_in_row(test_grid);
test_found_in_column(test_grid);
test_found_in_subsquare(test_grid);
println!("ok");
}
fn test_found_in_row(grid: [[u8; 9]; 9]) -> () {
test_found_in_row_instance(grid, 0, 1, false);
test_found_in_row_instance(grid, 0, 4, true);
test_found_in_row_instance(grid, 8, 5, false);
test_found_in_row_instance(grid, 8, 1, true);
}
fn test_found_in_column(grid: [[u8; 9]; 9]){
test_found_in_column_instance(grid, 0, 1, true);
test_found_in_column_instance(grid, 0, 3, true);
test_found_in_column_instance(grid, 0, 4, true);
test_found_in_column_instance(grid, 0, 6, true);
test_found_in_column_instance(grid, 0, 7, true);
test_found_in_column_instance(grid, 0, 8, true);
test_found_in_column_instance(grid, 0, 9, true);
test_found_in_column_instance(grid, 0, 2, false);
test_found_in_column_instance(grid, 0, 5, false);
test_found_in_column_instance(grid, 8, 5, true);
test_found_in_column_instance(grid, 8, 2, false);
}
fn test_found_in_subsquare(grid: [[u8; 9]; 9]) -> () {
test_found_in_subsquare_instance(grid, 0, 0, 1, true);
test_found_in_subsquare_instance(grid, 0, 0, 4, true);
test_found_in_subsquare_instance(grid, 0, 0, 6, false);
}
fn test_found_in_row_instance(grid: [[u8; 9]; 9], row: usize, number: u8, expect: bool) -> () {
if found_in_row(grid, row, number) != expect {
print!("F");
panic!("found_in_row failed for {}, {}", row, number)
} else {
print!(".")
}
}
fn test_found_in_column_instance(grid: [[u8; 9]; 9], column: usize, number: u8, expect: bool) -> () {
if found_in_column(grid, column, number) != expect {
print!("F");
panic!("found_in_column failed for {}, {}", column, number);
} else {
print!(".")
}
}
fn test_found_in_subsquare_instance(grid: [[u8; 9]; 9], row: usize, column: usize, number: u8, expect: bool) -> () {
if found_in_subsquare(grid, row, column, number) != expect {
print!("F");
panic!("found_in_subsquare failed for {}, {}, {}", row, column, number);
} else {
print!(".")
}
}
Execution Time
cargo build --release && time cargo run --release
Finished release [optimized] target(s) in 0.01s
Finished release [optimized] target(s) in 0.00s
Running `target/release/sudoku`
Running tests:
..................ok
[ 3 8 2 6 9 4 1 5 7 ]
[ 4 7 5 8 1 2 3 9 6 ]
[ 9 1 6 3 5 7 2 8 4 ]
[ 8 9 4 1 3 5 6 7 2 ]
[ 5 2 7 9 4 6 8 3 1 ]
[ 1 6 3 7 2 8 5 4 9 ]
[ 7 3 8 2 6 9 4 1 5 ]
[ 2 4 9 5 8 1 7 6 3 ]
[ 6 5 1 4 7 3 9 2 8 ]
0.605 secsWithout compiler optimizations:
cargo build && time cargo run
Finished dev [unoptimized + debuginfo] target(s) in 0.00s
Finished dev [unoptimized + debuginfo] target(s) in 0.00s
Running `target/debug/sudoku`
Running tests:
..................ok
[ 3 8 2 6 9 4 1 5 7 ]
[ 4 7 5 8 1 2 3 9 6 ]
[ 9 1 6 3 5 7 2 8 4 ]
[ 8 9 4 1 3 5 6 7 2 ]
[ 5 2 7 9 4 6 8 3 1 ]
[ 1 6 3 7 2 8 5 4 9 ]
[ 7 3 8 2 6 9 4 1 5 ]
[ 2 4 9 5 8 1 7 6 3 ]
[ 6 5 1 4 7 3 9 2 8 ]
13.954 secsC#
Is a language I use often. The performance did not impressed me.
Implementation
using System;
using System.IO;
using System.Threading.Tasks;
namespace ToyCSharp {
class Sudoku {
public static int[][] grid = new int[][]
{
new int[]{ 0, 0, 2, 0, 0, 4, 0, 0, 0 },
new int[]{ 0, 7, 0, 0, 0, 2, 0, 0, 0 },
new int[]{ 0, 0, 6, 3, 0, 0, 0, 8, 0 },
new int[]{ 0, 9, 0, 0, 0, 0, 0, 0, 0 },
new int[]{ 5, 2, 7, 9, 0, 0, 0, 0, 0 },
new int[]{ 0, 0, 0, 0, 0, 8, 0, 4, 0 },
new int[]{ 0, 0, 0, 0, 0, 0, 4, 0, 5 },
new int[]{ 0, 4, 0, 0, 0, 1, 0, 6, 0 },
new int[]{ 0, 0, 1, 0, 7, 0, 9, 0, 0 }
};
[STAThread]
public static void Main(string[] args)
{
Solve();
}
public static bool FoundInRow(int row, int number)
{
for(int column = 0; column < 9; column++)
{
if (grid[row][column] == number)
return true;
}
return false;
}
public static bool FoundInColumn(
int column,
int number
)
{
for(int row = 0; row < 9; row++)
{
if (grid[row][column] == number)
return true;
}
return false;
}
public static bool FoundInSubsquare(int row, int column, int number)
{
int ssRow = (int) Math.Floor((double) row / 3);
int ssColumn = (int) Math.Floor((double)column / 3);
for(int r = 0; r < 3; r++)
for (int c = 0; c < 3; c++)
if (grid[ssRow * 3 + r][ssColumn * 3 + c] == number) return true;
return false;
}
public static bool IsPossible(int row, int column, int number)
{
if (FoundInRow(row, number)) return false;
if (FoundInColumn(column, number)) return false;
if (FoundInSubsquare(row, column, number)) return false;
return true;
}
public static void PrintGrid()
{
for(int row = 0; row < 9; row++)
{
Console.Write("[ ");
for(int column = 0; column < 9; column++)
{
Console.Write($"{grid[row][column]} ");
}
Console.Write("]\n");
}
}
public static void Solve()
{
for(var row = 0; row < 9; row++)
{
for(var column = 0; column < 9; column ++)
{
if (grid[row][column] == 0)
{
for(var number = 1; number < 10; number++)
{
if(IsPossible(row, column, number))
{
grid[row][column] = number;
Solve();
grid[row][column] = 0;
}
}
return;
}
}
}
PrintGrid();
}
}
}
Execution Time
/usr/bin/csc /optimize /out:sudoku *.cs && chmod 755 sudoku && time ./sudoku
Microsoft (R) Visual C# Compiler version 3.6.0-4.20224.5 (ec77c100)
Copyright (C) Microsoft Corporation. All rights reserved.
Wrong type argument: stringp, 755
[ 3 8 2 6 9 4 1 5 7 ]
[ 4 7 5 8 1 2 3 9 6 ]
[ 9 1 6 3 5 7 2 8 4 ]
[ 8 9 4 1 3 5 6 7 2 ]
[ 5 2 7 9 4 6 8 3 1 ]
[ 1 6 3 7 2 8 5 4 9 ]
[ 7 3 8 2 6 9 4 1 5 ]
[ 2 4 9 5 8 1 7 6 3 ]
[ 6 5 1 4 7 3 9 2 8 ]
1.506 secsTurning off optimizations:
/usr/bin/csc /out:sudoku *.cs && chmod 755 sudoku && time ./sudoku
Microsoft (R) Visual C# Compiler version 3.6.0-4.20224.5 (ec77c100)
Copyright (C) Microsoft Corporation. All rights reserved.
[ 3 8 2 6 9 4 1 5 7 ]
[ 4 7 5 8 1 2 3 9 6 ]
[ 9 1 6 3 5 7 2 8 4 ]
[ 8 9 4 1 3 5 6 7 2 ]
[ 5 2 7 9 4 6 8 3 1 ]
[ 1 6 3 7 2 8 5 4 9 ]
[ 7 3 8 2 6 9 4 1 5 ]
[ 2 4 9 5 8 1 7 6 3 ]
[ 6 5 1 4 7 3 9 2 8 ]
1.798 secsGolang
Another very nice language, Golang is well know to have a good concurrency model. I don’t believe this is a place to this language shine.
Implementation
module sudoku
go 1.16
package main
import (
"fmt"
"math"
)
var testGrid [9][9]int = [9][9]int {
{ 0, 0, 4, 0, 0, 0, 0, 6, 7 },
{ 3, 0, 0, 4, 7, 0, 0, 0, 5 },
{ 1, 5, 0, 8, 2, 0, 0, 0, 3 },
{ 0, 0, 6, 0, 0, 0, 0, 3, 1 },
{ 8, 0, 2, 1, 0, 5, 6, 0, 4 },
{ 4, 1, 0, 0, 0, 0, 9, 0, 0 },
{ 7, 0, 0, 0, 8, 0, 0, 4, 6 },
{ 6, 0, 0, 0, 1, 2, 0, 0, 0 },
{ 9, 3, 0, 0, 0, 0, 7, 1, 0 },
}
var grid [9][9]int = [9][9]int {
{ 0, 0, 2, 0, 0, 4, 0, 0, 0 },
{ 0, 7, 0, 0, 0, 2, 0, 0, 0 },
{ 0, 0, 6, 3, 0, 0, 0, 8, 0 },
{ 0, 9, 0, 0, 0, 0, 0, 0, 0 },
{ 5, 2, 7, 9, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 8, 0, 4, 0 },
{ 0, 0, 0, 0, 0, 0, 4, 0, 5 },
{ 0, 4, 0, 0, 0, 1, 0, 6, 0 },
{ 0, 0, 1, 0, 7, 0, 9, 0, 0 },
}
func printGrid() {
for row := 0; row < 9; row++ {
fmt.Print("[ ")
for column := 0; column < 9; column++ {
fmt.Printf("%d ", grid[row][column])
}
fmt.Print("]\n")
}
}
func foundInRow(row int, number int) bool {
for column := 0; column < 9; column++ {
if (grid[row][column] == number){
return true
}
}
return false
}
func foundInColumn(column int, number int) bool {
for row := 0; row < 9; row++ {
if (grid[row][column] == number){
return true
}
}
return false
}
func foundInSubsquare(row int, column int, number int) bool {
ssRow := int(math.Floor(float64(row) / 3))
ssColumn := int(math.Floor(float64(column) / 3))
for r := 0; r < 3; r++ {
for c := 0; c < 3; c++ {
if (grid[ssRow * 3 + r][ssColumn * 3 + c] == number){
return true
}
}
}
return false
}
func isPossible(row int, column int, number int) bool {
if (foundInRow(row, number)) {
return false
}
if (foundInColumn(column, number)) {
return false
}
if (foundInSubsquare(row, column, number)) {
return false
}
return true
}
func solve() {
for row := 0; row < 9; row++ {
for column := 0; column < 9; column++ {
if (grid[row][column] == 0){
for number := 1; number < 10; number++ {
if (isPossible(row, column, number)){
grid[row][column] = number
solve()
grid[row][column] = 0
}
}
return
}
}
}
printGrid()
}
func main() {
solve()
}
package main
import (
"testing"
)
func TestFoundInRow(t *testing.T) {
rowCase(t, 0, 2, false)
rowCase(t, 0, 4, true)
rowCase(t, 0, 8, false)
}
func TestFoundInColumn(t *testing.T) {
columnCase(t, 0, 2, false)
columnCase(t, 1, 2, false)
columnCase(t, 0, 4, true)
columnCase(t, 1, 8, false)
}
func TestFoundInSubsquares(t *testing.T) {
subsquareCase(t, 0, 1, 2, false)
subsquareCase(t, 4, 4, 2, false)
subsquareCase(t, 4, 4, 1, true)
subsquareCase(t, 3, 3, 5, true)
subsquareCase(t, 3, 3, 8, false)
subsquareCase(t, 0, 1, 8, false)
}
func TestIsPossible(t *testing.T) {
isPossibleCase(t, 4, 4, 3, true)
isPossibleCase(t, 4, 4, 1, false)
isPossibleCase(t, 4, 4, 9, true)
isPossibleCase(t, 4, 4, 8, false)
isPossibleCase(t, 0, 1, 8, true)
}
func subsquareCase(t *testing.T, row, column, number int, want bool) {
got := foundInSubsquare(row, column, number)
AssertBoolean(t, got, want)
}
func rowCase(t *testing.T, row, number int, want bool) {
got := foundInRow(row, number)
AssertBoolean(t, got, want)
}
func columnCase(t *testing.T, column, number int, want bool) {
got := foundInColumn(column, number)
AssertBoolean(t, got, want)
}
func isPossibleCase(t *testing.T, row, column, number int, want bool) {
got := isPossible(row, column, number)
AssertBoolean(t, got, want)
}
func AssertInteger(t *testing.T, got, want int) {
t.Helper()
if got != want {
t.Errorf("got %d want %d", got, want)
}
}
func AssertBoolean(t *testing.T, got, want bool) {
t.Helper()
if got != want {
t.Errorf("got %t want %t", got, want)
}
}
Execution Time
go build && time ./sudoku
[ 3 8 2 6 9 4 1 5 7 ]
[ 4 7 5 8 1 2 3 9 6 ]
[ 9 1 6 3 5 7 2 8 4 ]
[ 8 9 4 1 3 5 6 7 2 ]
[ 5 2 7 9 4 6 8 3 1 ]
[ 1 6 3 7 2 8 5 4 9 ]
[ 7 3 8 2 6 9 4 1 5 ]
[ 2 4 9 5 8 1 7 6 3 ]
[ 6 5 1 4 7 3 9 2 8 ]
0.644 secsRuby
Ruby was one of my first programming languages. I seized the opportunity to touch it again after a long time.
Implementation
Using the conventional directory structure, I’ve used rspec for testing. The rpec library is also the only dependency in the Gemfile.
Estrutura do projeto
tree
.
├── Gemfile
├── Gemfile.lock
├── lib
│ └── sudoku.rb
├── Makefile
├── spec
│ ├── spec_helper.rb
│ └── spec_sudoku.rb
└── sudoku.rbEntrypoint
./sudoku.rb
(require './lib/sudoku')
sudoku = Sudoku.new
hardest_problem = [
[ 0, 0, 2, 0, 0, 4, 0, 0, 0 ],
[ 0, 7, 0, 0, 0, 2, 0, 0, 0 ],
[ 0, 0, 6, 3, 0, 0, 0, 8, 0 ],
[ 0, 9, 0, 0, 0, 0, 0, 0, 0 ],
[ 5, 2, 7, 9, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 8, 0, 4, 0 ],
[ 0, 0, 0, 0, 0, 0, 4, 0, 5 ],
[ 0, 4, 0, 0, 0, 1, 0, 6, 0 ],
[ 0, 0, 1, 0, 7, 0, 9, 0, 0 ],
]
sudoku.set_grid(hardest_problem)
sudoku.solve()Solution
./lib/sudoku.rb
class Sudoku
def initialize()
@grid = [
[ 0, 0, 4, 0, 0, 0, 0, 6, 7 ],
[ 3, 0, 0, 4, 7, 0, 0, 0, 5 ],
[ 1, 5, 0, 8, 2, 0, 0, 0, 3 ],
[ 0, 0, 6, 0, 0, 0, 0, 3, 1 ],
[ 8, 0, 2, 1, 0, 5, 6, 0, 4 ],
[ 4, 1, 0, 0, 0, 0, 9, 0, 0 ],
[ 7, 0, 0, 0, 8, 0, 0, 4, 6 ],
[ 6, 0, 0, 0, 1, 2, 0, 0, 0 ],
[ 9, 3, 0, 0, 0, 0, 7, 1, 0 ],
]
end
def set_grid(grid)
@grid = grid
end
def found_in_row(row, number)
return @grid[row].include?(number)
end
def found_in_column(column, number)
return @grid.transpose[column].include?(number)
end
def found_in_subsquare(row, column, number)
return @grid.drop(3 * (row/3)).take(3).transpose.drop(3 * (column/3)).take(3).flatten.include?(number)
end
def is_possible(row, column, number)
if found_in_row(row, number)
return false
end
if found_in_column(column, number)
return false
end
if found_in_subsquare(row, column, number)
return false
end
return true
end
def print_grid()
for row in (0..8)
print("[ ")
for column in (0..8)
print("#{@grid[row][column]} ")
end
print("]\n")
end
end
def solve()
for row in (0..8)
for column in (0..8)
if(@grid[row][column] == 0)
for number in (1..9)
if is_possible(row, column, number)
@grid[row][column] = number
solve()
@grid[row][column] = 0
end
end
return
end
end
end
print_grid()
end
endTests
./spec/spec_sudoku.rb
require "spec_helper"
require('sudoku')
RSpec.describe Sudoku do
it 'creates a sudoku class' do
sudoku = Sudoku.new
expect(sudoku).to be_kind_of(Sudoku)
end
it 'should find row values' do
sudoku = Sudoku.new
expect(sudoku.found_in_row(0, 4)).to eq(true)
expect(sudoku.found_in_row(0, 7)).to eq(true)
expect(sudoku.found_in_row(4, 8)).to eq(true)
expect(sudoku.found_in_row(4, 1)).to eq(true)
expect(sudoku.found_in_row(4, 5)).to eq(true)
expect(sudoku.found_in_row(0, 1)).to eq(false)
expect(sudoku.found_in_row(6, 2)).to eq(false)
expect(sudoku.found_in_row(8, 2)).to eq(false)
end
it 'should find column values' do
sudoku = Sudoku.new
expect(sudoku.found_in_column(0, 2)).to eq(false)
expect(sudoku.found_in_column(1, 2)).to eq(false)
expect(sudoku.found_in_column(4, 8)).to eq(true)
expect(sudoku.found_in_column(4, 1)).to eq(true)
expect(sudoku.found_in_column(4, 5)).to eq(false)
expect(sudoku.found_in_column(0, 1)).to eq(true)
expect(sudoku.found_in_column(6, 2)).to eq(false)
expect(sudoku.found_in_column(8, 2)).to eq(false)
end
it 'should find subsquare values' do
sudoku = Sudoku.new
expect(sudoku.found_in_subsquare(0, 0, 2)).to eq(false)
expect(sudoku.found_in_subsquare(0, 1, 2)).to eq(false)
expect(sudoku.found_in_subsquare(0, 4, 8)).to eq(true)
expect(sudoku.found_in_subsquare(0, 4, 1)).to eq(false)
expect(sudoku.found_in_subsquare(6, 4, 5)).to eq(false)
expect(sudoku.found_in_subsquare(6, 0, 1)).to eq(false)
expect(sudoku.found_in_subsquare(6, 6, 2)).to eq(false)
expect(sudoku.found_in_subsquare(6, 8, 2)).to eq(false)
end
it 'should set possible if values were not found' do
sudoku = Sudoku.new
expect(sudoku.is_possible(0, 0, 2)).to eq(true)
expect(sudoku.is_possible(0, 1, 2)).to eq(true)
expect(sudoku.is_possible(0, 4, 8)).to eq(false)
expect(sudoku.is_possible(0, 4, 1)).to eq(false)
expect(sudoku.is_possible(6, 4, 5)).to eq(true)
expect(sudoku.is_possible(6, 0, 1)).to eq(false)
expect(sudoku.is_possible(6, 6, 2)).to eq(true)
expect(sudoku.is_possible(6, 8, 2)).to eq(true)
end
endExecution Time
time ruby sudoku.rb
[ 3 8 2 6 9 4 1 5 7 ]
[ 4 7 5 8 1 2 3 9 6 ]
[ 9 1 6 3 5 7 2 8 4 ]
[ 8 9 4 1 3 5 6 7 2 ]
[ 5 2 7 9 4 6 8 3 1 ]
[ 1 6 3 7 2 8 5 4 9 ]
[ 7 3 8 2 6 9 4 1 5 ]
[ 2 4 9 5 8 1 7 6 3 ]
[ 6 5 1 4 7 3 9 2 8 ]
52.880 secsJavascript
Is the simplest implementation alongside of python.
Implementation
const testGrid = [
[ 0, 0, 4, 0, 0, 0, 0, 6, 7 ],
[ 3, 0, 0, 4, 7, 0, 0, 0, 5 ],
[ 1, 5, 0, 8, 2, 0, 0, 0, 3 ],
[ 0, 0, 6, 0, 0, 0, 0, 3, 1 ],
[ 8, 0, 2, 1, 0, 5, 6, 0, 4 ],
[ 4, 1, 0, 0, 0, 0, 9, 0, 0 ],
[ 7, 0, 0, 0, 8, 0, 0, 4, 6 ],
[ 6, 0, 0, 0, 1, 2, 0, 0, 0 ],
[ 9, 3, 0, 0, 0, 0, 7, 1, 0 ],
]
const grid = [
[ 0, 0, 2, 0, 0, 4, 0, 0, 0 ],
[ 0, 7, 0, 0, 0, 2, 0, 0, 0 ],
[ 0, 0, 6, 3, 0, 0, 0, 8, 0 ],
[ 0, 9, 0, 0, 0, 0, 0, 0, 0 ],
[ 5, 2, 7, 9, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 8, 0, 4, 0 ],
[ 0, 0, 0, 0, 0, 0, 4, 0, 5 ],
[ 0, 4, 0, 0, 0, 1, 0, 6, 0 ],
[ 0, 0, 1, 0, 7, 0, 9, 0, 0 ]
];
const printGrid = () => {
for(let row = 0; row < 9; row++)
{
process.stdout.write("[ ")
for(let column = 0; column < 9; column++)
{
process.stdout.write(`${grid[row][column]} `)
}
process.stdout.write("]\n")
}
process.stdout.write("\n")
}
const foundInRow = (row, number) => {
for (let column = 0; column < 9; column++) {
if (grid[row][column] === number) return true
}
return false
}
const foundInColumn = (column, number) => {
for (let row = 0; row < 9; row++) {
if (grid[row][column] === number) return true
}
return false
}
const foundInSubsquare = (row, column, number) => {
ssRow = Math.floor(row/3)
ssColumn = Math.floor(column/3)
for (let r = 0; r < 3; r++) {
for (let c = 0; c < 3; c++) {
if (grid[ssRow * 3 + r][ssColumn * 3 + c] === number) return true
}
}
return false
}
const isPossible = (row, column, number) => {
if (foundInRow(row, number)) return false
if (foundInColumn(column, number)) return false
if (foundInSubsquare(row, column, number)) return false
return true
}
const solve = () => {
for (let row = 0; row < 9; row++) {
for (let column = 0; column < 9; column++) {
if(grid[row][column] === 0)
{
for (let number = 1; number < 10; number++) {
if (isPossible(row, column, number)){
grid[row][column] = number
solve()
grid[row][column] = 0
}
}
return
}
}
}
printGrid()
}
solve()
Execution Time
time node index.js
[ 3 8 2 6 9 4 1 5 7 ]
[ 4 7 5 8 1 2 3 9 6 ]
[ 9 1 6 3 5 7 2 8 4 ]
[ 8 9 4 1 3 5 6 7 2 ]
[ 5 2 7 9 4 6 8 3 1 ]
[ 1 6 3 7 2 8 5 4 9 ]
[ 7 3 8 2 6 9 4 1 5 ]
[ 2 4 9 5 8 1 7 6 3 ]
[ 6 5 1 4 7 3 9 2 8 ]
1.291 secsJava
Java? Yes, why not!
Implementation
package moritz.algorithms;
public class Sudoku{
public static int[][] grid = new int[][]{
{ 0, 0, 2, 0, 0, 4, 0, 0, 0 },
{ 0, 7, 0, 0, 0, 2, 0, 0, 0 },
{ 0, 0, 6, 3, 0, 0, 0, 8, 0 },
{ 0, 9, 0, 0, 0, 0, 0, 0, 0 },
{ 5, 2, 7, 9, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 8, 0, 4, 0 },
{ 0, 0, 0, 0, 0, 0, 4, 0, 5 },
{ 0, 4, 0, 0, 0, 1, 0, 6, 0 },
{ 0, 0, 1, 0, 7, 0, 9, 0, 0 }
};
public static void main(String[] args){
solve();
}
public static void printGrid(){
for (int row = 0; row < 9; row++) {
System.out.print("[ ");
for (int column = 0; column < 9; column++) {
System.out.print(grid[row][column] + " ");
}
System.out.print("]\n");
}
}
public static boolean foundInRow(int row, int number){
for (int column = 0; column < 9; column++) {
if (grid[row][column] == number){
return true;
}
}
return false;
}
public static boolean foundInColumn(int column, int number){
for (int row = 0; row < 9; row++) {
if (grid[row][column] == number){
return true;
}
}
return false;
}
public static boolean foundInSubsquare(int row, int column, int number){
int ssRow = (int)Math.floor(row / 3);
int ssColumn = (int)Math.floor(column / 3);
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
if (grid[ssRow * 3 + r][ssColumn * 3 + c] == number){
return true;
}
}
}
return false;
}
public static boolean isPossible(int row, int column, int number){
if (foundInRow(row, number)){
return false;
}
if (foundInColumn(column, number)){
return false;
}
if (foundInSubsquare(row, column, number)){
return false;
}
return true;
}
public static void solve() {
for (int row = 0; row < 9; row++) {
for (int column = 0; column < 9; column++) {
if (grid[row][column] == 0){
for (int number = 1; number < 10; number++) {
if (isPossible(row, column, number)){
grid[row][column] = number;
solve();
grid[row][column] = 0;
}
}
return;
}
}
}
printGrid();
}
}Execution Time
[ 3 8 2 6 9 4 1 5 7 ]
[ 4 7 5 8 1 2 3 9 6 ]
[ 9 1 6 3 5 7 2 8 4 ]
[ 8 9 4 1 3 5 6 7 2 ]
[ 5 2 7 9 4 6 8 3 1 ]
[ 1 6 3 7 2 8 5 4 9 ]
[ 7 3 8 2 6 9 4 1 5 ]
[ 2 4 9 5 8 1 7 6 3 ]
[ 6 5 1 4 7 3 9 2 8 ]
0.629 secsClojure
I couldn’t forget to include a funcional language. And just for fun, I’ve implemented in addition to a the same as all others, a more human approach.
Base Implementation
Code
(ns sudoku
(:require [java-time :as t]))
(def grid
'(
(0 0 2 0 0 4 0 0 0)
(0 7 0 0 0 2 0 0 0)
(0 0 6 3 0 0 0 8 0)
(0 9 0 0 0 0 0 0 0)
(5 2 7 9 0 0 0 0 0)
(0 0 0 0 0 8 0 4 0)
(0 0 0 0 0 0 4 0 5)
(0 4 0 0 0 1 0 6 0)
(0 0 1 0 7 0 9 0 0))
)
(defn grid-item [grid row column]
(nth (nth grid row) column))
(defn found-in-row
[grid row number]
(reduce
#(if (= number %2)
(reduced true)
(or %1 (= number %2)))
false (nth grid row)))
(defn found-in-column
[grid
column
number]
(reduce
#(if (= number %2)
(reduced true)
(or %1 (= number %2)))
false (map (fn [row] (nth row column)) grid)))
(defn found-in-subsquare
[grid
row
column
number]
(let [ss-row (int (/ row 3))
ss-column (int (/ column 3))]
(reduce
#(if (= number %2)
(reduced true)
(or %1 (= number %2)))
false
(->> grid
(drop (* 3 ss-row))
(take 3)
(apply map list)
(drop (* 3 ss-column))
(take 3)
(apply map list)
(flatten)))))
(defn is-possible
([grid pos number] (is-possible grid (pos :row) (pos :column) number))
([grid row column number]
(cond
(found-in-row grid row number) false
(found-in-column grid column number) false
(found-in-subsquare grid row column number) false
:else true)))
(defn grid-set
([grid pos number] (grid-set grid (pos :row) (pos :column) number))
([grid row column number]
(apply list (update-in (vec (map vec grid)) [row column] (fn [itm] number)))))
(def start-pos
{:row 0 :column 0 :done false})
(defn next-pos
([pos] (next-pos (pos :row) (pos :column)))
([row column]
(cond
(and (= column 8) (= 8 row)) {:row row, :column (inc column) :done true}
(= column 8) {:row (inc row), :column 0 :done false}
:else {:row row, :column (inc column) :done false})))
(defn count-zeroes
[grid]
(count (filter (fn [n] (= n 0)) (flatten grid))))
(defn solve
([grid] (solve grid start-pos))
([grid pos]
(if (pos :done)
grid
(let [next (next-pos pos)]
(if (= (grid-item grid (pos :row) (pos :column)) 0)
(let [possibles (filter (fn [n] (is-possible grid pos n)) (range 1 10))]
(if (= (grid-item grid (pos :row) (pos :column)) 0)
(filter (fn [item] (not= item '())) (map (fn [p] (solve (grid-set grid pos p) next)) possibles))))
(solve grid next))))))
(defn run [options]
(let [solution (solve grid start-pos)
unwrap (fn [s]
(if (vector? (first s))
s
(recur (first s))))]
(doseq [item (unwrap solution)]
(println item))))Execution Time
time clj -X sudoku/run
[3 8 2 6 9 4 1 5 7]
[4 7 5 8 1 2 3 9 6]
[9 1 6 3 5 7 2 8 4]
[8 9 4 1 3 5 6 7 2]
[5 2 7 9 4 6 8 3 1]
[1 6 3 7 2 8 5 4 9]
[7 3 8 2 6 9 4 1 5]
[2 4 9 5 8 1 7 6 3]
[6 5 1 4 7 3 9 2 8]
clj -X sudoku/run 100,44s user 0,67s system 111% cpu 1:30,51 totalHuman Like Implementation
In this solution I created a matrix with all possible numbers in each position and start from the squared with less possibilities. Pretty much the way a human would solve the Sudoku puzzle.
Code
(ns order
(:require [java-time :as t]))
(def grid
'(
(0 0 2 0 0 4 0 0 0)
(0 7 0 0 0 2 0 0 0)
(0 0 6 3 0 0 0 8 0)
(0 9 0 0 0 0 0 0 0)
(5 2 7 9 0 0 0 0 0)
(0 0 0 0 0 8 0 4 0)
(0 0 0 0 0 0 4 0 5)
(0 4 0 0 0 1 0 6 0)
(0 0 1 0 7 0 9 0 0))
)
(def all-possibles-expected
'(((2) (2 8 9) () (3 5 9) (3 5 9) (1 3 9) (1 2 8) () ())
(() (2 6 8 9) (8 9) () () (1 6 9) (1 2 8) (2 8 9) ())
(() () (7 9) () () (6 9) (4) (9) ())
((5) (7 9) () (2 7 9) (4 9) (4 7 8 9) (2 5 8) () ())
(() (7 9) () () (3 9) () () (7) ())
(() () (3 5 7) (2 3 6 7) (3 6) (3 6 7 8) () (2 5 7 8) (2 8))
(() (2) (1 5) (3 5 9) () (3 9) (2 3 5) () ())
(() (4 8) (5 8) (3 5 7 9) () () (3 5 8) (5 8 9) (8 9))
(() () (5 8) (5 6) (4 5 6) (4 6) () () (2 8)))
)
(defn grid-item [grid row column]
(nth (nth grid row) column))
(defn found-in-row
[grid row number]
(reduce
#(if (= number %2)
(reduced true)
(or %1 (= number %2)))
false (nth grid row)))
(defn found-in-column
[grid
column
number]
(reduce
#(if (= number %2)
(reduced true)
(or %1 (= number %2)))
false (map (fn [row] (nth row column)) grid)))
(defn found-in-subsquare
[grid
row
column
number]
(let [ss-row (int (/ row 3))
ss-column (int (/ column 3))]
(reduce
#(if (= number %2)
(reduced true)
(or %1 (= number %2)))
false
(->> grid
(drop (* 3 ss-row))
(take 3)
(apply map list)
(drop (* 3 ss-column))
(take 3)
(apply map list)
(flatten)))))
(defn is-possible
([grid pos number] (is-possible grid (pos :row) (pos :column) number))
([grid row column number]
(cond
(found-in-row grid row number) false
(found-in-column grid column number) false
(found-in-subsquare grid row column number) false
:else true)))
(defn grid-set
([grid pos number] (grid-set grid (pos :row) (pos :column) number))
([grid row column number]
(apply list (update-in (vec (map vec grid)) [row column] (fn [itm] number)))))
(def start-pos
{:row 0, :column 0 :done false})
(defn next-pos
([] start-pos)
([pos]
(let [row (pos :row)
column (pos :column)]
(cond
(and (= column 8) (= 8 row)) {:row row, :column (inc column) :done true}
(= column 8) {:row (inc row), :column 0 :done false}
:else {:row row, :column (inc column) :done false}))))
(defn count-zeroes
[grid]
(count (filter (fn [n] (= n 0)) (flatten grid))))
(defn get-all-possibles-grid
[grid]
(map-indexed
(fn [row-index row]
(map-indexed
(fn [column-index column]
(filter (fn [n]
(and (= column 0)
(is-possible grid row-index column-index n))) (range 1 10)))
row))
grid))
(defn count-possibilities-grid
[grid]
(map
(fn [row] (map count row))
(get-all-possibles-grid grid)))
(defn least-possibilities-pos
[grid]
(if (= 0 (count-zeroes grid))
{:row 8 :column 8 :done true}
(let [value (apply
min-key
(fn [item]
(second (second item)))
(map-indexed
(fn [row-index row]
[row-index
(apply
min-key
second
(map-indexed
(fn [column-index column]
[column-index
(if (= column 0)
10
column)])
row))])
(count-possibilities-grid grid)))]
{:done false :row (first value) :column (first (second value))})))
(defn get-positions
[grid]
(let [items (sort-by
second
(filter
(fn [item]
(not (= 10 (second item))))
(reduce
concat
(map-indexed
(fn [row-index row]
(map-indexed
(fn [column-index column]
[(+ (* 9 row-index) column-index)
(if (= column 0)
10
column)])
row))
(count-possibilities-grid grid)))))]
(concat
(map-indexed
(fn [item-index item]
{:row (int (/ (first item) 9)) :column (mod (first item) 9) :done false})
items)
'({:done true}))))
(defn is-branch-valid
([grid] (is-branch-valid grid (count-possibilities-grid grid) start-pos))
([grid possibles pos]
(let [next (next-pos pos)
row (:row pos)
column (:column pos)
done (:done pos)]
(if done
true
(if (= (grid-item (count-possibilities-grid grid) row column)
(grid-item grid row column)
0)
false
(is-branch-valid grid possibles next))))))
(defn debug-solver
[pos ps new-grid]
(println pos)
(Thread/sleep 200)
(doseq [item ps]
(println item))
(doseq [item new-grid]
(println item)))
(defn debug-solution
[grid]
;; (Thread/sleep 1000)
(println "Found a solution!")
(doseq [item grid]
(println item)))
(defn solve
([grid positions possibilities]
(let [pos (first positions)]
(if (pos :done)
(do
(debug-solution grid)
grid
)
(if (is-branch-valid grid)
(if (= (grid-item grid (pos :row) (pos :column)) 0)
(let [possibles (grid-item possibilities
(pos :row) (pos :column))]
(filter (fn [item] (not= item '()))
(map (fn [p]
(let [new-grid (grid-set grid pos p)
ps (get-all-possibles-grid new-grid)]
;; (debug-solver pos ps new-grid)
(solve new-grid
(get-positions new-grid)
ps)))
possibles)))
(do
(println "something wrong..." pos)
(Thread/sleep 1000)
;; (solve grid (rest positions) (get-all-possibles-grid grid))
)))))))
(defn run [options]
(println (solve grid (get-positions grid) (get-all-possibles-grid grid))))Execution Time
time clj -X order/run
[3 8 2 6 9 4 1 5 7]
[4 7 5 8 1 2 3 9 6]
[9 1 6 3 5 7 2 8 4]
[8 9 4 1 3 5 6 7 2]
[5 2 7 9 4 6 8 3 1]
[1 6 3 7 2 8 5 4 9]
[7 3 8 2 6 9 4 1 5]
[2 4 9 5 8 1 7 6 3]
[6 5 1 4 7 3 9 2 8]
clj -X order/run 56,59s user 0,48s system 121% cpu 46,836 totalConclusion
No matter this language benchmark is not scientific, I display here my results.
| Linguagem | Optimized Time (s) | Unoptimized Time (s) |
|---|---|---|
| Python | 58.032 | |
| C++ | 0.281 | 1.307 |
| Rust | 0.605 | 13.954 |
| C# | 1.506 | 1.798 |
| GoLang | 0.644 | |
| Ruby | 52.880 | |
| Javascript | 1.291 | |
| Java | 0.629 | |
| Clojure 1 | 100.44 | |
| Clojure 2 | 56.59 |