nlothik (nlothik) wrote,
nlothik
nlothik

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

Вроде 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);
}
}


Tags: #base, программирование
Subscribe

  • Слова-паразиты

    С интересом уже давно смотрю за эволюцией русского языка, и на то, как он постоянно заимствует новые слова (преимущественно из американского…

  • Как они повидлу в карамельки засовывают

    В детстве у меня был проигрыватель для виниловых пластинок с изменяемой скоростью проигрывания. Обычный диск на 33 оборота можно было запустить на…

  • Кто это придумал?

    Ненависти Винды 11 пост! Я как сисадмин, гляжу на свойства папок практически постоянно — глядеть на закладку “безопасность” с…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments