компьютеры

Кто там померяться хотел

Вроде 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(board[yCor][x]));
}
for (int xCor = 0; xCor < 9; xCor++)
{
if (candidates.indexOf(board[y][xCor]) != -1)
candidates.remove(candidates.indexOf(board[y][xCor]));
}
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(board[yCor][xCor]));
}
}
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);
}
}