[Vari] Contest 15

[!k-0t1c!]

Ciao a tutti :)
Vi propongo un piccolo contest che trovo interessante sia dal punto di vista del linguaggio, sia da quello algoritmico.
L'idea è implementare un semplice risolutore automatico di sudoku (http://it.wikipedia.org/wiki/Sudoku) (versione classica, 9x9).
Il target è quello di trovare una soluzione ad un puzzle (se esiste), ed è specialmente importante farlo in un tempo ragionevole ;)
La scelta del linguaggio è naturalmente libera e dopo qualche risposta proporrò la mia soluzione, in F#.
Non importa come decidete di codificare il puzzle iniziale, l'importante è che misuriate il tempo necessario a valutare la soluzione.
Infine, la soluzione è da presentare semplicemente in formato CSV con 9 colonne per riga e 9 righe.
Se un puzzle non ha soluzione la cosa va segnalata all'utente.
Di seguito vi propongo un puzzle di riferimento notoriamente "difficile" su cui basare i benchmarks. Il formato è uguale a quello della soluzione ma al posto degli spazi vuoti ci sono degli 0:

0,0,0,0,0,0,0,0,0
0,0,0,0,0,3,0,8,5
0,0,1,0,2,0,0,0,0
0,0,0,5,0,7,0,0,0
0,0,4,0,0,0,1,0,0
0,9,0,0,0,0,0,0,0
5,0,0,0,0,0,0,7,3
0,0,2,0,1,0,0,0,0
0,0,0,0,4,0,0,0,9


Buon divertimento! ;)

[~FullSyst3m~]

Ciao a tutti :)
Vi propongo un piccolo contest che trovo interessante sia dal punto di vista del linguaggio, sia da quello algoritmico.
L'idea è implementare un semplice risolutore automatico di sudoku (http://it.wikipedia.org/wiki/Sudoku) (versione classica, 9x9).
Il target è non quello di trovare una soluzione ad un puzzle (se esiste), ed è specialmente importante farlo in un tempo ragionevole ;)
La scelta del linguaggio è naturalmente libera e dopo qualche risposta proporrò la mia soluzione, in F#.
Non importa come decidete di codificare il puzzle iniziale, l'importante è che misuriate il tempo necessario a valutare la soluzione.
Infine, la soluzione è da presentare semplicemente in formato CSV con 9 colonne per riga e 9 righe.
Se un puzzle non ha soluzione la cosa va segnalata all'utente.
Di seguito vi propongo un puzzle di riferimento notoriamente "difficile" su cui basare i benchmarks. Il formato è uguale a quello della soluzione ma al posto degli spazi vuoti ci sono degli 0:

0,0,0,0,0,0,0,0,0
0,0,0,0,0,3,0,8,5
0,0,1,0,2,0,0,0,0
0,0,0,5,0,7,0,0,0
0,0,4,0,0,0,1,0,0
0,9,0,0,0,0,0,0,0
5,0,0,0,0,0,0,7,3
0,0,2,0,1,0,0,0,0
0,0,0,0,4,0,0,0,9


Buon divertimento! ;)

Un utente che conosco ne aveva fatto uno in Python, io però non mi ci sono mai messo. Non ho mai giocato seriamente a sudoku, quindi dovrei prima fare un pò di pratica :D

[wingman87]

27 minuti e 41 secondi con Paint :p

[~FullSyst3m~]

27 minuti e 41 secondi con Paint :p

Cosa è che hai fatto con Paint?

[!k-0t1c!]

In 27 minuti immagino si sia fatto la griglia e l'abbia risolta, ma non era lo scopo del contest...

[DanieleC88]

Non sono sicuro di aver capito bene cosa si debba fare. :stordita:
Forse perché ho letto di fretta? :stordita:

[!k-0t1c!]

Ti deve aver confuso un "non" di troppo che mi dev'essere sfuggito ieri per la stanchezza. Il succo è sviluppare un risolutore di sudoku che trovi una soluzione rapidamente (tanto più in fretta quanto meglio).

[DanieleC88]

Sì, in effetti quel "non" mi aveva abbastanza destabilizzato, me ne sfuggiva lo scopo... :D
Ok, in questi giorni lavorerò ad un risolutore. ;)

[wingman87]

In 27 minuti immagino si sia fatto la griglia e l'abbia risolta, ma non era lo scopo del contest...
Esatto, mi piace risolvere i Sudoku così... vediamo se riuscite a fare un risolutore più veloce :p
Scherzo naturalmente :Prrr:

Riguardo il contest, i sudoku che si deve risolvere sono tutti risolvibili senza mai usare il bruteforce? Ossia ad ogni mossa è sempre possibile mettere con certezza un numero oppure a volte è necessario tirare a caso (naturalmente in maniera legale) e vedere poi come va ed eventualmente tornare indietro?
Il sudoku che hai proposto ad esempio non necessita di bruteforce e sono il genere di sudoku che mi piacciono di più.

[~FullSyst3m~]

Io è da un pò che non gioco a sudoku, quindi prima dovrei riprendere e poi implementare gli algoritmi che uso io per risolverlo. Vediamo se ho tempo per farlo.

[!k-0t1c!]

Esatto, mi piace risolvere i Sudoku così... vediamo se riuscite a fare un risolutore più veloce :p
Scherzo naturalmente :Prrr:

Riguardo il contest, i sudoku che si deve risolvere sono tutti risolvibili senza mai usare il bruteforce? Ossia ad ogni mossa è sempre possibile mettere con certezza un numero oppure a volte è necessario tirare a caso (naturalmente in maniera legale) e vedere poi come va ed eventualmente tornare indietro?
Il sudoku che hai proposto ad esempio non necessita di bruteforce e sono il genere di sudoku che mi piacciono di più.
Il risolutore deve risolvere qualsiasi schema risolvibile, dunque anche quelli che richiedono talvolta di tirare a "indovinare" (idealmente perfino uno schema vuoto o con un solo numero etc).

[gugoXX]

Mi iscrivo.
Ma sono incasinato questa settimana,non so quando riusciro' a tirare giu' qualcosa.

[ally]

...java...


public class Sudoku {

public static void main(String[] args) {

args = new String[]{"153","178","185","221","242","335","357","424","461","519","605","677","683","722","741","844","889"};

long time = System.currentTimeMillis();

int[][] matrix = parseProblem(args);
writeMatrix(matrix);
if (solve(0,0,matrix)) // solves in place
writeMatrix(matrix);
else
System.out.println("NONE");

System.out.println("in "+(System.currentTimeMillis()-time)+" millis");
}

static boolean solve(int i, int j, int[][] cells) {
if (i == 9) {
i = 0;
if (++j == 9)
return true;
}
if (cells[i][j] != 0) // skip filled cells
return solve(i+1,j,cells);

for (int val = 1; val <= 9; ++val) {
if (legal(i,j,val,cells)) {
cells[i][j] = val;
if (solve(i+1,j,cells))
return true;
}
}
cells[i][j] = 0; // reset on backtrack
return false;
}

static boolean legal(int i, int j, int val, int[][] cells) {
for (int k = 0; k < 9; ++k) // row
if (val == cells[k][j])
return false;

for (int k = 0; k < 9; ++k) // col
if (val == cells[i][k])
return false;

int boxRowOffset = (i / 3)*3;
int boxColOffset = (j / 3)*3;
for (int k = 0; k < 3; ++k) // box
for (int m = 0; m < 3; ++m)
if (val == cells[boxRowOffset+k][boxColOffset+m])
return false;

return true; // no violations, so it's legal
}

static int[][] parseProblem(String[] args) {
int[][] problem = new int[9][9]; // default 0 vals
for (int n = 0; n < args.length; ++n) {
int i = Integer.parseInt(args[n].substring(0,1));
int j = Integer.parseInt(args[n].substring(1,2));
int val = Integer.parseInt(args[n].substring(2,3));
problem[i][j] = val;
}
return problem;
}

static void writeMatrix(int[][] solution) {
for (int i = 0; i < 9; ++i) {
if (i % 3 == 0)
System.out.println(" -----------------------");
for (int j = 0; j < 9; ++j) {
if (j % 3 == 0) System.out.print("| ");
System.out.print(solution[i][j] == 0
? " "
: Integer.toString(solution[i][j]));

System.out.print(' ');
}
System.out.println("|");
}
System.out.println(" -----------------------");
}

}




-----------------------
| 9 8 7 | 6 5 4 | 3 2 1 |
| 2 4 6 | 1 7 3 | 9 8 5 |
| 3 5 1 | 9 2 8 | 7 4 6 |
-----------------------
| 1 2 8 | 5 3 7 | 6 9 4 |
| 6 3 4 | 8 9 2 | 1 5 7 |
| 7 9 5 | 4 6 1 | 8 3 2 |
-----------------------
| 5 1 9 | 2 8 6 | 4 7 3 |
| 4 7 2 | 3 1 9 | 5 6 8 |
| 8 6 3 | 7 4 5 | 2 1 9 |
-----------------------
in 41309 millis


...su centrino 1,6 Ghz prima maniera...

...ciao Andrea...

[!k-0t1c!]

Finalmente una prima soluzione :)
Un brute force, ok, ma almeno qualcuno si è dato da fare!
Aspetto almeno un'altra soluzione e poi posto la mia ;)

[ally]

Finalmente una prima soluzione :)
Un brute force, ok, ma almeno qualcuno si è dato da fare!
Aspetto almeno un'altra soluzione e poi posto la mia ;)

...non è codice mio...l'avevo trovato un po' di tempto fa...si un brute force compatto pratico e buono...

...ciao Andrea...

[banryu79]

Se vi può servire, posto un generatore di schemi sudoku che avevo implementato per sfizio un annetto fa (implementato con un algoritmo di backtracking, lo stesso tipo di algoritmo usato nel codice di ally per risolvere uno schema).

import java.util.ArrayList;
import java.util.Random;

