Jeśli nie wiadomo o co chodzi, to chodzi o spaghetti.
sudoku - ilość rozwiązań
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: Wrocław
0
- Rejestracja: dni
- Ostatnio: dni
0
heh mój programik w C nie działał ale siadłem sobie dziś wieczorem nad tym zadankiem i wyklepałem program w C# - co ciekawe teraz już daje poprawną liczbę rozwiązań i wygląda o wiele ciekawiej
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SudokuSolver
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Autorem programu jest Pawel Lepko {0} \n", "pawel.lepko@wp.pl");
Sudoku s = new Sudoku();
s.solve();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SudokuSolver
{
/// <summary>
/// Autor: Paweł Łepko
/// </summary>
class Sudoku
{
int [,] sudokuArray;
int[,] constSudoku;
const int sudokuSize = 9;
int licznik = 0;
public Sudoku()
{
sudokuArray = new int[sudokuSize, sudokuSize]
{
{0,6,0,0,2,0,0,4,0},
{5,0,0,3,0,0,0,0,0},
{0,8,0,0,1,0,0,0,0},
{6,0,0,0,0,7,0,0,0},
{0,3,7,0,0,0,2,8,0},
{0,2,0,8,0,0,0,3,0},
{0,0,0,0,0,0,0,0,0},
{7,0,0,4,0,0,0,0,1},
{0,0,0,0,6,0,0,2,0}
};
constSudoku = new int[sudokuSize, sudokuSize];
for (int i = 0;i < sudokuSize;i++)
{
for (int j = 0;j < sudokuSize;j++)
{
constSudoku[i,j] = sudokuArray[i,j];
}
}
}
public void solve()
{
licznik = 0;
this.solveSudoku(0, 0);
Console.WriteLine("Liczba rozwiazan sudoku: " + licznik);
}
private bool sprawdzKolizje(int row, int col, int n)
{
bool colision = false;
for( int i= 0; i < sudokuSize;i++)
{
if (sudokuArray[row,i] == n)
return true;
}
for (int i = 0; i < sudokuSize; i++)
{
if (sudokuArray[i, col] == n)
return true;
}
return colision;
}
private void showSolution()
{
for (int i = 0; i < sudokuSize; i++)
{
for (int j = 0; j < sudokuSize; j++)
{
Console.Write(sudokuArray[i, j] + " ");
if ((j + 1) % 3 == 0 && j!= 0)
Console.Write(" ");
}
Console.WriteLine("");
if ((i + 1) % 3 == 0 && i != 0)
Console.WriteLine(" ");
}
}
/// <summary>
/// Czy można wstawić numerek do daneg kwadratu
/// </summary>
/// <param name="row"></param>
/// <param name="col"></param>
/// <param name="n"></param>
/// <returns></returns>
private bool canInsert(int row, int col, int n)
{
bool canInsert = true;
int rowSq = (row / 3);
int colSq = (col / 3);
int rowStart = (rowSq * 3);
int colStart = (colSq * 3);
for (int i = rowStart; i < (rowStart + 3); i++)
{
for (int j = colStart; j < (colStart + 3); j++)
{
if (sudokuArray[i, j] == n) return false;
}
}
return canInsert;
}
private void solveSudoku(int row, int col)
{
if ((sudokuArray[row, col] == 0) && (constSudoku[row, col] == 0)) // czy dane komurka sudoku jest wolna
{
for (int n = 1; n < 10; n++) // numry od 1...9
{
//sprawdzamy czy nie powoduje kolizji i czy mozna wstawić
if ((sprawdzKolizje(row, col, n) == false) && canInsert(row, col, n)) // jesli nie koluduje
{
sudokuArray[row, col] = n; // wstawiamy numerek
//to idziemy do next komórki
if ((row == (sudokuSize - 1)) && (col == (sudokuSize - 1)))
licznik++;
else if ((col + 1) < sudokuSize)
solveSudoku(row, col + 1);
else if ((row + 1) < sudokuSize)
solveSudoku(row + 1, 0);
sudokuArray[row, col] = 0;
}
}
}
else//idziemy do innej komórki
{
if ((col + 1) < sudokuSize)
solveSudoku(row, col + 1);
else if ((row + 1) < sudokuSize)
solveSudoku(row + 1, 0);
}
}
}
}
- Rejestracja: dni
- Ostatnio: dni
- Postów: 7
0
Ja nie pieprzyłbym się z C/C++/C#/Java tylko użyłbym prolog i resztę czasu przeznaczyłbym na dobrą butelkę wina. W darmowych materiałach książki[0] podany jest przepis na sudoku mniejszych wymiarów.
- Rejestracja: dni
- Ostatnio: dni
0
moje rozwiązanie w C - w przeciwieństwie do pythona działa( po włączeniu optymalizacji ) w około 1s.
#include <stdio.h>
#include <stdlib.h>
//Autor: Paweł Łepko: pawel.lepko@wp.pl
#define sudokuSize 9
int sudokuArray[sudokuSize][sudokuSize] =
{
{0,6,0,0,2,0,0,4,0},
{5,0,0,3,0,0,0,0,0},
{0,8,0,0,1,0,0,0,0},
{6,0,0,0,0,7,0,0,0},
{0,3,7,0,0,0,2,8,0},
{0,2,0,8,0,0,0,3,0},
{0,0,0,0,0,0,0,0,0},
{7,0,0,4,0,0,0,0,1},
{0,0,0,0,6,0,0,2,0}
};
int constSudoku[sudokuSize][sudokuSize];
int licznik = 0;
//dekalracje funkcji
void solve();
int sprawdzKolizje(int row, int col, int n);
int canInsert(int row, int col, int n);
void solveSudoku(int row, int col);
//definicje funkcji
void solve()
{
licznik = 0;
solveSudoku(0, 0);
printf("Liczba rozwiazan sudoku: %d \n", licznik);
}
int sprawdzKolizje(int row, int col, int n)
{
int colision = 0;
int i = 0;
for( i= 0; i < sudokuSize;i++)
{
if (sudokuArray[row][i] == n)
return 1;
}
for (i = 0; i < sudokuSize; i++)
{
if (sudokuArray[i][col] == n)
return 1;
}
return colision;
}
int canInsert(int row, int col, int n)
{
int canInsert = 1;
int i =0;
int j = 0;
int rowSq = (row / 3);
int colSq = (col / 3);
int rowStart = (rowSq * 3);
int colStart = (colSq * 3);
for (i = rowStart; i < (rowStart + 3); i++)
{
for (j = colStart; j < (colStart + 3); j++)
{
if (sudokuArray[i][j] == n) return 0;
}
}
return canInsert;
}
void solveSudoku(int row, int col)
{
if ((sudokuArray[row][col] == 0) && (constSudoku[row][col] == 0)) // czy dane komurka sudoku jest wolna
{
int n = 0;
for (n = 1; n < 10; n++) // numry od 1...9
{
//sprawdzamy czy nie powoduje kolizji i czy mozna wstawić
if ((sprawdzKolizje(row, col, n) == 0) && canInsert(row, col, n)==1) // jesli nie koluduje
{
sudokuArray[row][col] = n; // wstawiamy numerek
//to idziemy do next komórki
if ((row == (sudokuSize - 1)) && (col == (sudokuSize - 1)))
licznik++;
else if ((col + 1) < sudokuSize)
solveSudoku(row, col + 1);
else if ((row + 1) < sudokuSize)
solveSudoku(row + 1, 0);
sudokuArray[row][col] = 0;
}
}
}
else//idziemy do innej komórki
{
if ((col + 1) < sudokuSize)
solveSudoku(row, col + 1);
else if ((row + 1) < sudokuSize)
solveSudoku(row + 1, 0);
}
}
int main()
{
int i = 0;
int j = 0;
for (i = 0;i < sudokuSize;i++)
{
for (j = 0;j < sudokuSize;j++)
{
constSudoku[i][j] = sudokuArray[i][j];
}
}
printf("Autor programu: Pawel Lepko: pawel.lepko@wp.pl!\n");
solve();
system("PAUSE");
return 0;
}
- Rejestracja: dni
- Ostatnio: dni
0
a i jeszcze jedno:
funkcje sprawdzKolizje można napisać przy użyciu jednej pętli.
int sprawdzKolizje(int row, int col, int n)
{
int colision = 0;
int i = 0;
for( i= 0; i < sudokuSize;i++)
{
if (sudokuArray[row][i] == n || sudokuArray[i][col] == n)
return 1;
}
return colision;
}
- Rejestracja: dni
- Ostatnio: dni
0
@Złowieszczy:
Rozwiązanie prologowe nie jest takie krótkie:
http://user.it.uu.se/~justin/sudoku.pl
- Rejestracja: dni
- Ostatnio: dni
0
ja moje rozwiązanie w C# też pisałem około jednej godziny.
- Rejestracja: dni
- Ostatnio: dni
0
porównywać ANSI C do Pythona to tak samo jakby porównywać Karate Kyokushin do Aikido
- Rejestracja: dni
- Ostatnio: dni
0
Ja nie pieprzyłbym się z C/C++/C#/Java tylko użyłbym prolog i resztę czasu przeznaczyłbym na dobrą butelkę wina.
Rozwiązanie sudoku jest banalne, gdy ma się bibliotekę do badań operacyjnych - niezależnie od języka.
Ja napisałem niedawno coś takiego, i zajęło mi może kwadrans.
(uwaga: to nie jest gotowiec na przedstawiony problem w tym wątku, bo nie podaje ilości wszystkich rozwiązań)
// dodać referencję do Microsoft.Solver.Foundation.dll
// biblioteka do pobrania http://msdn.microsoft.com/en-us/devlabs/hh145003.aspx
using System;
using Microsoft.SolverFoundation.Services;
class SudokuApplication
{
static void Main()
{
int[,] grid = {{ 8,0,0, 4,0,6, 0,0,7 },
{ 0,0,0, 0,0,0, 4,0,0 },
{ 0,1,0, 0,0,0, 6,5,0 },
{ 6,0,9, 0,3,0, 7,8,0 },
{ 0,0,0, 0,7,0, 0,0,0 },
{ 0,4,8, 0,2,0, 1,0,3 },
{ 0,6,2, 0,0,0, 0,9,0 },
{ 0,0,1, 0,0,0, 0,0,0 },
{ 0,0,0, 9,0,2, 0,0,6 }};
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
Console.Write(grid[i, j] + " ");
Console.WriteLine();
}
Console.WriteLine();
SolverContext context = SolverContext.GetContext();
Model sudoku = context.CreateModel();
Decision[,] vars = new Decision[9, 9];
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
{
vars[i, j] = new Decision(Domain.IntegerRange(1, 9), null);
sudoku.AddDecision(vars[i, j]);
if (grid[i, j] != 0)
sudoku.AddConstraint(null, vars[i, j] == grid[i, j]);
}
for (int i = 0; i < 9; i++)
{
sudoku.AddConstraint(null, Model.AllDifferent(vars[i, 0], vars[i, 1], vars[i, 2], vars[i, 3],
vars[i, 4], vars[i, 5], vars[i, 6], vars[i, 7],
vars[i, 8]));
sudoku.AddConstraint(null, Model.AllDifferent(vars[0, i], vars[1, i], vars[2, i], vars[3, i],
vars[4, i], vars[5, i], vars[6, i], vars[7, i],
vars[8, i]));
}
for (int i = 0; i < 9; i += 3)
for (int j = 0; j < 9; j += 3)
sudoku.AddConstraint(null, Model.AllDifferent(vars[i, j], vars[i, j + 1], vars[i, j + 2],
vars[i + 1, j], vars[i + 1, j + 1], vars[i + 1, j + 2],
vars[i + 2, j], vars[i + 2, j + 1], vars[i + 2, j + 2]));
Solution solution = context.Solve();
if (solution.Quality == SolverQuality.Infeasible)
Console.WriteLine("brak rozwiązania");
else
{
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
grid[i, j] = (int)vars[i, j].ToDouble();
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
Console.Write(grid[i, j] + " ");
Console.WriteLine();
}
}
context.ClearModel();
Console.ReadKey();
}
}
- Rejestracja: dni
- Ostatnio: dni
0
z ciekawości przepisałem swoje rozwiązanie do javy żeby sprawdzić jak długo działa na przykładzie ne0. Mam procka Pentium 4- 2.8GHz oraz 2GB pamięci DDR1. Czas jaki udało mi się uzyskać to około: 1.3s.
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package sudoku;
/**
*
* @author pawel
*/
public class Sudoku
{
/**
* @param args the command line arguments
*/
public static void main(String[] args)
{
// TODO code application logic here
long end = 0;
long start = 0;
start = System.currentTimeMillis();
SudokuSolver s = new SudokuSolver();
s.solve();
end = System.currentTimeMillis();
System.out.println("Czas "+((end-start))+" s.");
}
}
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package sudoku;
/**
*
* @author pawel łepko: pawel.lepko@wp.pl
*/
public class SudokuSolver
{
private int [][] sudokuArray;
private int [][] constSudoku;
private final int sudokuSize = 9;
private int licznik = 0;
//additional variable:
private boolean canInsertV = true;
private int rowSq = 0;
private int colSq = 0;
private int rowStart = 0;
private int colStart = 0;
private int rowLimit = 0;
private int colLimit = 0;
public SudokuSolver()
{
sudokuArray = new int[][]
{
{0,6,0,0,2,0,0,4,0},
{5,0,0,3,0,0,0,0,0},
{0,8,0,0,1,0,0,0,0},
{6,0,0,0,0,7,0,0,0},
{0,3,7,0,0,0,2,8,0},
{0,2,0,8,0,0,0,3,0},
{0,0,0,0,0,0,0,0,0},
{7,0,0,4,0,0,0,0,1},
{0,0,0,0,6,0,0,2,0}
};
constSudoku = new int[sudokuSize][sudokuSize];
for (int i = 0;i < sudokuSize;i++)
{
for (int j = 0;j < sudokuSize;j++)
constSudoku[i][j] = sudokuArray[i][j];
}
}
public void solve()
{
licznik = 0;
this.solveSudoku(0, 0);
System.out.println("Liczba rozwiazan sudoku: " + licznik);
}
private boolean sprawdzKolizje(int row, int col, int n)
{
boolean colision = false;
for( int i= 0; i < sudokuSize;i++)
{
if (sudokuArray[row][i] == n || sudokuArray[i][col] == n)
return true;
}
return colision;
}
private boolean canInsert(int row, int col, int n)
{
canInsertV = true;
rowSq = (row / 3);
colSq = (col / 3);
rowStart = (rowSq * 3);
colStart = (colSq * 3);
rowLimit = rowStart + 3;
colLimit = colStart + 3;
for (int i = rowStart; i < (rowLimit); i++)
{
for (int j = colStart; j < (colLimit); j++)
if (sudokuArray[i][j] == n) return false;
}
return canInsertV;
}
private void solveSudoku(int row, int col)
{
if ((sudokuArray[row][col] == 0) && (constSudoku[row][col] == 0)) // czy dane komurka sudoku jest wolna
{
for (int n = 1; n < 10; n++) // numry od 1...9
{
//sprawdzamy czy nie powoduje kolizji i czy mozna wstawić
if ((sprawdzKolizje(row, col, n) == false) && canInsert(row, col, n)) // jesli nie koluduje
{
sudokuArray[row][col] = n; // wstawiamy numerek
//to idziemy do next komórki
if ((row == (sudokuSize - 1)) && (col == (sudokuSize - 1)))
licznik++;
else if ((col + 1) < sudokuSize)
solveSudoku(row, col + 1);
else if ((row + 1) < sudokuSize)
solveSudoku(row + 1, 0);
sudokuArray[row][col] = 0;
}
}
}
else//idziemy do innej komórki
{
if ((col + 1) < sudokuSize)
solveSudoku(row, col + 1);
else if ((row + 1) < sudokuSize)
solveSudoku(row + 1, 0);
}
}
}
- Rejestracja: dni
- Ostatnio: dni
0
nie wiem o co chodzi z tą pracą ale wydaję mi się że jak ktoś rekrutuję nowego pracownika to w firmie a nie zdalnie przez internet.
- Rejestracja: dni
- Ostatnio: dni
0
ogloszeniowiec napisał(a)
Mam wasze IP, wy już pracy a all... nie dostaniecie! Pozdrawiam :P
Masz ich protokoły internetowe? Z Comarchu się urwałeś?
- Rejestracja: dni
- Ostatnio: dni
0
Na maszynie z procesorem Pentium4 2.8Ghz i 2GB DDR1:
Czas znalezienia wszystkich rozwiązań sudoku:
Java: 1.3 sec
ANSI C: 0.45 sec
C#: (TimeSpan.Miliseconds = 734, TimeSpan.TotalMilliseconds = 1703,125)
- Rejestracja: dni
- Ostatnio: dni
0
Dopowiedz mi, proszę, na kilka pytań:
Skąd wiadomo, że w wyniku nie będzie powtórzonych rozwiązań? Bo numerek iteracji inny...?
Skąd wiesz, że wszystkie plansze tego sudoku zostały odnalezione?? Bo program zakończył działanie??
Pozdrawiam
- Rejestracja: dni
- Ostatnio: dni
0
Widzę twoje szybkie rozwiązanie w Ansi C (0,18 s) i podbijam moim rozwiązaniem w C++ (0,07 s, http://pastebin.com/usStpNiq). Takie same opcje optymalizatora (-O3, -march=native). Najśmieszniejsze jest to, że rozwiązanie w C++ jest 200 razy szybsze niż pythonowe ;).
- Rejestracja: dni
- Ostatnio: dni
0
to spróbuj tego:
clock_t start, end;
start = clock();
solve();.....................................
end = clock();
elapsed = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("Czas: %f \n", elapsed);
- Rejestracja: dni
- Ostatnio: dni
0
Algorytm który używam sprawdza po kolei wszystkie możliwe rozwiązania (w porządku leksykograficznym), odrzucając jak najszybciej możliwości bezcelowe, przykładowo jeżeli wiadomo, że rozwiązanie w postaci (1,2,.........) jest na pewno nieprawidłowe (dwójka nie pasuje) to sprawdza (1,3,.......). Tym sposobem przechodzi przez wszystkie możliwe rozwiązania.
- Rejestracja: dni
- Ostatnio: dni
0
A jeśli zacznę rozwiązywanie planszy od środkowej górnej komórki (3x3)??
To sprawi, że w górnej lewej komórce wystąpią inne liczby (niż przy liczeniu od lewej).
Czy ten wariant będzie brany pod uwagę?
- Rejestracja: dni
- Ostatnio: dni
0
mój program wyszukuję wszystkie możliwe rozwiązania dlatego też nie ma znaczenia od której komórki zaczniesz wyszukiwanie. Ważne aby program odwiedził każde pole oprócz tych które zostały ustawione na stałe.
- Rejestracja: dni
- Ostatnio: dni
0
ciekawe testy na temat sudoku:
http://attractivechaos.wordpress.com/2011/06/19/an-incomplete-review-of-sudoku-solver-implementations/
to jest dopiero sudoku:
http://magictour.free.fr/topn87
- Rejestracja: dni
- Ostatnio: dni
0
I tak do mnie już zdzwonili ;)