|
|
|
|
Strumenti |
06-06-2009, 21:11 | #1 |
Member
Iscritto dal: Jul 2008
Messaggi: 237
|
[Vari] Contest 15
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: Codice:
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 Ultima modifica di !k-0t1c! : 07-06-2009 alle 12:07. |
06-06-2009, 23:30 | #2 | |
Senior Member
Iscritto dal: Mar 2007
Messaggi: 4660
|
Quote:
__________________
Firma eliminata e avatar cambiato. Troppa gente giudica il monaco dall'abito. |
|
07-06-2009, 01:33 | #3 |
Senior Member
Iscritto dal: Nov 2005
Messaggi: 2745
|
27 minuti e 41 secondi con Paint
|
07-06-2009, 09:44 | #4 |
Senior Member
Iscritto dal: Mar 2007
Messaggi: 4660
|
Cosa è che hai fatto con Paint?
__________________
Firma eliminata e avatar cambiato. Troppa gente giudica il monaco dall'abito. |
07-06-2009, 10:22 | #5 |
Member
Iscritto dal: Jul 2008
Messaggi: 237
|
In 27 minuti immagino si sia fatto la griglia e l'abbia risolta, ma non era lo scopo del contest...
|
07-06-2009, 11:59 | #6 |
Senior Member
Iscritto dal: Jun 2002
Città: Dublin
Messaggi: 5989
|
Non sono sicuro di aver capito bene cosa si debba fare.
Forse perché ho letto di fretta?
__________________
C'ho certi cazzi Mafa' che manco tu che sei pratica li hai visti mai! |
07-06-2009, 12:09 | #7 |
Member
Iscritto dal: Jul 2008
Messaggi: 237
|
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).
|
07-06-2009, 13:01 | #8 |
Senior Member
Iscritto dal: Jun 2002
Città: Dublin
Messaggi: 5989
|
Sì, in effetti quel "non" mi aveva abbastanza destabilizzato, me ne sfuggiva lo scopo...
Ok, in questi giorni lavorerò ad un risolutore.
__________________
C'ho certi cazzi Mafa' che manco tu che sei pratica li hai visti mai! |
07-06-2009, 14:05 | #9 | |
Senior Member
Iscritto dal: Nov 2005
Messaggi: 2745
|
Quote:
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ù. |
|
07-06-2009, 14:08 | #10 |
Senior Member
Iscritto dal: Mar 2007
Messaggi: 4660
|
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.
__________________
Firma eliminata e avatar cambiato. Troppa gente giudica il monaco dall'abito. |
07-06-2009, 16:30 | #11 | |
Member
Iscritto dal: Jul 2008
Messaggi: 237
|
Quote:
|
|
07-06-2009, 22:39 | #12 |
Senior Member
Iscritto dal: May 2004
Città: Londra (Torino)
Messaggi: 3691
|
Mi iscrivo.
Ma sono incasinato questa settimana,non so quando riusciro' a tirare giu' qualcosa.
__________________
Se pensi che il tuo codice sia troppo complesso da capire senza commenti, e' segno che molto probabilmente il tuo codice e' semplicemente mal scritto. E se pensi di avere bisogno di un nuovo commento, significa che ti manca almeno un test. |
08-06-2009, 08:32 | #13 |
Bannato
Iscritto dal: Jan 2003
Città:
Messaggi: 4420
|
...java...
Codice:
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(" -----------------------"); } } Codice:
----------------------- | 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 ...ciao Andrea... |
08-06-2009, 11:11 | #14 |
Member
Iscritto dal: Jul 2008
Messaggi: 237
|
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 |
08-06-2009, 11:21 | #15 | |
Bannato
Iscritto dal: Jan 2003
Città:
Messaggi: 4420
|
Quote:
...ciao Andrea... |
|
08-06-2009, 12:20 | #16 |
Senior Member
Iscritto dal: Oct 2007
Città: Padova
Messaggi: 4131
|
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).
Codice:
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."); } }
__________________
As long as you are basically literate in programming, you should be able to express any logical relationship you understand. If you don’t understand a logical relationship, you can use the attempt to program it as a means to learn about it. (Chris Crawford) |
08-06-2009, 12:28 | #17 |
Member
Iscritto dal: Jul 2008
Messaggi: 237
|
Aspetto ancora qualcosa di algoritmicamente più..."simpatico"
|
08-06-2009, 15:49 | #19 |
Member
Iscritto dal: Jul 2008
Messaggi: 237
|
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
|
08-06-2009, 16:03 | #20 |
Senior Member
Iscritto dal: Oct 2001
Messaggi: 11471
|
Questo è il codice:
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')) Codice:
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 Ultima modifica di VICIUS : 12-06-2009 alle 20:53. |
Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 15:49.