/**
* build up a new Sudoku schema using a backtracking algorithm tecnique while filling a
* cell one at time with a random generated number (whoes values are in the dominio).
* If the generated value is correct (no duplicate value in same region, column and row)
* than it is stored, otherwise discard it and try with a new one.
* If all values for current cell are invalid step back.
*
* @author Francesco Baro
*/
public class SudokuGenerator
{
private int[] gridValues;
private ArrayList<ArrayList<Integer>> available;

// Algorithm Statistics
private int loops; // counter for tracking total loops in the algorithm
private int stepsBack; // counter for tracking how many "steps back" has been performed


public SudokuGenerator()
{
gridValues = new int[81]; // 81 cells

available = new ArrayList<ArrayList<Integer>>(); // 9 values for each cell
for(int i = 0; i < 81; i++)
{
ArrayList<Integer> numberset = new ArrayList<Integer>(9);
for(int k = 1; k <= 9; k++)
{
numberset.add(new Integer(k));
}
available.add(numberset);
}
}


/**
* generate a new, valid, Sudoku schema.
*/
public void generateSchema()
{
int cellIndex = 0;

do
{
loops++;

if (notOutOfNumbers(cellIndex))
{
int randomIndex = nextRandom(cellIndex);
int value = available.get(cellIndex).get(randomIndex);
if (isValid(value, cellIndex))
{
gridValues[cellIndex] = value; // store value
available.get(cellIndex).remove(randomIndex); // remove used num
cellIndex++; // step foward!
continue;
}
else
{
available.get(cellIndex).remove(randomIndex); // invalid number
continue;
}
}
else
{
for(int i = 1; i <= 9; i++)
available.get(cellIndex).add(new Integer(i)); // replenish numbers
gridValues[cellIndex] = 0; // reset value
cellIndex--; // step back!
stepsBack++;
continue;
}
}
while(cellIndex < 81);
}

private boolean notOutOfNumbers(final int cellIndex)
{
return available.get(cellIndex).size() > 0;
}

private int nextRandom(final int cellIndex)
{
ArrayList<Integer> subset = available.get(cellIndex);
int limit = subset.size();

Random rand = new Random();
int index = rand.nextInt(limit); // between 0(inclusive) and limit(exclusive)

return index;
}

/**
* check if last generated value is not a duplicate in the region, row and colum.
*/
private boolean isValid(int randomVal, final int cellIndex)
{
boolean valid = true;


// check same row
int rowIndex[] = indexesOfRow(findRow(cellIndex));
for(int i = 0; i < 9; i++)
{
if (rowIndex[i] != cellIndex) // same cell, skip testing
{
if (gridValues[rowIndex[i]] == randomVal) // value alredy present
{
valid = false;
break;
}
}
}


// check same column
int colIndex[] = indexesOfColumn(findColumn(cellIndex));
for(int i = 0; i < 9; i++)
{
if (colIndex[i] != cellIndex)
{
if (gridValues[colIndex[i]] == randomVal)
{
valid = false;
break;
}
}
}


// check same region
int regionIndexes[] = indexesOfRegion(findRegion(cellIndex));
for(int i = 0; i < 9; i++)
{
if (regionIndexes[i] != cellIndex)
{
if (gridValues[regionIndexes[i]] == randomVal)
{
valid = false;
break;
}
}
}

return valid;
}

private int findRow(final int index)
{
double division = Math.ceil((index + 1.0) / 9.0);
return (int) division;
}

private int findColumn(final int index)
{
int modulo = (index+1) % 9;
modulo = (modulo != 0) ? modulo : 9;
return modulo;
}

private int findRegion(final int index)
{
int row = findRow(index);
int column = findColumn(index);

int sumRow;
if (row <= 3)
sumRow = 0;
else
if (row <= 6)
sumRow = 3;
else
sumRow = 6;

int sumColumn;
if (column <= 3)
sumColumn = 1;
else
if (column <= 6)
sumColumn = 2;
else
sumColumn = 3;

return sumRow + sumColumn;
}

private int[] indexesOfRow(int row)
{
int[] indexArray = new int[9];

int maxIndex = (row * 9) - 1;
int minIndex = maxIndex - 8;
for(int i = 0; i < 9; i++)
{
indexArray[i] = minIndex++;
}

return indexArray;
}

private int[] indexesOfColumn(int column)
{
int[] indexArray = new int[9];

for(int i = 0; i < 9; i++)
{
indexArray[i] = (column + 9*i) - 1;
}

return indexArray;
}

private int[] indexesOfRegion(int region)
{
int[] indexArray = new int[9];

int startingValue;

if (region == 1)
startingValue = 0;
else
if (region == 2)
startingValue = 3;
else
if (region == 3)
startingValue = 6;
else
if (region == 4)
startingValue = 27;
else
if (region == 5)
startingValue = 30;
else
if (region == 6)
startingValue = 33;
else
if (region == 7)
startingValue = 54;
else
if (region == 8)
startingValue = 57;
else
startingValue = 60;

int increment = 1;
int sum = 0;
for(int i = 1; i <= 9; i++)
{
if (i < 4)
sum = 0;
else
if (i > 3 && i < 7)
sum = 9;
else
if (i > 6)
sum = 18;

indexArray[i-1] = startingValue + (increment-1) + sum;
if (increment%3 == 0)
increment = 0;
increment++;
}


return indexArray;
}

public int getLoops()
{
return loops;
}

public int getStepsBack()
{
return stepsBack;
}

public int[] getValues()
{
return gridValues;
}

/**
* used fo testing the class
*/
public static void main(String[] argv)
{
// SudokuGenerator generator = new SudokuGenerator();
// long timeStart = System.currentTimeMillis();
// generator.generateSchema();
// long timeEnd = System.currentTimeMillis();
//
// int[] alpha = generator.gridValues;
// int c = 0;
// for(int i = 0; i < alpha.length; i++)
// {
// c++;
// System.out.print(""+ alpha[i] + ",");
// if (c%9 == 0)
// System.out.println("");
//
// }
// System.out.println("\ngenerated " + c + " values.");
// System.out.println("total loops: " + generator.getLoops());
// System.out.println("steps back: " + generator.getStepsBack());
// System.out.println("schema generated in " + (timeEnd-timeStart) + " milliseconds");

int testTimes = 100000;

int totalLoops = 0;
int totalStepsBack = 0;

long timeStart = System.currentTimeMillis();
for(int i = 0; i < testTimes; i++)
{
SudokuGenerator generator = new SudokuGenerator();
generator.generateSchema();
totalLoops += generator.getLoops();
totalStepsBack += generator.getStepsBack();
}
long timeEnd = System.currentTimeMillis();


System.out.println("average loops: " + totalLoops/testTimes);
System.out.println("average steps back: " + totalStepsBack/testTimes);
System.out.println("average generation time " + (timeEnd-timeStart)/testTimes + " milliseconds");
System.out.println("total time " + (timeEnd-timeStart) + " milliseconds, for running " +
"algorithm " + testTimes + " times.");
}
}

[!k-0t1c!]

Aspetto ancora qualcosa di algoritmicamente più..."simpatico" ;)

[Tommo]

Io ne ho fatto uno abbastanza complesso, ma che per ora non funziona se si deve "indovinare" un valore :D

Però nel caso di quelli facili ci mette davvero poco... magari poi lo posto.

[!k-0t1c!]

Io ne ho fatto uno abbastanza complesso, ma che per ora non funziona se si deve "indovinare" un valore :D

Però nel caso di quelli facili ci mette davvero poco... magari poi lo posto.
Applicando solo le regole, senza "indovinare" mai, la cosa è fattibile in 15righe :p Tutto sta nel saper usare le regole inizialmente e poi "indovinare" intelligentemente. Se comunque hai la parte di verifica delle regole e di riempimento secondo le regole implementare la parte che "indovina" ed eventualmente fa backtracking non dovrebbe essere traumatico ;)

[VICIUS]

Questo è il codice:
require 'Matrix'

class SudokuGrid < Matrix
def self.create_from_file(file_name)
puzzle = Array.new
File.open(file_name) do |f|
while line = f.gets
puzzle << line.split(',').map { |x| x.to_i }
end
end
rows puzzle
end
def to_s
str = ''
0.upto 8 do |row|
0.upto 8 do |col|
str += "#{self[row,col]}" + (((col+1) % 3 == 0) ? " " : " ")
end
str += (((row+1) % 3 == 0) ? "\n\n" : "\n")
end
str.chop
end
def dup
SudokuGrid.rows(@rows)
end
def []=(row, col, value)
@rows[row][col] = value
end
def each_empty_cell
0.upto 8 do |row|
0.upto 8 do |col|
yield row, col if self[row,col] == 0
end
end
end
def find_possible_values(row, col)
all = [1, 2, 3, 4, 5, 6, 7, 8, 9]
box = get_box(row,col)
row = get_row(row)
col = get_col(col)
all - (box + row + col) - [0]
end
private
def get_box(row, col)
clean_matrix(minor(3*(row/3), 3, 3*(col/3), 3))
end
def get_row(row)
clean_matrix(minor(row,1,0,9))
end
def get_col(col)
clean_matrix(minor(0,9,col,1))
end
def clean_matrix(matrix)
matrix.to_a.flatten
end
end

class ConstraintError < Exception
end

class Solver
def self.solve(instance)
instance = instance.dup
row, col, values = try_guessing(instance)
return instance if row.nil?
values.each do |guess|
instance[row,col] = guess
begin
return solve(instance)
rescue ConstraintError
next
end
end
raise ConstraintError
end
private
def self.try_guessing(instance)
continue = true
while continue
continue = false
rowm, colm, valuesm = nil
min = 10
instance.each_empty_cell do |row, col|
values = instance.find_possible_values(row, col)
case values.size
when 0
raise ConstraintError
when 1
instance[row, col] = values[0]
continue = true
else
if !continue and values.size < min
rowm, colm, valuesm, min = row, col, values, values.size
end
end
end
end
return rowm, colm, valuesm
end
end

puts Solver.solve(SudokuGrid.create_from_file('altro.txt'))
Questo è l'output:
9 8 7 6 5 4 3 2 1
2 4 6 1 7 3 9 8 5
3 5 1 9 2 8 7 4 6

1 2 8 5 3 7 6 9 4
6 3 4 8 9 2 1 5 7
7 9 5 4 6 1 8 3 2

5 1 9 2 8 6 4 7 3
4 7 2 3 1 9 5 6 8
8 6 3 7 4 5 2 1 9

Ovviamente trattandosi di una specie di brute force ci mette una vita (quasi 30 secondi sul mio imac). Conoscete qualche strategia più intelligente da usare per risolvere questo giochino?

[ally]

...qui (http://sudoku.klaas.nl/) viene proposta una applet con diversi sistemi di solver...l'algoritmo proposto risolve il caso richiesto dal thread in una manciata di secondi...volevo chiedere all'autore del thread se la difficoltà di risoluzione di questo sudoku sta solo nella scelta di usare una scala di valori decrescente per la prima riga (un brute force incrementando il valore per ogni riquadro arriverà a ricostruire la sequenza 9-8-7... nel maggior tempo possibile) o ci sono altri giochini dietro?...

...ciao Andrea...

[!k-0t1c!]

Ok, dai, posto la mia: il codice è per lo più una traduzione di un post che ho trovato, ma solo per una questione di eleganza. Infatti ho sempre reputato l'uso di un po' di constraint programming la via più comoda e dunque appoggiarsi a un solver era secondo me naturale :p
Il codice è come al solito in F# (4.0), ed in questo caso è richiesta la presenza di Microsoft Solver Foundation (l'express edition gratuita basta).
Il tempo impiegato sul mio misero T7700 @ 2.4ghz è 500ms e gran parte del tempo è spesa per il caricamento/inizializzazione del solver e non per la ricerca della soluzione.

open System
open System.IO
open Microsoft.SolverFoundation.Common
open Microsoft.SolverFoundation.Services

module Sudoku =
type SudokuCell(row, col, value) =
let mutable _value = value
member x.Row = row
member x.Col = col
member x.Value with get() = _value and set(v) = _value <- v
member x.FloatValue with get() = float _value and set(v:float) = _value <- int v

type Block = { KeyRow : int; KeyCol : int; IsIn : Rational }

let Solve(src:int array array) =
let rational (i:int) = Rational.op_Implicit i
let ctx = SolverContext.GetContext()
let model = ctx.CreateModel()
let line = Set(Domain.IntegerRange(rational 0, rational 9), "line")
let board = Array2D.init 9 9 (fun r c -> SudokuCell(r, c, src.[r].[c]))
let boardDec = Decision(Domain.IntegerRange(rational 1, rational 9), "board", line, line)
boardDec.SetBinding(board |> Seq.cast<SudokuCell>, "FloatValue", "Row", "Col")
let presetBoard = Parameter(Domain.IntegerRange(rational 0, rational 9), "presetBoard", line, line)
presetBoard.SetBinding(board |> Seq.cast<SudokuCell>, "Value", "Row", "Col")
model.AddDecision boardDec
model.AddParameter presetBoard
model.AddConstraint(null, Model.ForEach(line, fun i -> Model.ForEachWhere(line, (fun j -> Term.op_Equality(boardDec.[i,j],presetBoard.[i, j])), fun j -> Term.op_GreaterThan(presetBoard.[i, j], 0 |> rational |> Term.op_Implicit)))) |> ignore
model.AddConstraint(null, Model.ForEach(line, fun j -> Model.AllDifferent (Model.ForEach(line, fun i -> boardDec.[i,j])))) |> ignore
model.AddConstraint(null, Model.ForEach(line, fun i -> Model.AllDifferent (Model.ForEach(line, fun j -> boardDec.[i,j])))) |> ignore
let isInBlock i j row col = if i * 3 <= row && row <= i * 3 + 2 && j * 3 <= col && col <= j * 3 + 2 then rational 1 else rational 0
for i in 0..2 do
for j in 0..2 do
let boardBlock = Parameter(Domain.IntegerNonnegative, "boardBlock", line, line)
model.AddParameters boardBlock
boardBlock.SetBinding(board |> Seq.cast<SudokuCell> |> Seq.map(fun c -> { KeyRow = c.Row; KeyCol = c.Col; IsIn = isInBlock i j c.Row c.Col }), "IsIn", "KeyRow", "KeyCol")
model.AddConstraint(null, Model.AllDifferent(Model.ForEach(line, fun keyi -> Model.ForEachWhere(line, (fun keyj -> boardDec.[keyi, keyj]), fun keyj -> boardBlock.[keyi,keyj])))) |> ignore
let solution = ctx.Solve()
if solution.Quality = SolverQuality.Feasible then
ctx.PropagateDecisions()
Some [| for i in 0..8 -> [| for j in 0..8 -> board.[i,j].Value |] |]
else None

let main() =
let puzzle = "sudoku.csv" |> File.ReadAllLines |> Array.Parallel.map(fun ln -> ln.Split([|','|], StringSplitOptions.RemoveEmptyEntries) |> Array.Parallel.map(int))
let sw = System.Diagnostics.Stopwatch.StartNew()
match Sudoku.Solve puzzle with
| Some b -> sw.Stop()
let lines = b |> Array.Parallel.map(fun r -> (r |> Array.fold(fun acc b -> sprintf "%s,%i" acc b) String.Empty).Substring 1)
File.WriteAllLines("solved.csv", lines)
lines |> Seq.iter(fun ln -> printfn "%s" ln)
printfn "Parsed and solved in %ims" sw.ElapsedMilliseconds
| None -> printfn "failed"
Console.ReadKey() |> ignore

do main();;

[!k-0t1c!]

@ally: Il puzzle proposto è preso da QUI (http://en.wikipedia.org/wiki/Algorithmics_of_sudoku) e l'ho scelto apposta perché ero curioso di vedere quanto avrebbe stimolato la gente ad andare 1po' oltre il mero brute force :)

[ally]

1,4,5,7,8,2,6,3,9
3,7,9,1,6,4,5,2,8
2,6,8,3,9,5,4,1,7
5,2,1,4,7,8,3,9,6
4,3,7,6,1,9,2,8,5
8,9,6,2,5,3,1,7,4
7,8,4,5,2,1,9,6,3
6,1,3,9,4,7,8,5,2
9,5,2,8,3,6,7,4,1



0,0,0,0,0,0,0,0,0
0,0,0,0,0,3,0,8,5
0,0,1,0,2,0,0,0,0
0,0,0,5,0,7,0,0,0
0,0,4,0,0,0,1,0,0
0,9,0,0,0,0,0,0,0
5,0,0,0,0,0,0,7,3
0,0,2,0,1,0,0,0,0
0,0,0,0,4,0,0,0,9




...le grigle sembrano diverse...prendo come riferimento la posizione del numero uno sul primo quadrante...

...ciao Andrea...

[!k-0t1c!]

http://tbn3.google.com/images?q=tbn:6Z2zAP5ZaDTN8M:http://westrum.files.wordpress.com/2009/02/holy-facepalm.jpg
Mi ero dimenticato una riga, quella che impone che i valori iniziali diversi da 0 ed i valori finali nelle stesse posizioni coincidano...Fixed, il tempo è salito di qualche millisecondo ma siamo sempre li ;)

[Tommo]

Applicando solo le regole, senza "indovinare" mai, la cosa è fattibile in 15righe :p Tutto sta nel saper usare le regole inizialmente e poi "indovinare" intelligentemente. Se comunque hai la parte di verifica delle regole e di riempimento secondo le regole implementare la parte che "indovina" ed eventualmente fa backtracking non dovrebbe essere traumatico ;)

