gb0? Даю свой б-м причёсанный Питоновский и Джава код для решения головоломок Судоку. Запустить питонский код под PyPy у меня не получилось, так как я не смог поставить под PyPy библиотеку numpy. Хер её знает, чего ей было надо, что-то там не компилялось.Форматирование Джавовского кода пошло по известному месту, но в Эклипсе можно автоматически выровнять, да и javac в принципе пофигу, из какого форматирования делать класс-файл. Питонский код у меня после копипасты отсюда заработал нормально, так что вроде все пробелы на месте. В каждой из программ одна и та же головоломка. Решается она этим алгоритмом за 2 485 371 шагов.
При запуске в виртуалке под 16-й убунтой с Python 3.5.x и JDK 9 я получал следующие результаты:
Питон:
Elapsed time: 1314.434238910675 / 1890.829473565886 variants per second
Джава:
1.073778411 seconds elapsed / 2314603.2501113494 variants per second
Хотя предыдущий рекорд в 6 300 раз быстрее я не побил (видимо, на Винде Питон ещё более тормозной), но преимущество в 1 300 раз -- тоже неплохо... %)
[Python]
import numpy as np
import time
def solve(ySudoku, xSudoku):
global attempts
if attempts % 10000 == 0:
print(str(attempts) + " attempts")
print(board)
attempts = attempts + 1
nextY = -1
nextX = -1
if xSudoku == 8:
nextX = 0
nextY = ySudoku + 1
else:
nextX = xSudoku + 1
nextY = ySudoku
#base case, we stop when we reach y = 9
if ySudoku == 9:
print("Solved in " + str(attempts) + " attempts:")
print(board)
return True
if board[ySudoku][xSudoku] == 0:
candidates = np.linspace(1, 9, 9, dtype=np.int8)
for y in range(0,9):
candidates = np.delete(candidates, np.argwhere(candidates==board[y][xSudoku]
for x in range(0, 9):
candidates = np.delete(candidates, np.argwhere(candidates==board[ySudoku][x]
yQuadrant = int(ySudoku / 3)
xQuadrant = int(xSudoku / 3)
for yCor in range(yQuadrant * 3, yQuadrant * 3 + 3):
for xCor in range(xQuadrant * 3, xQuadrant * 3 + 3):
candidates = np.delete(candidates, np.argwhere(candidates==board[yCor][xCor]
if candidates.size > 0:
for candidate in candidates:
board[ySudoku][xSudoku] = candidate
if solve(nextY, nextX):
return True
else:
board[ySudoku][xSudoku] = 0
return False
else:
return False
else:
return solve(nextY, nextX)
def loadpuzzle(hints):
for y in range(0,9):
for x in range(0, 9):
board[y][x] = hints[y*9 + x];
print("Puzzle loaded")
board = np.zeros((9, 9), np.int8)
attempts = 0
puzzle = [0,0,0,0,0,0,0,0,8,0,0,3,0,0,0,4,0,0,0,9,0,0,2,0,0,6,0,0,0,0,0,7,9,0,0,0,0,0,0,0,6,1,2,0,0,0,6,0,5,0,2,0,7,0,0,0,8,0,0,0,5,0,0,0,1,0,0,0,0,0,2,0,4,0,5,0,0,0,0,0,3]
loadpuzzle(puzzle)
startTime = time.time()
solve(0,0)
elapsedTime = time.time() - startTime
print("Elapsed time: " + str(elapsedTime) + " / " + str(attempts / elapsedTime) + " variants per second")
[Java]
package mypack;
import java.util.ArrayList;
public class solver
{
static int count;
static int[][] board;
static int[] puzzle;
public static void main(String[] args)
{
count = 0;
puzzle = new int[] {0,0,0,0,0,0,0,0,8,0,0,3,0,0,0,4,0,0,0,9,0,0,2,0,0,6,0,0,0,0,0,7,9,0,0,0,0,0,0,0,6,1,2,0,0,0,6,0,5,0,2,0,7,0,0,0,8,0,0,0,5,0,0,0,1,0,0,0,0,0,2,0,4,0,5,0,0,0,0,0,3}
board = new int[9][9];
printboard();
loadboard(puzzle);
printboard();
long startTime = System.nanoTime();
solveCell(0,0);
long stopTime = System.nanoTime();
double elapsed = (stopTime - startTime) / 1000000000.0;
System.out.println(elapsed + " seconds elapsed / " + count / elapsed + " variants per second");
}
public static void printboard()
{
for (int y = 0; y < 9; y++)
{
for (int x = 0; x < 9; x++)
{
System.out.print(board[y][x] + " ");
}
System.out.println();
}
System.out.println();
}
public static void loadboard(int[] hints)
{
for (int y = 0; y < 9; y++)
{
for (int x = 0; x < 9; x++)
{
board[y][x] = hints[y*9 + x];
}
}
}
public static boolean solveCell(int y, int x)
{
if (count % 10000 == 0)
{
print("Attempt: " + count);
printboard();
}
count++;
int nextY = -1;
int nextX = -1;
if (x == 8)
{
nextX = 0;
nextY = y + 1;
}
else
{
nextX = x + 1;
nextY = y;
}
if (y == 9)
{
print("Took " + count + " attempts");
printboard();
return true;
}
if (board[y][x] == 0)
{
ArrayList<Integer> candidates = new ArrayList<Integer>();
for (int i = 1; i <= 9; i++)
{
candidates.add(i);
}
for (int yCor = 0; yCor < 9; yCor++)
{
if (candidates.indexOf(board[yCor][x]) != -1)
candidates.remove(candidates.indexOf(boa
}
for (int xCor = 0; xCor < 9; xCor++)
{
if (candidates.indexOf(board[y][xCor]) != -1)
candidates.remove(candidates.indexOf(boa
}
int yQuadrant = y / 3;
int xQuadrant = x / 3;
for (int yCor = yQuadrant * 3; yCor < yQuadrant * 3 + 3; yCor++)
{
for (int xCor = xQuadrant * 3; xCor < xQuadrant * 3 + 3; xCor++)
{
if (candidates.indexOf(board[yCor][xCor]) != -1)
candidates.remove(candidates.indexOf(boa
}
}
int candisize = candidates.size();
if (candisize > 0)
{
for (int i = 0; i < candisize; i++)
{
board[y][x] = candidates.get(i);
if (solveCell(nextY, nextX))
{
return true;
}
else
{
board[y][x] = 0;
}
}
return false;
}
else
{
return false;
}
}
else
{
return solveCell(nextY, nextX);
}
}
public static void print(String toPrint)
{
System.out.println(toPrint);
}
}
