[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 (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~]

Originariamente inviato da !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 (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

[wingman87]

27 minuti e 41 secondi con Paint

[~FullSyst3m~]

Originariamente inviato da wingman87

27 minuti e 41 secondi con Paint

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.
Forse perché ho letto di fretta?

[!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...
Ok, in questi giorni lavorerò ad un risolutore.

[wingman87]

Originariamente inviato da !k-0t1c!

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
Scherzo naturalmente

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!]

Originariamente inviato da wingman87

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

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]

Originariamente inviato da !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

...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

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

[!k-0t1c!]

Originariamente inviato da Tommo

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

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 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?