Vero.
Un'altro conto è invece fare che ci mette 13 ms a risolverlo :)

Ora provo a metterci il "guessing" spero che non faccia aumentare assurdamente i tempi...

[rеpne scasb]

■

[d_traveler]

Linguaggio: C
Algoritmo: Non utilizza la forza bruta.
Tempo: Il tempo impiegato e molto minore di 1 millesimo di secondo


#include <stdio.h>
#include <time.h>

#define N_CLK 10
#define INPUT_FILE_NAME "SUDOKU.DAT"
#define SIZE 9
#define CELL (SIZE/3)

int main(void)

{
clock_t clk[N_CLK];
FILE *input_file_handle;
int b,i,j,k,l,m,n,o,s,sp,sv=SIZE*SIZE,sk[SIZE][SIZE],ts[SIZE][SIZE];

if((input_file_handle=fopen(INPUT_FILE_NAME,"rt"))==NULL)
{
fprintf(stderr,"Non trovo il file " INPUT_FILE_NAME "\n");
return 1;
}

for(i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
{
fscanf(input_file_handle,"%d,",&sk[i][j]);
if(sk[i][j])
sv--;
}
}

if(fclose(input_file_handle))
{
fprintf(stderr,"Errore durante fclose\n");
return 1;
}

printf("*** Input ***\n\n");

for(i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
printf("%d ",sk[i][j]);
printf("\n");
}

clk[0]=clock();

do
{
for(i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
ts[i][j]=0;
}
for(i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
{
if(sk[i][j])
{
for(k=0;k<SIZE;k++)
ts[k][j]|=1<<(sk[i][j]-1);
for(k=0;k<SIZE;k++)
ts[i][k]|=1<<(sk[i][j]-1);
for(k=(i/CELL)*CELL;k<((i/CELL)*CELL+CELL);k++)
{
for(l=(j/CELL)*CELL;l<((j/CELL)*CELL+CELL);l++)
ts[k][l]|=1<<(sk[i][j]-1);
}
}
}
}
for(b=0;b<SIZE;b++)
{
for(i=0;i<SIZE;i++)
{
for(l=j=0;j<SIZE;j++)
{
if(sk[i][j]==0)
{
if((ts[i][j]&(1<<b))==0)
{
l++;
m=j;
}
}
}
if(l==1)
{
sk[i][m]=b+1;
sv--;
for(k=0;k<SIZE;k++)
ts[k][m]|=1<<b;
for(k=0;k<SIZE;k++)
ts[i][k]|=1<<b;
for(k=(i/CELL)*CELL;k<((i/CELL)*CELL+CELL);k++)
{
for(l=(m/CELL)*CELL;l<((m/CELL)*CELL+CELL);l++)
ts[k][l]|=1<<b;
}
}
}
for(j=0;j<SIZE;j++)
{
for(l=i=0;i<SIZE;i++)
{
if(sk[i][j]==0)
{
if((ts[i][j]&(1<<b))==0)
{
l++;
m=i;
}
}
}
if(l==1)
{
sk[m][j]=b+1;
sv--;
for(k=0;k<SIZE;k++)
ts[k][j]|=1<<b;
for(k=0;k<SIZE;k++)
ts[m][k]|=1<<b;
for(k=(m/CELL)*CELL;k<((m/CELL)*CELL+CELL);k++)
{
for(l=(j/CELL)*CELL;l<((j/CELL)*CELL+CELL);l++)
ts[k][l]|=1<<b;
}
}
}
for(i=0;i<SIZE;i+=CELL)
{
for(j=0;j<SIZE;j+=CELL)
{
for(n=0,k=i;k<(i+CELL);k++)
{
for(l=j;l<(j+CELL);l++)
{
if(sk[k][l]==0)
{
if((ts[k][l]&(1<<b))==0)
{
n++;
m=k;
o=l;
}
}
}
}
if(n==1)
{
sk[m][o]=b+1;
sv--;
for(k=0;k<SIZE;k++)
ts[k][o]|=1<<b;
for(k=0;k<SIZE;k++)
ts[m][k]|=1<<b;
for(k=(m/CELL)*CELL;k<((m/CELL)*CELL+CELL);k++)
{
for(l=(o/CELL)*CELL;l<((o/CELL)*CELL+CELL);l++)
ts[k][l]|=1<<b;
}
}
}
}
}

for(sp=i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
{
if(sk[i][j]==0)
{
for(s=k=0;k<SIZE;k++)
s|=1<<sk[k][j];
for(k=0;k<SIZE;k++)
s|=1<<sk[i][k];
for(k=(i/CELL)*CELL;k<((i/CELL)*CELL+CELL);k++)
{
for(l=(j/CELL)*CELL;l<((j/CELL)*CELL+CELL);l++)
s|=1<<sk[k][l];
}
for(s>>=1,l=k=0;k<SIZE;k++)
{
if(s&(1<<k))
l++;
else
m=k;
}
if(l==(SIZE-1))
{
sk[i][j]=m+1;
sv--;
sp=1;
break;
}
}
if(sp)
break;
}
if(sp)
break;
}

} while (sv);

clk[1]=clock();

printf("\n*** Soluzione ***\n\n");

for(i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
printf("%d ",sk[i][j]);
printf("\n");
}

printf("\nTempo per ricercare la soluzione: %7.3f secondi\n",(double)(clk[1]-clk[0])/CLK_TCK);

return 0;
}


Tipico Output:


*** Input ***

0 0 0 0 0 0 0 0 0
0 0 0 0 0 3 0 8 5
0 0 1 0 2 0 0 0 0
0 0 0 5 0 7 0 0 0
0 0 4 0 0 0 1 0 0
0 9 0 0 0 0 0 0 0
5 0 0 0 0 0 0 7 3
0 0 2 0 1 0 0 0 0
0 0 0 0 4 0 0 0 9

*** Soluzione ***

9 8 7 6 5 4 3 2 1
2 4 6 1 7 3 9 8 5
3 5 1 9 2 8 7 4 6
1 2 8 5 3 7 6 9 4
6 3 4 8 9 2 1 5 7
7 9 5 4 6 1 8 3 2
5 1 9 2 8 6 4 7 3
4 7 2 3 1 9 5 6 8
8 6 3 7 4 5 2 1 9

Tempo per ricercare la soluzione: 0.000 secondi


P.S. Se riscontrare errori avvertitemi.
P.P.S. Se c'e' un numero sufficiente di persone interessare a sapere come funziona, saro' lieta di spiegarlo.

in c, difficilissimo.

[Tommo]

P.S. Se riscontrare errori avvertitemi.
P.P.S. Se c'e' un numero sufficiente di persone interessare a sapere come funziona, saro' lieta di spiegarlo.

Per me o hai un pc sperimentale oppure usi magia nera :asd:
Mi interesserebbe capire da dove iniziare per leggerlo più che altro :asd:

Ma c'è qualche "guideline" per avere dei risultati prestazionali eccellenti come fai sempre oppure serve solamente un'esperienza eccessiva? :stordita:

[rеpne scasb]

■

[rеpne scasb]

■

[d_traveler]

Affatto, il tempo stimato per scrivere il sorgente e' stato di circa 30 minuti (non ti fare impressionare c'e' un sacco di copia&incolla).

in poco tempo anche. mi sembra difficilissimo il c, io non riesco a farlo neanche in java o in python che conosco un pò meglio.

[!k-0t1c!]

Bene bene, festa delle bitmasks :D
Codice illeggibile, specie senza commenti, ma è comunque comprensibile il principio, complimenti :)

Direi che questo contest è stato risolto interessantemente, il prossimo lo penserò per qualcosa di molto parallelizzabile :cool:

P.S.: "lieta" <- donna in questo campo? doppi complimenti. Anche se qualcuno potrebbe fare la classica battuta "ecco perché scrive codice così contorto" ;)

[rеpne scasb]

■

[wingman87]

@rеpne scasb: Una domanda: gli or + shift servono a segnare in una casella che il numero corrente non può starci? Molto interessante, io nel risolvere i sudoku a mano ho sempre fatto il contrario invece con questo metodo una volta segnata la casella non devi più cancellare il segno che fai. Anche se in effetti facendolo a mano quando i segni diventano tanti diventa un po' un pasticcio...
E un'altra cosa: pensavo che senza il bruteforce non si potesse risolvere qualsiasi schema. Sbaglio?

[rеpne scasb]

■

[banryu79]

Bravissima, repne :flower:

[rеpne scasb]

■

[VICIUS]

Bravissima, repne :flower:
Vero. Non possiamo che inchinarci. :ave:

[rеpne scasb]

■

[Tommo]

E di che :sofico:

Cmq io son riuscito a risolvere tutti gli schemi che ho trovato su internet in meno di 100 ms (intorno ai 40 ms in media) sul mio E6600 @2.4ghz.
La cosa strana è che non riesco a risolvere SOLO quello nell'OP, perchè per qualche motivo non riesce a trovare alcuna soluzione soddisfacente...
però credevo che "tirando ad indovinare" si dovrebbe arrivare sempre alla soluzione completa, se si provano tutte le possibilità. :stordita:

[malocchio]

Che io sapessi il sudoku si risolve solo attraverso brute force, che sia backtracking o qualcos'altro di più stupido. La parte interessante del risolutore sta nel trovare le ottimizzazioni migliori per tagliare fuori la più grossa parte dei tentativi nel minor tempo possibile.:O

Mi sembrava di aver letto che il sudoku è un problema NP-completo.:sofico:

Proprio un questi giorni mi era venuto in mente di scrivere un risolutore, e poi mi trovo questo contest!!! :D Vedrò se al lavoro trovo il tempo :Prrr:

[bio82]

