Sudoku
Publish date: Sep 27, 2021
TL;DR
Fiz várias implementações de uma solução recursiva simples do Sudoku. Os resultados estão aqui.
A Ideia
Após assistir um vídeo interessante do canal Computerphile sobre recursividade que implementava uma solução para o Sudoku, decidi implementar a mesma solução - ou como eu me lembrava dela - por conta própria.
Um Problema para Testar a Implementação
Decidi testar a implementação inicialmente com o mesmo problema apresentado no vídeo. Assim eu não teria dúvida se estaria cometendo algum erro na linguagem que estaria penalizando demais o desempenho da solução. O problema em questão:
#!/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 ],
]Depois de obter sucesso resolvendo o mesmo problema do vídeo, testei com um problema difícil.
#!/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 ],
];Soluções
Seguindo a ideia de vídeo, implementei a primeira solução em python, depois segui implementado em outras linguanges para comparar tempo de execução. Este exercício não tem como finalidade gerar um benchmark confiável entre liguangens, mas apenas exercício. Há muitas estratégias disponíveis para criar programas rápidos, mesmo em linguagens tidas como lentas.
Python
A minha primeira foi implementada em python, a mesma linguagem do vídeo. Esse é a minha primeira solução e basicamente repete a implementada no vídeo. Ela não foi escrita para ser eficiente, mas eventualmente retorna as soluções para o problema. Um problema visível é que a função is_possible repete o laço for três vezes quando poderia executá-lo somente uma vez.
Implementação
#!/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()Tempo de Execução
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++
A primeira ideia foi buscar extremos. Escrever a mesma ideia de solução em uma linguagem o mais performática possível. A minha escolha foi o C++. Abaixo a implmentação e os resultados.
Implementação
#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;
}
Tempo de Execução
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 secsOu, sem a flag de otimização:
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
Outra linguagem voltada para performance, porém mais moderna, que eu tive a curiosidade de testar foi Rust. Essa linguagem tem muitos recursos de sintaxe que eu desconheço e desconfio que alguma escolha que eu posso ter feito na forma de representar o meu problema podem ter deixado a execução mais lenta, mas aí vai o que fiz.
Implementação
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!(".")
}
}
Tempo de Execução
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 secsDeixando também as versões sem otimizações de compilador:
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#
É uma linguagem que eu já tenho mais familiaridade, portanto a imlementação foi muito rápida. A performance obtidade não chega a impressionar.
Implementação
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();
}
}
}
Tempo de Execução
/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 secsDeixando também as versões sem otimizações de compilador:
/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.
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.798 secsGolang
Outra linguagem que eu quis testar foi Golang. A linguagem do Google famosa pelo seu modelo de concorrência vai ter pouco chance de brilhar nas mãos deste açougueiro do código. Essa implementação também promete ser descuidada e trazer muitas ineficiências pelo mau uso!
Implementação
Como esta não é uma linguagem que eu uso no dia-a-dia, segui um roteiro para criar um projeto novo. A solução em Golang recebeu regalias e foi feita em 3 arquivos.
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)
}
}
Tempo de Execução
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 foi uma das linguagens que eu aprendi quando estava começando com a programação. Aproveitei a oportunidade para matar as saudades.
Implementação
Aqui também preferi partir da estrutura de diretórios convencional para usar o rspec para fazer meus testes. rspec tb é a única dependência no 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()Solução
./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
endTestes
./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
endTempo de Execução
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
Achou que não ia ter Javascript? É a linguagem menos burocrática e fiz uma implementação com a mesma característica.
Implementação
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()
Tempo de Execução
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? Bora!
Implementação
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();
}
}Tempo de Execução
[ 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
Não poderia faltar uma linguagem funcional. E como estava divertido, implementei uma solução parecida com a do python e mais uma variação numa abordagem mais parecida com a humana.
Implementação Inicial
Código
(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))))Tempo de Execução
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 totalImplementação com Abordagem Humana
Nesta solução eu gero uma matriz com as números possibilidades em cada campo vazio e procuro preencher primeiro os que tem menos opções. Tentando assim cortara árvore de busca.
Código
(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))))Tempo de Execução
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 totalConclusão
Ainda sabendo que de nada vale esse benchmark porque os níveis de conhecimento que eu tenho das linguagens é muito variado e não foram utilizadas as melhores práticas em cada uma delas, deixo aqui anotadas os valores do tempo de execução de cada linguagem.
| Linguagem | Tempo Otimizado(s) | Tempo não Otimizado(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 |