Secondo me, se il Sudoku ha una soluzione "univoca" non serve alcun bruteforce (la dimostrazione del quale, mi sta impegnando piu' del previsto). A riprova, comunque, non sono riuscita a costruire un sudoku in grado di resistere alle due tecniche combinate sopracitate.

ci sono alcuni schemi che obbligano la persona a fare guessing:

0,0,0 0,0,0 1,0,0
0,x,x 0,0,0 0,0,0
0,x,x 0,0,0 0,0,0

0,0,0 0,0,1 0,0,0
0,x,x 0,0,0 0,0,0
0,x,Y 0,0,0 0,0,0

0,0,0 0,0,0 0,0,0
0,0,0 0,0,0 0,0,0
0,0,0 0,0,0 0,0,0


metti il caso (non raro negli schemi difficili) che hai tutto fermo e l'unica mossa possibile sia quella di mettere 1 dove c'è la Y, il tuo sistema non può risolvere lo schema...

o ho capito male? saresti obbligato, finita la parte di completamento o ad implementare un'IA che sappia fare questi passaggi o il brute force...

risolto questo problema, penso che tu possa risolvere qualsiasi schema :D

bio

[rеpne scasb]

■

[rеpne scasb]

■

[gugoXX]

Per poter capire mi serve un sudoku del tipo che hai in mente. Me ne fai un esempio completo?

Ho capito, uno che finisce p.es. con

1,2,3,4
2,x,x,3
3,x,x,2
4,3,2,1

Dove nelle x si possono mettere o 4 o 1 ma ci sono 2 schemi possibili entrambi validi.

Tanto io parlo, ma non ho ancora scritto mezza riga (e chissa' quando lo faro'...)

Immagino si possano costruire schemi in cui non siano implicate solo 4 celle, ma magari di piu', con piu' possibili schemi di risposta tutti validi.

[ally]

Ho capito, uno che finisce p.es. con

1,2,3,4
2,x,x,3
3,x,x,2
4,3,2,1

Dove nelle x si possono mettere o 4 o 1 ma ci sono 2 schemi possibili entrambi validi.

Tanto io parlo, ma non ho ancora scritto mezza riga (e chissa' quando lo faro'...)

Immagino si possano costruire schemi in cui non siano implicate solo 4 celle, ma magari di piu', con piu' possibili schemi di risposta tutti validi.

...penso che la disposizione debba prevedere una sola soluzione...

...ciao Andrea...

[!k-0t1c!]

Che io sapessi il sudoku si risolve solo attraverso brute force, che sia backtracking o qualcos'altro di più stupido.
Errore, supererrore. Se vedi il sudoku come una matrice puoi scrivere un sistema di equazioni e disequazioni da soddisfare. Detto questo qualunque schema di sudoku è risolvibile senza brute forcing, risolvendo il sistema. Naturalmente il sistema può non avere soluzioni e a quel punto il sudoku è impossibile e può essere dimostrato matematicamente, altrimenti il sistema può avere una soluzione o un numero n finito di soluzioni e per trovarle non è certamente necessario il brute force :)

[ally]

...infatti...


Affinché una matrice incompleta sia considerata valida, ai fini del gioco, è necessario che la soluzione sia univoca, ovvero non devono sussistere due o più soluzioni differenti, nei quali casi il gioco viene considerato non valido. Nei casi di varianti di sudoku (p.es. killer, jigsaw, x, toroidale, ecc.) ulteriori condizioni devono essere verificate affinché la matrice risulti valida. La difficoltà di un sudoku non è data dalla quantità di numeri iniziali, bensì dalla loro disposizione.


...ciao Andrea...

[rеpne scasb]

■

[malocchio]

Errore, supererrore. Se vedi il sudoku come una matrice puoi scrivere un sistema di equazioni e disequazioni da soddisfare. Detto questo qualunque schema di sudoku è risolvibile senza brute forcing, risolvendo il sistema. Naturalmente il sistema può non avere soluzioni e a quel punto il sudoku è impossibile e può essere dimostrato matematicamente, altrimenti il sistema può avere una soluzione o un numero n finito di soluzioni e per trovarle non è certamente necessario il brute force :)

http://freeuser.org/2005/11/15/sudoku-np-completo/

http://freeuser.org/2008/01/03/sudoku-e-riducibile-a-sat-quindi-e-np-completo/

Quello che tu chiami sistema di equazioni è in realtà un SAT, problema NP-completo.;)

[rеpne scasb]

■

[DanieleC88]

Scusa se insisto: hai disponibili un sudoku a soluzione univoca, che sia risolvibile soltanto tramite brute-force?
Non ho verificato se ha effettivamente una soluzione univoca, ma questo mette in crisi il tuo algoritmo e quasi certamente richiede brute force con backtracking:
http://upload.wikimedia.org/wikipedia/en/6/6a/Star_Burst_Leo_Sudoku.JPG

[VICIUS]

Non ho verificato se ha effettivamente una soluzione univoca, ma questo mette in crisi il tuo algoritmo e quasi certamente richiede brute force con backtracking:
http://upload.wikimedia.org/wikipedia/en/6/6a/Star_Burst_Leo_Sudoku.JPG

Strano. Questo sulla mia soluzione in ruby ed è praticamente istantaneo a differenza di quello proposto da !k-0t1c! nel primo messaggio che impiega una vita.

[bio82]

settimana enigmistica di questa settimana:

0,0,7 0,0,8 0,0,0
0,1,0 0,0,0 3,0,0
0,0,0 4,0,0 0,0,9

0,8,0 0,9,0 0,0,6
0,2,0 0,0,0 0,7,0
5,0,0 0,3,0 0,4,0

9,0,0 0,0,6 0,0,0
0,0,4 0,0,0 0,1,0
0,0,0 2,0,0 8,0,0


dove le uniche 2 mosse iniziali che ho trovato (2 minuti:D) valide entrambe a schema vuoto sono:


0,4,7 0,0,8 0,0,0
0,1,0 0,0,0 3,0,0
0,0,0 4,0,0 0,0,9

0,8,0 0,9,0 0,0,6
0,2,0 0,0,0 0,7,0
5,0,0 0,3,0 0,4,0

9,0,0 0,0,6 0,0,0
0,0,4 0,0,0 0,1,0
0,0,0 2,0,0 8,9,0


questo schema non dovrebbe avere soluzione senza bruteforce o uno schema di soluzione alternativo :D

bio

[!k-0t1c!]

@DanieleC88

9,5,7,1,8,4,3,6,2
2,8,1,9,6,3,4,7,5
6,4,3,7,2,5,1,9,8
4,9,6,3,5,7,8,2,1
8,7,5,4,1,2,9,3,6
3,1,2,8,9,6,5,4,7
7,2,9,5,4,8,6,1,3
5,3,4,6,7,1,2,8,9
1,6,8,2,3,9,7,5,4
Parsed and solved in 484ms

Con la mia implementazione il tempo sembra rimanere basso e tutto funziona ;)
Vediamo un po' con cosa se ne esce repne

Edit:
per quanto riguarda quello di bio82 segue la soluzione, sempre grazie al solver usando 1po' di CP

3,4,7,9,2,8,5,6,1
2,1,9,6,7,5,3,8,4
6,5,8,4,1,3,7,2,9
7,8,1,5,9,4,2,3,6
4,2,3,8,6,1,9,7,5
5,9,6,7,3,2,1,4,8
9,3,2,1,8,6,4,5,7
8,7,4,3,5,9,6,1,2
1,6,5,2,4,7,8,9,3
Parsed and solved in 490ms

il tempo sembra inchiodato li...:D

[rеpne scasb]

■

[rеpne scasb]

■

[rеpne scasb]

■

[DanieleC88]

Studiato. Ha una soluzione univoca e il software che ho sviluppato non lo risolve. Sto apportando le relative modifiche affinche' sia risolvibile senza l'uso della forza bruta. Ti ringrazio.

Lyane.

Di niente, sono sempre interessato a studiare soluzioni così intelligenti, quindi se posso contribuire a migliorarle (per quel poco che posso fare...) lo faccio con piacere.

ciao ;)

[Vincenzo1968]

Io ho trovato codesto codice in C:

http://pubpages.unh.edu/~pas/hacks/sudoku/


#define GRIDSIZE 9
#define MAXLINE GRIDSIZE+2

unsigned int grid[GRIDSIZE][GRIDSIZE];
unsigned int col[GRIDSIZE];
unsigned int row[GRIDSIZE];
unsigned int region[GRIDSIZE];
unsigned int istack[GRIDSIZE*GRIDSIZE];
unsigned int jstack[GRIDSIZE*GRIDSIZE];
unsigned int stackp;

void grid_input(char *filename);
void grid_display();
void placenum(unsigned n, unsigned i, unsigned j);
void removenum(unsigned n, unsigned i, unsigned j);
unsigned solve();
unsigned legal(unsigned n, unsigned i, unsigned j);

int main(int argc, char **argv)
{
clock_t c_start, c_end;

c_start = clock();

grid_input(argv[1]);

grid_display();

if (solve())
{
printf("Solution found!\n");
grid_display();
}
else
{
printf("No solution found\n");
}

c_end = clock();

printf("\nTempo impiegato -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

return 0;
}

/* read initial grid from specified file */
void grid_input(char *filename) {

FILE *fp;
char line[MAXLINE];
unsigned i,j;

if ((fp = fopen(filename, "r")) == NULL)
{
fprintf(stderr, "Couldn't open input file\n");
exit(1);
}

stackp = 0;
for (i = 0; i < GRIDSIZE; i++)
{
if (fgets(line, MAXLINE, fp))
{
for (j = 0; j < GRIDSIZE; j++)
{
if (line[j] >= '1' && line[j] <= '9')
{
placenum(line[j] - '0', i, j);
}
else /* assume empty */
{
istack[stackp] = i;
jstack[stackp] = j;
stackp++;
}
}
}
else
{
fprintf(stderr, "Unexpected input error\n");
exit(1);
}
}
}

/* solve grid with current stack of empty squares */
unsigned solve()
{
int n;
int i, j;

if (stackp <= 0) { /* no empty squares so */
return 1; /* solved */
}
stackp--;
i = istack[stackp];
j = jstack[stackp];

for (n = 1; n <= 9; n++)
{
if (legal(n, i, j))
{
placenum(n, i, j);
if (solve())
{
return 1;
}
removenum(n, i, j);
}
}

/* no solution at all from this point */
stackp++;

return 0;
}


/* is it legal to put value n at row i, column j? */
unsigned legal(unsigned n, unsigned i, unsigned j) {
return (grid[i][j] == 0) &&
((row[i] & (1 << (n-1))) == 0) &&
((col[j] & (1 << (n-1))) == 0) &&
((region[3 * (i/3) + (j/3)] & (1 << (n-1))) == 0);
}

/* place number n at row i, column j */
void placenum(unsigned n, unsigned i, unsigned j) {
unsigned r;

grid[i][j] = n;
row[i] ^= (1 << (n-1));
col[j] ^= (1 << (n-1));
region[3 * (i/3) + (j/3)] ^= (1 << (n-1));
}

/* remove number n at row i, column j */
void removenum(unsigned n, unsigned i, unsigned j) {
unsigned r;

grid[i][j] = 0;
row[i] ^= (1 << (n-1));
col[j] ^= (1 << (n-1));
region[3 * (i/3) + (j/3)] ^= (1 << (n-1));
}



/* display current grid */
void grid_display()
{
unsigned i, j;

for (i = 0; i < GRIDSIZE; i++) {
for (j = 0; j < GRIDSIZE; j++) {
printf("+---");
}
printf("+\n");
for (j = 0; j < GRIDSIZE; j++) {
if (grid[i][j] == 0) {
printf("| ");
}
else {
printf("| %d ", grid[i][j]);
}
}
printf("|\n");
}
for (j = 0; j < GRIDSIZE; j++) {
printf("+---");
}
printf("+\n");
}


Questo è il risultato per il sudoku del primo post
http://www.guidealgoritmi.it/images/ImgForums/Contest15sol1.jpg

Questo è il risultato per il sudoku proposto da DanieleC88:
http://www.guidealgoritmi.it/images/ImgForums/Contest15sol2.jpg

[malocchio]

Scusa se insisto: hai disponibili un sudoku a soluzione univoca, che sia risolvibile soltanto tramite brute-force?

No, io conosco solo la teoria, non c'ho mai sbattuto la testa:banned:

Ciao :stordita:

[gugoXX]

Io non ho capito, mi fai un esempio completo 9x9 di un tale tipo di sudoku?

Pensavo che il problema fosse integrare anche sudoku a soluzione non unica, invece pare non sia cosi'.

[!k-0t1c!]

Pensavo che il problema fosse integrare anche sudoku a soluzione non unica, invece pare non sia cosi'.
Infatti in teoria sarebbe così, per quelli a soluzione multipla basta una soluzione qualunque (e questo si può fare sicuramente senza brute force).

[gugoXX]

Infatti in teoria sarebbe così, per quelli a soluzione multipla basta una soluzione qualunque (e questo si può fare sicuramente senza brute force).

Il mio problema sarebbe in questo caso quello di trovare quali sono le caselle implicate che possono avre piu' soluzioni plausibili, senza usare il backtracking, parente della forza bruta.

[rеpne scasb]

■

[!k-0t1c!]

repne, spero che se lavori in questo campo non programmi così perché nonostante la qualità indiscussa dell'algoritmo il codice è a dir poco illeggibile :)

[marco.r]

Versione prolog con risolutore per domini finiti.
Sulla mia macchina ci mette circa 0.01-0.015 secondi per gli esempi visti prima, a prescindere dalle soluzioni (e.g. togliendo valori).
Nell'esempio hard invece ci mette un bel po' di piu' :p
La maggior parte del codice e' per l'input-output :rolleyes:


charSymbol( '1', 1 ).
charSymbol( '2', 2 ).
charSymbol( '3', 3 ).
charSymbol( '4', 4 ).
charSymbol( '5', 5 ).
charSymbol( '6', 6 ).
charSymbol( '7', 7 ).
charSymbol( '8', 8 ).
charSymbol( '9', 9 ).
charSymbol( '0', N ):-
N #>= 1,
N #=< 9.

readSymbol( Stream, S ):-
get_char( Stream, C ),
charSymbol( C, S ),
get_char( Stream, _ ).

readSymbols( _ , [], 0 ).
readSymbols( Stream, [H|T], N ):-
readSymbol( Stream, H ),
M is N - 1,
readSymbols( Stream, T, M ).


readLine( Stream, Line ):-
readSymbols( Stream, Line, 9 ).

readLines( _ , [] , 0 ).
readLines( Stream, [H|T], N ):-
M is N-1,
readLine( Stream, H ),
readLines( Stream, T, M ).

readBoard( Filename, Board ):-
open( Filename, read, Stream ),
readLines( Stream, Board, 9 ),
close(Stream),
!.

printLine( [] ):-
write('\n').

printLine( [H|T] ):-
write(H),
write(' '),
printLine(T).

printBoard( [] ).
printBoard( [H|T] ):-
printLine(H),
printBoard(T).



columns( [], [], [] ).
columns( [[Cii|Cin] | C], [Cii|X],[Cin|Y]) :-
columns(C,X,Y).

transpose( [[]|_] , [] ).
transpose( M, [Ci|Cn] ):-
columns(M,Ci,R),
transpose( R, Cn ).

sum( [], 0 ).
sum( [H|T], N ):-
sum( T, M ),
N #= M + H.



rowsConstraints([]).
rowsConstraints([H|T]):-
fd_all_different(H),
sum( H, 45 ),
rowsConstraints(T).

colsConstraints(Board):-
transpose(Board,Columns),
rowsConstraints( Columns ).

dropRows( Matrix, Matrix, 0 ).
dropRows( Matrix, SubM, N ):-
M is N-1,
Matrix = [_|T],
dropRows( T, SubM, M ).

takeRows( _, [], 0 ).
takeRows( Matrix, SubM, N ):-
M is N-1,
Matrix = [H|MatrixT],
SubM = [H|SubMT],
takeRows( MatrixT, SubMT, M ).

flatten( [], [] ).
flatten( [H|T], Result ):-
flatten(T,X),
append(H,X,Result).

subMatrix( Matrix, SubM, RowBegin, ColBegin, RowLength, ColLength ):-
dropRows( Matrix, SM1, RowBegin ),
takeRows( SM1, SM2, RowLength ),
transpose(SM2,SM3),
dropRows( SM3, SM4, ColBegin ),
takeRows( SM4, SM5, ColLength ),
% transpose( SM5, SubM ).
flatten( SM5, SubM).

blocks(Board,Blocks):-
Blocks = [B1,B2,B3,B4,B5,B6,B7,B8,B9],

subMatrix(Board,B1,0,0,3,3),
subMatrix(Board,B2,0,3,3,3),
subMatrix(Board,B3,0,6,3,3),
subMatrix(Board,B4,3,0,3,3),
subMatrix(Board,B5,3,3,3,3),
subMatrix(Board,B6,3,6,3,3),
subMatrix(Board,B7,6,0,3,3),
subMatrix(Board,B8,6,3,3,3),
subMatrix(Board,B9,6,6,3,3).


blockConstraints(Board):-
blocks(Board,Blocks),
rowsConstraints( Blocks ).


constraints( Board ):-
rowsConstraints( Board ),
colsConstraints( Board ),
blockConstraints( Board ).


solve( Filename, Board ):-
readBoard( Filename, Board ),
constraints( Board ),
flatten(Board,Values),
fd_labeling( Values, [variable_method(first_fail)] ).

main:-
argument_value(1,Filename),
cpu_time(Begin),
solve(Filename,Solution),
cpu_time(End),
Time is End - Begin,
printBoard(Solution),
% write('Time needed:'),
% write(Time),
% write('\n').


:- initialization(main).

[rеpne scasb]

■

[rеpne scasb]

■

[rеpne scasb]

■

[!k-0t1c!]

Mi pare utilizzi la "forza bruta" per cercare la soluzione o sbaglio?
Non sbagli, e rischia allegramente lo stack overflow :)
Comunque buffa quella funzione CRC separata per formare CRC in ASCII art, ma trovo una cosa malsana scrivere codice in un certo modo...ghgh :cool:

[malocchio]

Mi sto allenando per questo http://www.ioccc.org/

Mi piacciono cose di questo tipo:


#include <stdio.h>
#include <stdlib.h>

int main(int a,char **A){FILE*B;typedef unsigned long C;C b
[8]; if(!(a==7&&(B= fopen(1[A],"rb")))) return 1;for(7[b]=0
;7[b]<5;7[b]++)b[7[ b]]=strtoul(A[2+7[b ]],0,16-!7[b]*6);5[
b]=3[b] ; while ((6[b]= getc(B)
)!=(C)- 1){if(2 [b])for (7[b]=0
;7[b]<4 ;7[b]++ )if(((6 [b]>>7[
b])^(6[ b]>>(7-7[b])))&1)6[ b] ^=(1
<<7[b]) ^(1<<(7-7[b]));5[b] ^= 6[b]
<<(0[b] -8);for(7[b]=0;7[b] <8;7[b]
++)if(( 5[b]>>(0[b]- 1))&1)5
[b]=(5[ b]<<1)^ 1[b]; else 5[
b]<<=1; }5[b]&=((((C)1 <<(0[b]
-1))-1) <<1)|1; if(2[b] )for(7[
b]=0;7[ b]<(0[b ]>>1);7 [b] ++)
if(((5[b]>>7[b])^(5 [b]>>(0 [b]-1-7 [b])))&1)5[b]^=((C)
1<<7[b])^((C)1<<(0[ b]-1-7[ b]));5[ b]^=4[b];fclose(B);
printf("%0*lX\n", ( int)(0[ b]+3)>> 2,5[b]); return 0;}


Ora si spiega tutto. Ma l'assembly inline non è previsto? :sofico: :ciapet:

Scusa ma che sono ste cose: 1[A] 7[b] eccetera? Un'oscura opzione del C ?!?!?

[rеpne scasb]

■

[Tommo]

in pratica ptr[i] fa *(i + ptr)... quindi funziona anche il contrario. Non ci avevo mai pensato prima.
certo davvero che brutto :asd:

[~FullSyst3m~]

Mi sto allenando per questo http://www.ioccc.org/

Mi piacciono cose di questo tipo:


#include <stdio.h>
#include <stdlib.h>

int main(int a,char **A){FILE*B;typedef unsigned long C;C b
[8]; if(!(a==7&&(B= fopen(1[A],"rb")))) return 1;for(7[b]=0
;7[b]<5;7[b]++)b[7[ b]]=strtoul(A[2+7[b ]],0,16-!7[b]*6);5[
b]=3[b] ; while ((6[b]= getc(B)
)!=(C)- 1){if(2 [b])for (7[b]=0
;7[b]<4 ;7[b]++ )if(((6 [b]>>7[
b])^(6[ b]>>(7-7[b])))&1)6[ b] ^=(1
<<7[b]) ^(1<<(7-7[b]));5[b] ^= 6[b]
<<(0[b] -8);for(7[b]=0;7[b] <8;7[b]
++)if(( 5[b]>>(0[b]- 1))&1)5
[b]=(5[ b]<<1)^ 1[b]; else 5[
b]<<=1; }5[b]&=((((C)1 <<(0[b]
-1))-1) <<1)|1; if(2[b] )for(7[
b]=0;7[ b]<(0[b ]>>1);7 [b] ++)
if(((5[b]>>7[b])^(5 [b]>>(0 [b]-1-7 [b])))&1)5[b]^=((C)
1<<7[b])^((C)1<<(0[ b]-1-7[ b]));5[ b]^=4[b];fclose(B);
printf("%0*lX\n", ( int)(0[ b]+3)>> 2,5[b]); return 0;}


Bellissimo questo codice usato per l'ASCII art.
Ma in quale direzione si dovrebbe leggere il codice? :D
Comunque credo che sia molto più difficile scrivere codice in modo da formare un'ASCII art. E bisogna essere anche davvero bravi.

[||ElChE||88]

certo davvero che brutto :asd:
Io lo trovo quasi elegante, nella sua semplicità (certo che se uno lo usa al di fuori di un contest simile a quello sopra mi viene qualche dubbio che sia un po' sadico :D).
Ma in quale direzione si dovrebbe leggere il codice? :D
Comunque credo che sia molto più difficile scrivere codice in modo da formare un'ASCII art. E bisogna essere anche davvero bravi.
Si legge normalmente (int main(int a,char **A) { FILE*B; typedef unsigned long C; C b[8]; if(!(a==... etc).
Comunque ce ne sono altri anche più impressionanti (il simulatore di volo...).

[~FullSyst3m~]

Comunque ce ne sono altri anche più impressionanti (il simulatore di volo...).

Si deve essere davvero bravi per fare cose del genere.

[malocchio]

in pratica ptr[i] fa *(i + ptr)... quindi funziona anche il contrario. Non ci avevo mai pensato prima.
certo davvero che brutto :asd:

Ecco spiegata la mia bassa considerazione del C... :stordita:

[rеpne scasb]

■

[~FullSyst3m~]

Ho corretto il bug del precedente codice. In seguito alla correzione il sudoku di DanieleC88 non era ancora risolvibile. Ho quindi aggiunto un altro metodo risolutivo basato sull'analisi del legame di 4 segni su 4 posizioni univoche. Adesso viene risolto anche il sudoku di DanieleC88. I tempi di risoluzione si sono allungati e sono sull'ordine dei 60 milionesimi di secondo.


#include <stdio.h>
#include <time.h>

#define N_CLK 2
#define INPUT_FILE_NAME "SUDOKU.DAT"
#define SIZE 9
#define CELL (SIZE/3)
#define ANY_VAL ((1<<SIZE)-1)
#define C9 126

int main(void)

{
clock_t clk[N_CLK];
FILE *input_file_handle;
int b,c1,c2,c3,i,j,k,l,m,n,o,p,q,sp,sw,sv=SIZE*SIZE,sk[SIZE][SIZE],ts[SIZE][SIZE],va[SIZE],vb[SIZE],vc[SIZE],vd[SIZE];
int cc[C9]={0x000F,0x0017,0x0027,0x0047,0x0087,0x0107,0x001B,0x002B,0x004B,0x008B,0x010B,0x0033,0x0053,0x0093,0x0113,0x0063,0x00A3,0x0123,0x00C3,0x0143,0x0183,0x001D,0x002D,0x004D,0x008D,0x010D,0x0035,0x0055,0x0095,0x0115,0x0065,0x00A5,0x0125,0x00C5,0x0145,0x0185,0x0039,0x0059,0x0099,0x0119,0x0069,0x00A9,0x0129,0x00C9,0x0149,0x0189,0x0071,0x00B1,0x0131,0x00D1,0x0151,0x0191,0x00E1,0x0161,0x01A1,0x01C1,0x001E,0x002E,0x004E,0x008E,0x010E,0x0036,0x0056,0x0096,0x0116,0x0066,0x00A6,0x0126,0x00C6,0x0146,0x0186,0x003A,0x005A,0x009A,0x011A,0x006A,0x00AA,0x012A,0x00CA,0x014A,0x018A,0x0072,0x00B2,0x0132,0x00D2,0x0152,0x0192,0x00E2,0x0162,0x01A2,0x01C2,0x003C,0x005C,0x009C,0x011C,0x006C,0x00AC,0x012C,0x00CC,0x014C,0x018C,0x0074,0x00B4,0x0134,0x00D4,0x0154,0x0194,0x00E4,0x0164,0x01A4,0x01C4,0x0078,0x00B8,0x0138,0x00D0,0x0158,0x0198,0x00E8,0x0168,0x01A8,0x01C8,0x00F0,0x0170,0x01B0,0x01D0,0x01E0};

if((input_file_handle=fopen(INPUT_FILE_NAME,"rt"))==NULL)
{
fprintf(stderr,"Non trovo il file " INPUT_FILE_NAME "\n");
return 1;
}

for(sw=sv,i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
{
fscanf(input_file_handle,"%d,",&sk[i][j]);
if(sk[i][j])
sv--;
}
}

if(fclose(input_file_handle))
{
fprintf(stderr,"Errore durante fclose\n");
return 1;
}

printf("*** Input ***\n\n");

for(i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
printf("%d ",sk[i][j]);
printf("\n");
}

clk[0]=clock();

for(i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
ts[i][j]=ANY_VAL;
}

for(i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
{
if(sk[i][j])
{
for(k=0;k<SIZE;k++)
{
ts[k][j]&=ANY_VAL-(1<<(sk[i][j]-1));
ts[i][k]&=ANY_VAL-(1<<(sk[i][j]-1));
}
for(k=(i/CELL)*CELL;k<((i/CELL)*CELL+CELL);k++)
{
for(l=(j/CELL)*CELL;l<((j/CELL)*CELL+CELL);l++)
ts[k][l]&=ANY_VAL-(1<<(sk[i][j]-1));
}
}
}
}

do
{
for(b=0;b<SIZE;b++)
{
for(i=0;i<SIZE;i++)
{
for(l=j=0;j<SIZE;j++)
{
if(sk[i][j]==0)
{
if(ts[i][j]&(1<<b))
{
l++;
m=j;
}
}
}
if(l==1)
{
sk[i][m]=b+1;
sv--;
for(k=0;k<SIZE;k++)
{
ts[k][m]&=ANY_VAL-(1<<b);
ts[i][k]&=ANY_VAL-(1<<b);
}
for(k=(i/CELL)*CELL;k<((i/CELL)*CELL+CELL);k++)
{
for(l=(m/CELL)*CELL;l<((m/CELL)*CELL+CELL);l++)
ts[k][l]&=ANY_VAL-(1<<b);
}
}
}
for(j=0;j<SIZE;j++)
{
for(l=i=0;i<SIZE;i++)
{
if(sk[i][j]==0)
{
if(ts[i][j]&(1<<b))
{
l++;
m=i;
}
}
}
if(l==1)
{
sk[m][j]=b+1;
sv--;
for(k=0;k<SIZE;k++)
{
ts[k][j]&=ANY_VAL-(1<<b);
ts[m][k]&=ANY_VAL-(1<<b);
}
for(k=(m/CELL)*CELL;k<((m/CELL)*CELL+CELL);k++)
{
for(l=(j/CELL)*CELL;l<((j/CELL)*CELL+CELL);l++)
ts[k][l]&=ANY_VAL-(1<<b);
}
}
}
for(i=0;i<SIZE;i+=CELL)
{
for(j=0;j<SIZE;j+=CELL)
{
for(n=0,k=i;k<(i+CELL);k++)
{
for(l=j;l<(j+CELL);l++)
{
if(sk[k][l]==0)
{
if(ts[k][l]&(1<<b))
{
n++;
m=k;
o=l;
}
}
}
}
if(n==1)
{
sk[m][o]=b+1;
sv--;
for(k=0;k<SIZE;k++)
{
ts[k][o]&=ANY_VAL-(1<<b);
ts[m][k]&=ANY_VAL-(1<<b);
}
for(k=(m/CELL)*CELL;k<((m/CELL)*CELL+CELL);k++)
{
for(l=(o/CELL)*CELL;l<((o/CELL)*CELL+CELL);l++)
ts[k][l]&=ANY_VAL-(1<<b);
}
}
}
}
}

for(i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
{
if(sk[i][j]==0)
{
for(k=b=0;b<SIZE;b++)
{
if(ts[i][j]&(1<<b))
{
k++;
n=b;
}
}
if(k==1)
{
sk[i][j]=n+1;
sv--;
for(k=0;k<SIZE;k++)
{
ts[k][j]&=ANY_VAL-(1<<n);
ts[i][k]&=ANY_VAL-(1<<n);
}
for(k=(i/CELL)*CELL;k<((i/CELL)*CELL+CELL);k++)
{
for(l=(j/CELL)*CELL;l<((j/CELL)*CELL+CELL);l++)
ts[k][l]&=ANY_VAL-(1<<n);
}
}
}
}
}

for(sp=i=0;i<SIZE;i++)
{
for(j=0;j<(SIZE-1);j++)
{
if(sk[i][j]==0)
{
for(n=b=0;b<SIZE;b++)
{
if(ts[i][j]&(1<<b))
n++;
}
if(n==2)
{
for(k=j+1;k<SIZE;k++)
{
if(sk[i][k]==0)
{
if(ts[i][j]==ts[i][k])
{
for(l=0;l<SIZE;l++)
{
if((l!=k)&&(l!=j)&&(sk[i][l]==0))
{
o=ts[i][l];
ts[i][l]&=~ts[i][j];
if(ts[i][l]!=o)
sp=1;
}
}
break;
}
}
}
}
}
}
}

for(j=0;j<SIZE;j++)
{
for(i=0;i<(SIZE-1);i++)
{
if(sk[i][j]==0)
{
for(n=b=0;b<SIZE;b++)
{
if(ts[i][j]&(1<<b))
n++;
}
if(n==2)
{
for(k=i+1;k<SIZE;k++)
{
if(sk[k][j]==0)
{
if(ts[i][j]==ts[k][j])
{
for(l=0;l<SIZE;l++)
{
if((l!=k)&&(l!=i)&&(sk[l][j]==0))
{
o=ts[l][j];
ts[l][j]&=~ts[i][j];
if(ts[l][j]!=o)
sp=1;
}
}
break;
}
}
}
}
}
}
}

for(i=0;i<SIZE;i+=CELL)
{
for(j=0;j<SIZE;j+=CELL)
{
for(k=i;k<(i+CELL);k++)
{
for(l=j;l<(j+CELL);l++)
{
if(sk[k][l]==0)
{
for(m=b=0;b<SIZE;b++)
{
if(ts[k][l]&(1<<b))
m++;
}
if(m==2)
{
for(m=k;m<(i+CELL);m++)
{
for(n=l+1;n<(j+CELL);n++)
{
if(sk[m][n]==0)
{
if(ts[k][l]==ts[m][n])
{
for(o=i;o<(i+CELL);o++)
{
for(p=j;p<(j+CELL);p++)
{
c1=k*SIZE+l;
c2=m*SIZE+n;
c3=o*SIZE+p;
if((c3!=c1)&&(c3!=c2)&&(sk[o][p]==0))
{
q=ts[o][p];
ts[o][p]&=~ts[k][l];
if(ts[o][p]!=q)
sp=1;
}
}
}
break;
}
}
}
}
}
}
}
}
}
}

for(i=0;i<SIZE;i++)
{
for(b=0;b<SIZE;b++)
{
for(va[b]=vb[b]=j=0;j<SIZE;j++)
{
if(sk[i][j]==0)
{
if(ts[i][j]&(1<<b))
{
va[b]|=1<<j;
vb[b]++;
}
}
}
}
for(j=0;j<(SIZE-1);j++)
{
if(vb[j]==2)
{
for(k=j+1;k<SIZE;k++)
{
if(vb[k]==2)
{
if(va[j]==va[k])
{
l=(1<<j)|(1<<k);
for(m=0;m<SIZE;m++)
{
if(va[j]&(1<<m))
{
if(ts[i][m]!=l)
sp=1;
ts[i][m]=l;
}
}
}
}
}
}
}
}

for(j=0;j<SIZE;j++)
{
for(b=0;b<SIZE;b++)
{
for(va[b]=vb[b]=i=0;i<SIZE;i++)
{
if(sk[i][j]==0)
{
if(ts[i][j]&(1<<b))
{
va[b]|=1<<i;
vb[b]++;
}
}
}
}
for(i=0;i<(SIZE-1);i++)
{
if(vb[i]==2)
{
for(k=i+1;k<SIZE;k++)
{
if(vb[k]==2)
{
if(va[i]==va[k])
{
l=(1<<i)|(1<<k);
for(m=0;m<SIZE;m++)
{
if(va[i]&(1<<m))
{
if(ts[m][j]!=l)
sp=1;
ts[m][j]=l;
}
}
}
}
}
}
}
}

for(i=0;i<SIZE;i+=CELL)
{
for(j=0;j<SIZE;j+=CELL)
{
for(q=0,k=i;k<(i+CELL);k++)
{
for(l=j;l<(j+CELL);l++,q++)
{
vc[q]=ts[k][l];
vd[q]=sk[k][l];
}
}
for(b=0;b<SIZE;b++)
{
for(va[b]=vb[b]=k=0;k<SIZE;k++)
{
if(vd[k]==0)
{
if(vc[k]&(1<<b))
{
va[b]|=1<<k;
vb[b]++;
}
}
}
}
for(k=0;k<(SIZE-1);k++)
{
if(vb[k]==2)
{
for(l=k+1;l<SIZE;l++)
{
if(vb[l]==2)
{
if(va[k]==va[l])
{
m=(1<<k)|(1<<l);
for(n=0;n<SIZE;n++)
{
if(va[k]&(1<<n))
{
if(vc[n]!=m)
sp=1;
vc[n]=m;
}
}
}
}
}
}
}
for(q=0,k=i;k<(i+CELL);k++)
{
for(l=j;l<(j+CELL);l++,q++)
ts[k][l]=vc[q];
}
}
}

for(i=0;i<SIZE;i+=CELL)
{
for(j=0;j<SIZE;j+=CELL)
{
for(b=0;b<SIZE;b++)
{
for(m=0,k=i;k<(i+CELL);k++)
{
for(l=j;l<(j+CELL);l++)
{
if(sk[k][l]==0)
{
if(ts[k][l]&(1<<b))
{
va[m]=k-i;
vb[m]=l-j;
m++;
}
}
}
}
if(m==2)
{
if(va[0]==va[1])
{
for(k=0;k<SIZE;k++)
{
if((k<j)||(k>(j+CELL)))
{
q=ts[va[0]+i][k];
ts[va[0]+i][k]&=~(1<<b);
if(q!=ts[va[0]+i][k])
sp=1;
}
}
}
if(vb[0]==vb[1])
{
for(k=0;k<SIZE;k++)
{
if((k<i)||(k>(i+CELL)))
{
q=ts[k][vb[0]+j];
ts[k][vb[0]+j]&=~(1<<b);
if(q!=ts[k][vb[0]+j])
sp=1;
}
}
}
}
if(m==3)
{
if((va[0]==va[1])&&(va[0]==va[2]))
{
for(k=0;k<SIZE;k++)
{
if((k<j)||(k>(j+CELL)))
{
q=ts[va[0]+i][k];
ts[va[0]+i][k]&=~(1<<b);
if(q!=ts[va[0]+i][k])
sp=1;
}
}
}
if((vb[0]==vb[1])&&(vb[0]==vb[2]))
{
for(k=0;k<SIZE;k++)
{
if((k<i)||(k>(i+CELL)))
{
q=ts[k][vb[0]+j];
ts[k][vb[0]+j]&=~(1<<b);
if(q!=ts[k][vb[0]+j])
sp=1;
}
}
}
}
}
}
}

if((sv==sw)&&(sp==0))
{
for(i=0;i<SIZE;i++)
{
for(q=0;q<C9;q++)
{
for(k=j=0;j<SIZE;j++)
{
if(sk[i][j]==0)
{
if((ts[i][j]|cc[q])==cc[q])
k++;
}
}
if(k==4)
{
for(j=0;j<SIZE;j++)
{
if(sk[i][j]==0)
{
if((ts[i][j]|cc[q])!=cc[q])
{
p=ts[i][j];
ts[i][j]&=~cc[q];
if(p!=ts[i][j])
sp=1;
}
}
}
}
if(sp==1)
break;
}
if(sp==1)
break;
}

if(sp==0)
{
for(j=0;j<SIZE;j++)
{
for(q=0;q<C9;q++)
{
for(k=i=0;i<SIZE;i++)
{
if(sk[i][j]==0)
{
if((ts[i][j]|cc[q])==cc[q])
k++;
}
}
if(k==4)
{
for(i=0;i<SIZE;i++)
{
if(sk[i][j]==0)
{
if((ts[i][j]|cc[q])!=cc[q])
{
p=ts[i][j];
ts[i][j]&=~cc[q];
if(p!=ts[i][j])
sp=1;
}
}
}
}
if(sp==1)
break;
}
if(sp==1)
break;
}
}
}

if((sv==sw)&&(sp==0))
{
printf("\n*** Soluzione parziale (%d) ***\n\n",sv);

for(i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
{
if(sk[i][j])
printf("%d ",sk[i][j]);
else
{
for(k=b=0;b<SIZE;b++)
{
if(ts[i][j]&(1<<b))
{
printf("%d",b+1);
k++;
}
}
for(l=0;l<(SIZE-k-2);l++)
printf(" ");
}
}
printf("\n");
}
return 1;
}
else
sw=sv;
} while (sv);

clk[1]=clock();

printf("\n*** Soluzione ***\n\n");

for(i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
printf("%d ",sk[i][j]);
printf("\n");
}

printf("\nTempo per ricercare la soluzione: %7.3f secondi\n",(double)(clk[1]-clk[0])/CLK_TCK);

return 0;
}


Che casino, mi sembra arabo :D

[malocchio]

Ho corretto il bug del precedente codice. In seguito alla correzione il sudoku di DanieleC88 non era ancora risolvibile. Ho quindi aggiunto un altro metodo risolutivo basato sull'analisi del legame di 4 segni su 4 posizioni univoche. Adesso viene risolto anche il sudoku di DanieleC88. I tempi di risoluzione si sono allungati e sono sull'ordine dei 60 milionesimi di secondo.

[CUT]


Ho due domande:

1. utilizzando questo metodo di procedimento, ovvero inserendo metodi di eliminazione/inserimento/ottimizzazione, come fa ad avere la certezza che il programma riesca a risolvere qualsiasi istanza di Sudoku?

2. perdonami ma non riesco a leggere il tuo codice, ma ho una domandina facile: hai per caso implementato una qualche sorta di stack?

[rеpne scasb]

■

[Kralizek]

resuscito questo topic per linkare questo video quanto mai azzeccato! ;)

http://www.youtube.com/watch?v=Mp8Y2yjV4fU

[skeleton]

salve a tutti,
è possibile risolvere questo sudoku in batch???
Non importa quanto tempo impiega, mi interesserebbe solo sapere il codice per farlo.

Grazie in anticipo per il vostro sicuro aiuto.

[skeleton]

up

[gugoXX]

Ecco.

Dato questo input
http://technology.amis.nl/blog/wp-content/images/250px-sudoku-by-l2g-20050714_svg.png

Una soluzione SQL, sotto Oracle che permette le query ricorsive, e' questa

with x( s, ind ) as
( select sud, instr( sud, ' ' )
from ( select '53 7 6 195 98 6 8 6 34 8 3 17 2 6 6 28 419 5 8 79' sud from dual )
union all
select substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )
, instr( s, ' ', ind + 1 )
from x
, ( select to_char( rownum ) z
from dual
connect by rownum <= 9
) z
where ind > 0
and not exists ( select null
from ( select rownum lp
from dual
connect by rownum <= 9
)
where z = substr( s, trunc( ( ind - 1 ) / 9 ) * 9 + lp, 1 )
or z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 )
or z = substr( s, mod( trunc( ( ind - 1 ) / 3 ), 3 ) * 3
+ trunc( ( ind - 1 ) / 27 ) * 27 + lp
+ trunc( ( lp - 1 ) / 3 ) * 6
, 1 )
)
)
select s
from x
where ind = 0


Come si puo' vedere, la sanita' mentale tende e a zero molto velocemente.
Il risultato eseguito:
http://technology.amis.nl/blog/wp-content/images/sqlplus.png

Ed eventualmente riprocessato
http://technology.amis.nl/blog/wp-content/images/250px-sudoku-by-l2g-20050714_solution_svg.png

http://technology.amis.nl/blog/6404/oracle-rdbms-11gr2-solving-a-sudoku-using-recursive-subquery-factoring

[malocchio]

Ecco.

Dato questo input
http://technology.amis.nl/blog/wp-content/images/250px-sudoku-by-l2g-20050714_svg.png

Una soluzione SQL, sotto Oracle che permette le query ricorsive, e' questa

with x( s, ind ) as
( select sud, instr( sud, ' ' )
from ( select '53 7 6 195 98 6 8 6 34 8 3 17 2 6 6 28 419 5 8 79' sud from dual )
union all
select substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )
, instr( s, ' ', ind + 1 )
from x
, ( select to_char( rownum ) z
from dual
connect by rownum <= 9
) z
where ind > 0
and not exists ( select null
from ( select rownum lp
from dual
connect by rownum <= 9
)
where z = substr( s, trunc( ( ind - 1 ) / 9 ) * 9 + lp, 1 )
or z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 )
or z = substr( s, mod( trunc( ( ind - 1 ) / 3 ), 3 ) * 3
+ trunc( ( ind - 1 ) / 27 ) * 27 + lp
+ trunc( ( lp - 1 ) / 3 ) * 6
, 1 )
)
)
select s
from x
where ind = 0


Come si puo' vedere, la sanita' mentale tende e a zero molto velocemente.
Il risultato eseguito:
http://technology.amis.nl/blog/wp-content/images/sqlplus.png

Ed eventualmente riprocessato
http://technology.amis.nl/blog/wp-content/images/250px-sudoku-by-l2g-20050714_solution_svg.png

http://technology.amis.nl/blog/6404/oracle-rdbms-11gr2-solving-a-sudoku-using-recursive-subquery-factoring

:sbonk:
La devo presentare alla mia prof di informatica, che crede di interndersene di db :rotfl:

[VICIUS]

Ecco.

Dato questo input
http://technology.amis.nl/blog/wp-content/images/250px-sudoku-by-l2g-20050714_svg.png

Una soluzione SQL, sotto Oracle che permette le query ricorsive, e' questa
...

Come è messo a prestazioni? I tempi sono paragonabili ad altre soluzioni scritte con sistemi più "normali"?

[gugoXX]

Come è messo a prestazioni? I tempi sono paragonabili ad altre soluzioni scritte con sistemi più "normali"?

Nono, lenta. Piu' lenta di quella in C# di almeno 10 volte.

[shinya]

Nono, lenta. Piu' lenta di quella in C# di almeno 10 volte.
Sarei curioso di vedere l'execution plan... riesci a postarlo? :) Purtroppo non ho un 11g sotto mano...

[gugoXX]

Sarei curioso di vedere l'execution plan... riesci a postarlo? :) Purtroppo non ho un 11g sotto mano...

Niente Toad per ora, e un execution plan sotto SqlPlus non lo consiglio.
Vedo cosa posso fare.
Comunque dovrebbe funzionare anche su una 8i

[shinya]

Niente Toad per ora, e un execution plan sotto SqlPlus non lo consiglio.
Vedo cosa posso fare.
Comunque dovrebbe funzionare anche su una 8i
Eh no, purtroppo il 'recursive subquery factoring' come l'hanno chiamato è una feature dell'11gR2... intendo quel "with x ... as ... select ... from x..." dove fai il 'from x' della 'x' che dichiare nella 'with'. Forse mi sono ingarbugliato con le parole..

[gugoXX]

SI', hai ragione. Non posso richiamare la With all'interno della With stessa sotto 10g.
Mi sa che dovremo aspettare per il piano d'esecuzione allora.
Immagino tante belle "Connect By Pump".

[^TiGeRShArK^]

Spettacolo! :D

Io averi preferito un calcio nei coglioni piuttosto che anche solo provare a scrivere qualcosa di simile in SQL. :asd:

[flx2000]

Mi aggiungo al coro di complimenti per rеpne scasb. Fa veramente piacere sentir parlare in italiano una persona tanto abile con gli algoritmi (e con l'offuscamento artistico del codice).
Complimenti davvero, ho visto tardi questo topic per poter partecipare al contest, ma sono felice di esserci comunque approdato per averci trovato numerose menti brillanti.

[gugoXX]

Mi aggiungo al coro di complimenti per rеpne scasb. Fa veramente piacere sentir parlare in italiano una persona tanto abile con gli algoritmi (e con l'offuscamento artistico del codice).
Complimenti davvero, ho visto tardi questo topic per poter partecipare al contest, ma sono felice di esserci comunque approdato per averci trovato numerose menti brillanti.

Comunque i contest non sono scaduti :)
Puoi sempre provare questo e anche gli altri. Sono esercizi penso interessanti, un po' al di la' anche di alcuni test universitari necessariamente focalizzati su qualche punto invece che cosi' aperti.

Qui gli altri, secondo cortese lista offerta da Vincenzo1968, il nostro segretario nonche' boia (strano accoppiamento)


Contest 1: Bitmap (http://www.hwupgrade.it/forum/showthread.php?t=1784948)

Contest 2: Ricerca (http://www.hwupgrade.it/forum/showthread.php?t=1785752)

Contest 3: La somma (http://www.hwupgrade.it/forum/showthread.php?t=1787500)

Contest 4: DNA (http://www.hwupgrade.it/forum/showthread.php?t=1791293)

Contest 5: Sottomatrici (http://www.hwupgrade.it/forum/showthread.php?t=1799059)

Contest 6: Parsing (http://www.hwupgrade.it/forum/showthread.php?t=1850150)

Contest 7: Il lotto (http://www.hwupgrade.it/forum/showthread.php?t=1839674)

Proposta (http://www.hwupgrade.it/forum/showthread.php?t=1872715)

Contest 8: Compattamento Barionico (http://www.hwupgrade.it/forum/showthread.php?t=1877648)

Contest 9: Divisori dei numeri triangolari (http://www.hwupgrade.it/forum/showthread.php?t=1882576)

Contest 10: Numeri palindormi (Semplice) (http://www.hwupgrade.it/forum/showthread.php?t=1883750)

Contest 11: Change. NP-Hard. (http://www.hwupgrade.it/forum/showthread.php?t=1884158)

Contest 12: Il muro (http://www.hwupgrade.it/forum/showthread.php?t=1890800)

Contest 13: Date (http://www.hwupgrade.it/forum/showthread.php?t=1981159)

Contest 14: Corsa delle macchine (http://www.hwupgrade.it/forum/showthread.php?t=1982858)

Contest 15: sudoku (http://www.hwupgrade.it/forum/showthread.php?t=1995326)

Contest 16: Intervalli (http://www.hwupgrade.it/forum/showthread.php?t=2006573)

Contest 17: Compilatori e interpreti. Parte I: interpreti. (http://www.hwupgrade.it/forum/showthread.php?t=2030843)


Edit: Vincenzo1968 ci tiene a fare sapere che non si ritiene un boia, ma "solo" un inquisitore.

[marco.r]

Come attivita' natalizia mi sono dedicato alla stesura di una versione in common lisp.
Backtracking con pruning dell'albero semplice semplice.
Unica furbizia la rappresentazione dei dati e un po' di ottimizzazioni sparse.

Volevo fare un po' di paragoni con gli esempi presenti su
http://en.wikipedia.org/wiki/Algorithmics_of_sudoku
ma ho avuto qualche difficolta' a far funzionare il codice degli altri.

in particolare il codice di vincenzo mi riporta uno schema diverso a quello che gli do in pasto... forse devo usare una notazione diversa ?
esempio:

# cat input4.txt
0 0 0 0 0 0 0 0 0
0 0 0 0 0 3 0 8 5
0 0 1 0 2 0 0 0 0
0 0 0 5 0 7 0 0 0
0 0 4 0 0 0 1 0 0
0 9 0 0 0 0 0 0 0
5 0 0 0 0 0 0 7 3
0 0 2 0 1 0 0 0 0
0 0 0 0 4 0 0 0 9



# ./vincenzo input4.txt
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
| 3 | | | | 8 | | 5 | | |
+---+---+---+---+---+---+---+---+---+
| | | | | 1 | | | | 2 |
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | | 5 | | |
+---+---+---+---+---+---+---+---+---+
| 7 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | 4 | | | | |
+---+---+---+---+---+---+---+---+---+


repne: la maggio parte degli esempi postati in quella pagina non vengono risolti
esempio:

*** Input ***

0 0 0 0 0 0 0 3 9
0 0 0 0 0 1 0 0 5
0 0 3 0 5 0 8 0 0
0 0 8 0 9 0 0 0 6
0 7 0 0 0 2 0 0 0
1 0 0 4 0 0 0 0 0
0 0 9 0 8 0 0 5 0
0 2 0 0 0 0 6 0 0
4 0 0 7 0 0 0 0 0

*** Soluzione parziale (60) ***

25678 14568 124567 268 2467 4678 1247 3 9
26789 4689 2467 23689 23467 1 247 2467 5
2679 1469 3 269 5 4679 8 12467 1247
235 345 8 135 9 357 123457 1247 6
3569 7 456 13568 136 2 13459 1489 1348
1 3569 256 4 367 35678 23579 2789 2378
367 136 9 1236 8 346 12347 5 12347
3578 2 157 1359 134 3459 6 14789 13478
4 13568 156 7 1236 3569 1239 1289 1238


Ally: non ho capito come formattare l'input al programma...

Vicious: non viene trovato il Modulo matrix... e' una qualche libreria disponibile ?

Sono sotto linux e non ho potuto provare la versione F# e quella Oracle. Vedo citata una versione C#, ma non trovo il codice :mbe:

Se mi spiegate come far andare gli esempi provo a compilare una tabellina,intanto questi sono i miei risultati coi problemi indicati in quella pagina.
I tempi sono il tempo medio su mille esecuzioni


processor : 1
vendor_id : GenuineIntel
cpu family : 6
model : 15
model name : Intel(R) Core(TM)2 Duo CPU T7250 @ 2.00GHz
stepping : 13
cpu MHz : 2001.000
cache size : 2048 KB
physical id : 0
siblings : 2
core id : 1
cpu cores : 2
apicid : 1
initial apicid : 1
fpu : yes
fpu_exception : yes
cpuid level : 10
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx lm constant_tsc arch_perfmon pebs bts rep_good pni dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm lahf_lm ida tpr_shadow vnmi flexpriority
bogomips : 3990.00
clflush size : 64
cache_alignment : 64
address sizes : 36 bits physical, 48 bits virtual
power management:



0 0 0 0 0 0 0 0 0
0 0 0 0 0 3 0 8 5
0 0 1 0 2 0 0 0 0
0 0 0 5 0 7 0 0 0
0 0 4 0 0 0 1 0 0
0 9 0 0 0 0 0 0 0
5 0 0 0 0 0 0 7 3
0 0 2 0 1 0 0 0 0
0 0 0 0 4 0 0 0 9

Tempo : 18.53 ms

1 0 0 0 0 0 0 0 2
0 9 0 4 0 0 0 5 0
0 0 6 0 0 0 7 0 0
0 5 0 9 0 3 0 0 0
0 0 0 0 7 0 0 0 0
0 0 0 8 5 0 0 4 0
7 0 0 0 0 0 6 0 0
0 3 0 0 0 9 0 8 0
0 0 2 0 0 0 0 0 1

Tempo: 25.55 ms

0 0 1 0 0 4 0 0 0
0 0 0 0 6 0 3 0 5
0 0 0 9 0 0 0 0 0
8 0 0 0 0 0 7 0 3
0 0 0 0 0 0 0 2 8
5 0 0 0 7 0 6 0 0
3 0 0 0 8 0 0 0 6
0 0 9 2 0 0 0 0 0
0 4 0 0 0 1 0 0 0

Tempo: 9.13 ms

9 0 0 1 0 4 0 0 2
0 8 0 0 6 0 0 7 0
0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 1
0 7 0 0 0 0 0 3 0
3 0 0 0 0 0 0 0 7
0 0 0 0 0 0 0 0 0
0 3 0 0 7 0 0 8 0
1 0 0 2 0 9 0 0 4

Tempo: 3.72 ms

0 0 1 0 0 4 0 0 0
0 0 0 0 6 0 3 0 5
0 0 0 9 0 0 0 0 0
8 0 0 0 0 0 7 0 3
0 0 0 0 0 0 0 2 8
5 0 0 0 7 0 6 0 0
3 0 0 0 8 0 0 0 6
0 0 9 2 0 0 0 0 0
0 4 0 0 0 1 0 0 0

Tempo: 9.04 ms

0 0 0 0 0 0 0 3 9
0 0 0 0 0 1 0 0 5
0 0 3 0 5 0 8 0 0
0 0 8 0 9 0 0 0 6
0 7 0 0 0 2 0 0 0
1 0 0 4 0 0 0 0 0
0 0 9 0 8 0 0 5 0
0 2 0 0 0 0 6 0 0
4 0 0 7 0 0 0 0 0

Tempo: 50.37 ms

0 2 0 4 0 3 7 0 0
0 0 0 0 0 0 0 3 2
0 0 0 0 0 0 0 0 4
0 4 0 2 0 0 0 7 0
8 0 0 0 5 0 0 0 0
0 0 0 0 0 1 0 0 0
5 0 0 0 0 0 9 0 0
0 3 0 9 0 0 0 0 7
0 0 1 0 0 8 6 0 0

Tempo: 67.96 ms

0 0 1 0 8 0 6 0 4
0 3 7 6 0 0 0 0 0
5 0 0 0 0 0 0 0 0
0 0 0 0 0 5 0 0 0
0 0 6 0 1 0 8 0 0
0 0 0 4 0 0 0 0 0
0 0 0 0 0 0 0 0 3
0 0 0 0 0 7 5 2 0
8 0 2 0 9 0 7 0 0

Tempo: 2.04 ms



E infine il codice :P


(declaim (optimize (speed 3) (debug 0) (safety 0)))

(deftype choices-length () '(integer 0 9))
(deftype choice () '(integer 1 9))
(deftype cell-pos () '(mod 81))
(deftype choices () '(cons list choices-length))
(deftype cell () '(cons choices cell-pos))
(deftype row () '(integer 0 8))
(deftype col () '(integer 0 8))
(deftype bblock () '(integer 0 8))

;;; Position related code
(defun make-pos (row col)
(+ (* row 9) col))

(defun row-of-orig (pos)
(floor pos 9))

(defparameter *row-of-table*
(make-array 81 :element-type 'row :initial-contents (loop for n below 81 collect (row-of-orig n))))

(defun row-of (pos)
(declare (type cell-pos pos)
(type (simple-array row (81)) *row-of-table*))
(the fixnum (aref *row-of-table* pos)))


(defun col-of-orig (pos)
(mod pos 9))

(defparameter *col-of-table*
(make-array 81 :element-type 'col :initial-contents (loop for n below 81 collect (col-of-orig n))))

(defun col-of (pos)
(declare (type cell-pos pos)
(type (simple-array col (81)) *col-of-table*))
(the fixnum (aref *col-of-table* pos)))


(defun block-of-orig (pos)
(let ((brow (floor (row-of pos) 3))
(bcol (floor (col-of pos) 3)))
(+ (* 3 brow) bcol)))

(defparameter *block-of-table*
(make-array 81 :element-type 'bblock :initial-contents (loop for n below 81 collect (block-of-orig n))))

(defun block-of (pos)
(declare (type cell-pos pos)
(type (simple-array bblock (81)) *block-of-table*))
(the fixnum (aref *block-of-table* pos)))


(defun same-row (pos1 pos2)
(declare (type cell-pos pos1)
(type cell-pos pos2))
(= (row-of pos1) (row-of pos2)))

(defun same-col (pos1 pos2)
(= (col-of pos1) (col-of pos2)))

(defun same-block (pos1 pos2)
(= (block-of pos1) (block-of pos2)))

(defun remove-first-choice (elem list)
(declare (type choice elem)
(type choices list))
(loop for x in (car list)
when (/= x elem)
sum 1 into n
and
collecting x into xs
finally (return (cons xs n))))

(defun remove-first-cell (elem list)
(declare (type cell elem)
(type list list))
(loop for x in (car list)
when (not (eql elem x))
collect x))


(defun values-of (x)
; (declare (type cell x)
; (optimize (speed 3) (debug 0) (safety 0)))
(car x))

(defun position-of (x)
(declare (type cell x))
(cdr x))

(defun insert-number (board pos new-value)
(declare (type cell-pos pos)
(type choice new-value))
(loop for x in board
for p = (position-of x)
for values = (values-of x)
for new-list = (cond ((eql p pos) (cons (list new-value) 1))
((same-row p pos) (remove-first-choice new-value values))
((same-col p pos) (remove-first-choice new-value values))
((same-block p pos) (remove-first-choice new-value values))
(t values))
collecting (cons new-list p)))


(defun empty-board ()
(loop for x below 81 collect (cons (cons '(1 2 3 4 5 6 7 8 9) 9) x)))

(defun read-board (filename)
(with-open-file (stream filename :direction :input)
(let ((board (empty-board)))
(loop for row from 0 below 9 do
(loop for col from 0 below 9
for number fixnum = (read stream)
when (> number 0) do
(setf board (insert-number board (make-pos row col) number))))
board)))

(defun n-of-values (x)
(declare (type cell x))
(cdr (car x)))

(defun pick-next (board)
(loop for cell in (cdr board)
with best = (first board)
and best-length = (n-of-values (first board))
and rest = ()
if (< (n-of-values cell) best-length)
do
(push best rest)
(setf best cell)
(setf best-length (n-of-values cell))
else do (push cell rest)
finally (return (list best rest))))

(defun rec-solve (count solution board)
(if (eql 81 count)
solution
(destructuring-bind (best remaining) (pick-next board)
(loop
for value in (values-of (car best))
for position = (position-of best) then (position-of best)
for sol = (rec-solve (1+ count)
(cons (list position value) solution)
(insert-number remaining position value))
do
(when sol
(return sol))))))

(defun solve (board)
(rec-solve 0 () board))

(defun print-solution (solution)
(labels ((cmp (x y) (< (first x) (first y))))
(let ((sorted (sort solution #'cmp)))
(loop for cell in sorted
do (if (= 0 (mod (1+ (first cell)) 9))
(format t "~a~%"(second cell))
(format t "~a " (second cell)))))))


(defun main (filename)
(let* ((board (read-board filename))
(solution (solve board)))
(print-solution solution)))

[DanieleC88]

Io proprio stasera ho incontrato questo...

http://scottkirkwood.blogspot.com/2006/07/shortest-sudoku-solver-in-python.html

Questo si chiama "Obfuscated Python", vero cdimauro? :p

[cdimauro]

Mai visto codice Python così brutto. :Puke:

[VICIUS]

Vicious: non viene trovato il Modulo matrix... e' una qualche libreria disponibile ?
Dovrebbe far parte della libreria standard di ruby. Sicuro di aver installato tutto bene?

[marco.r]

Dovrebbe far parte della libreria standard di ruby. Sicuro di aver installato tutto bene?

Francamente... no :D.
Ubuntu e Debian hanno la fissa di dividere le distribuzioni ufficali in piu' pacchetti, faro' una verifica.

[marco.r]

uhm, no, non riesco a trovare il pacchetto contenente il modulo indicato... qualcuno ha qualche idea ? Alla peggio mi sposto sotto windows per le prove... :S

[rеpne scasb]

■

[VICIUS]

uhm, no, non riesco a trovare il pacchetto contenente il modulo indicato... qualcuno ha qualche idea ? Alla peggio mi sposto sotto windows per le prove... :S
Prova a cambiare 'Matrix' in 'matrix' vedi mai che la ricerca su linux sia case sensitive.

[marco.r]

Questo sudoku non ha una soluzione univoca.

Io come solutione trovo solo la seguente. Te ne risultano altre ?


7,5,1,8,4,6,2,3,9
8,9,2,3,7,1,4,6,5
6,4,3,2,5,9,8,7,1
2,3,8,1,9,7,5,4,6
9,7,4,5,6,2,3,1,8
1,6,5,4,3,8,9,2,7
3,1,9,6,8,4,7,5,2
5,2,7,9,1,3,6,8,4
4,8,6,7,2,5,1,9,3

[rеpne scasb]

■