API tools faq
paste
Guest User

Untitled

a guest
Apr 25th, 2018
85
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.27 KB | None | 0 0
raw download clone embed print report
  1. import java.util.Arrays;
  2. import java.util.HashSet;
  3. import java.util.Iterator;
  4. import java.util.Set;
  5.  
  6.  
  7. public class Sudoku {
  8.  
  9. private static final int SIZE = 9;
  10. private static final int CELL = 3;
  11. private static Set<Integer> all;
  12. private static Set<Integer> cell;
  13. private Set<Integer> mnozina1;
  14.  
  15. // public static int sudoku[][] = {
  16. // {0,3,0, 8,0,0, 0,0,0},
  17. // {9,0,5, 6,0,0, 7,0,0},
  18. // {0,0,1, 0,9,3, 2,0,0},
  19. //
  20. // {8,0,6, 5,0,0, 0,0,0},
  21. // {0,4,0, 0,3,0, 0,0,0},
  22. // {0,0,0, 0,0,0, 0,0,0},
  23. //
  24. // {4,0,2, 3,0,6, 9,5,0},
  25. // {0,1,9, 0,8,0, 0,6,0},
  26. // {3,0,8, 2,0,9, 0,1,0},
  27. // };
  28.  
  29. // public static int sudoku[][] = {
  30. // {4,7,2, 0,0,0, 0,0,0},
  31. // {1,0,5, 7,6,0, 0,0,4},
  32. // {0,0,0, 0,0,0, 0,0,0},
  33. //
  34. // {0,0,0, 0,8,0, 0,0,0},
  35. // {0,4,7, 2,0,0, 0,0,0},
  36. // {8,3,0, 4,0,1, 0,0,2},
  37. //
  38. // {5,8,0, 0,2,0, 0,7,0},
  39. // {0,0,0, 3,0,8, 0,2,9},
  40. // {0,0,4, 0,7,0, 0,1,0},
  41. //};
  42.  
  43. public static int sudoku[][] = {
  44. {0,6,2, 0,7,0, 0,0,0},
  45. {0,0,0, 0,0,0, 0,0,0},
  46. {0,4,0, 6,9,1, 0,7,0},
  47.  
  48. {8,0,1, 0,2,9, 6,0,0},
  49. {0,9,0, 0,0,7, 8,0,0},
  50. {0,0,0, 0,6,3, 5,0,0},
  51.  
  52. {3,0,0, 0,0,0, 0,0,0},
  53. {0,2,7, 0,0,0, 0,6,0},
  54. {0,1,0, 0,5,0, 0,4,0},
  55. };
  56.  
  57. public Sudoku(){
  58. all = new HashSet<Integer>();
  59. cell = new HashSet<Integer>();
  60. cell.add(0);cell.add(1);cell.add(2);
  61. for(int i = 1; i < 10; i++)
  62. all.add(i);
  63. mnozina1 = new HashSet<Integer>();
  64. }
  65.  
  66. //cislo bunky
  67. //prejst vsetky riadky okrem aktualneho
  68. //ak najde cislo v len jednom riadku zistit bunku kde chyba
  69. //skontrolovat vsety stlpce a zistit ci je len jeden kde moze byt dane cislo
  70. //dopisat cislo a opakovat pre stlpce - riadky
  71.  
  72. public void printSudoku(){
  73. System.out.println("-----------");
  74. for (int y = 0; y < SIZE; y++){
  75. for(int x = 0; x < SIZE; x++){
  76. System.out.print(sudoku[y][x]);
  77. if(x==2 || x==5)
  78. System.out.print(" ");
  79. }
  80. System.out.println();
  81. if(y==2 || y==5)
  82. System.out.println();
  83. }
  84. }
  85.  
  86. /*private int searchBunka(int sudoku[][], int cislo){
  87.  
  88. }*/
  89.  
  90. public int[][] solveSudoku(){
  91. Set<Integer> temp;
  92. int[][] polePredtym;
  93. Iterator<Integer> iterator;
  94. for(int i = 0; i < SIZE*SIZE; i++){
  95. polePredtym = sudokuCopy();
  96. for(int y = 0; y < SIZE; y++){
  97. for(int x = 0; x < SIZE; x++){
  98. if(sudoku[y][x] == 0){
  99. temp = new HashSet<Integer>(all);
  100. temp.removeAll(getMnozina1(x, y));
  101. if(temp.size() == 1){
  102. iterator = temp.iterator();
  103. sudoku[y][x] = iterator.next();
  104. }
  105. }
  106. // if(sudoku[y][x] == 0){
  107. // sudoku[y][x] = solveRowColum(x, y);
  108. // }
  109. }
  110. }
  111. if(Arrays.deepEquals(polePredtym, sudoku)){
  112. if(isSolved())
  113. System.out.printf("Suroku vyriesene pri %d prechode.\n", i);
  114. else
  115. System.out.println("Suroku nevyriesene.");
  116. return sudoku;
  117. }
  118. }
  119. System.out.println("Suroku nevyriesene.");// rozmysliet odstranenie
  120. return sudoku;
  121. }
  122.  
  123. private int[][] sudokuCopy(){
  124. int copy[][] = new int[SIZE][SIZE];
  125. for(int i = 0; i < SIZE; i++){
  126. for(int j = 0; j < SIZE; j++){
  127. copy[i][j] = sudoku[i][j];
  128. }
  129. }
  130. return copy;
  131. }
  132.  
  133. /*private int solveOne(int sudoku[][], int x, int y){
  134.  
  135. }*/
  136.  
  137. private Set<Integer> getMnozina1(int x, int y){
  138. mnozina1.clear();
  139. for(int i = 0; i < SIZE; i++)
  140. mnozina1.add(sudoku[y][i]);
  141. for(int i = 0; i < SIZE; i++)
  142. mnozina1.add(sudoku[i][x]);
  143. int cellNumb[] = getCellNumb(x, y);
  144. for(int i = cellNumb[1]*CELL; i<cellNumb[1]*CELL+CELL; i++)
  145. for(int j = cellNumb[0]*CELL; j<cellNumb[0]*CELL+CELL; j++)
  146. mnozina1.add(sudoku[i][j]);
  147. mnozina1.remove(0);
  148. return mnozina1;
  149. }
  150.  
  151. private Set<Integer> getMnozina2(int realX, int realY){
  152. Set<Integer> mnozinaR1 = new HashSet<Integer>();
  153. Set<Integer> mnozinaR2 = new HashSet<Integer>();
  154. Set<Integer> mnozinaRS = new HashSet<Integer>();
  155. Set<Integer> mnozinaS1 = new HashSet<Integer>();
  156. Set<Integer> mnozinaS2 = new HashSet<Integer>();
  157. Set<Integer> row = new HashSet<Integer>(cell);
  158. Set<Integer> column = new HashSet<Integer>(cell);
  159. int x = realX, y = realY;
  160. while(x > 2)
  161. x -= CELL;
  162. while(y > 2)
  163. y -= CELL;
  164. int cellNumb[] = getCellNumb(x, y);
  165. row.remove(y);
  166. column.remove(x);
  167. Iterator<Integer> iRow, iColumn;
  168. iRow = row.iterator();
  169. int y1Row = iRow.next(), y2Row = iRow.next();
  170. iColumn = column.iterator();
  171. int x1Column = iColumn.next(), x2Column = iColumn.next();
  172. for(int i = 0; i < SIZE; i++){
  173. mnozinaR1.add(sudoku[y1Row+cellNumb[1]*CELL][i]);
  174. mnozinaS1.add(sudoku[i][x1Column+cellNumb[0]*CELL]);
  175. mnozinaRS.add(sudoku[realY][i]);
  176. mnozinaRS.add(sudoku[i][realX]);
  177. mnozinaR2.add(sudoku[y2Row+cellNumb[1]*CELL][i]);
  178. mnozinaS2.add(sudoku[i][x2Column+cellNumb[0]*CELL]);
  179. }
  180. for(int i = cellNumb[1]*CELL; i<cellNumb[1]*CELL+CELL; i++)
  181. for(int j = cellNumb[0]*CELL; j<cellNumb[0]*CELL+CELL; j++)
  182. mnozinaRS.add(sudoku[i][j]);
  183. mnozinaR1.retainAll(mnozinaR2);
  184. mnozinaS1.retainAll(mnozinaS2);
  185. mnozinaR1.retainAll(mnozinaS1);
  186. mnozinaR1.removeAll(mnozinaRS);
  187. mnozinaR1.remove(0);
  188. return mnozinaR1;
  189. }
  190.  
  191. private int solveRowColum(int x, int y){
  192. Set<Integer> mnozinaRiadky = getRows(x, y, true);
  193. Set<Integer> mnozinaStlpce = getColumns(x, y, false);
  194. Set<Integer> mnozinaBunka = getCell(x, y);
  195. mnozinaRiadky.retainAll(mnozinaStlpce);
  196. mnozinaRiadky.removeAll(mnozinaBunka);
  197. mnozinaRiadky.remove(0);
  198. if(mnozinaRiadky.size() == 1){
  199. return (Integer)(mnozinaRiadky.toArray()[0]);
  200. }
  201. else{
  202. mnozinaRiadky = getRows(x, y, false);
  203. mnozinaStlpce = getColumns(x, y, true);
  204. mnozinaStlpce.retainAll(mnozinaRiadky);
  205. mnozinaStlpce.removeAll(mnozinaBunka);
  206. mnozinaStlpce.remove(0);
  207. if(mnozinaStlpce.size() == 1){
  208. return (Integer)(mnozinaStlpce.toArray()[0]);
  209. }
  210. else
  211. return 0;
  212. }
  213.  
  214. }
  215.  
  216. private Set<Integer> getRows(int x, int y, boolean all){
  217. boolean realyAll = all;
  218. Set<Integer> rowPos = getNextRowPos(x, y);
  219. Set<Integer> rowNumbs1 = new HashSet<Integer>();
  220. Set<Integer> rowNumbs2 = new HashSet<Integer>();
  221. Iterator<Integer> iter = rowPos.iterator();
  222. int row1 = iter.next(), row2 = iter.next();
  223. if(sudoku[row1][x] != 0 && sudoku[row2][x] != 0)
  224. realyAll = true;
  225. for(int i = 0; i < SIZE; i++){
  226. if(realyAll){
  227. rowNumbs1.add(sudoku[row1][i]);
  228. rowNumbs2.add(sudoku[row2][i]);
  229. }
  230. else{
  231. if(sudoku[row1][x] == 0)
  232. rowNumbs1.add(sudoku[row1][i]);
  233. if(sudoku[row2][x] == 0)
  234. rowNumbs2.add(sudoku[row2][i]);
  235. }
  236. }
  237. if(realyAll){
  238. rowNumbs1.retainAll(rowNumbs2);
  239. return rowNumbs1;
  240. }
  241. else{
  242. if(sudoku[row1][x] == 0){
  243. return rowNumbs1;
  244. }
  245. else{
  246. return rowNumbs2;
  247. }
  248. }
  249. }
  250.  
  251. private Set<Integer> getColumns(int x, int y, boolean all){
  252. boolean realyAll = all;
  253. Set<Integer> columnPos = getNextColumnPos(x, y);
  254. Set<Integer> columnNumbs1 = new HashSet<Integer>();
  255. Set<Integer> columnNumbs2 = new HashSet<Integer>();
  256. Iterator<Integer> iter = columnPos.iterator();
  257. int column1 = iter.next(), column2 = iter.next();
  258. if(sudoku[y][column1] != 0 && sudoku[y][column2] != 0)
  259. realyAll = true;
  260. for(int i = 0; i < SIZE; i++){
  261. if(realyAll){
  262. columnNumbs1.add(sudoku[i][column1]);
  263. columnNumbs2.add(sudoku[i][column2]);
  264. }
  265. else{
  266. if(sudoku[y][column1] == 0)
  267. columnNumbs1.add(sudoku[i][column1]);
  268. if(sudoku[y][column2] == 0)
  269. columnNumbs2.add(sudoku[i][column2]);
  270. }
  271. }
  272. if(realyAll){
  273. columnNumbs1.retainAll(columnNumbs2);
  274. return columnNumbs1;
  275. }
  276. else{
  277. if(sudoku[y][column1] == 0){
  278. return columnNumbs1;
  279. }
  280. else{
  281. return columnNumbs2;
  282. }
  283. }
  284. }
  285.  
  286. private Set<Integer> getCell(int x, int y){
  287. int cellPos[] = getCellNumb(x, y);
  288. Set<Integer> cellNumbs = new HashSet<Integer>();
  289. for(int i = cellPos[1]*CELL; i < cellPos[1]*CELL+CELL; i++)
  290. for(int j = cellPos[0]*CELL; j < cellPos[0]*CELL+CELL; j++)
  291. cellNumbs.add(sudoku[i][j]);
  292. return cellNumbs;
  293. }
  294.  
  295. private Set<Integer> getNextInRow(int x, int y){
  296. Set<Integer> rowPos = getNextRowPos(x, y);
  297. Set<Integer> nextRowNumbs = new HashSet<Integer>();
  298. Iterator<Integer> iter = rowPos.iterator();
  299. int row1 = iter.next(), row2 = iter.next();
  300. nextRowNumbs.add(sudoku[y][row1]);
  301. nextRowNumbs.add(sudoku[y][row2]);
  302. nextRowNumbs.remove(0);
  303. return nextRowNumbs;
  304. }
  305.  
  306. private Set<Integer> getNextInColumn(int x, int y){
  307. Set<Integer> columnPos = getNextRowPos(x, y);
  308. Set<Integer> nextColumnNumbs = new HashSet<Integer>();
  309. Iterator<Integer> iter = columnPos.iterator();
  310. int column1 = iter.next(), column2 = iter.next();
  311. nextColumnNumbs.add(sudoku[column1][x]);
  312. nextColumnNumbs.add(sudoku[column2][x]);
  313. nextColumnNumbs.remove(0);
  314. return nextColumnNumbs;
  315. }
  316.  
  317. private Set<Integer> getNextRowPos(int x, int y){
  318. int cellNumb[] = getCellNumb(x, y);
  319. Set<Integer> rowPos = new HashSet<Integer>();
  320. for(int i = cellNumb[1]*CELL; i < cellNumb[1]*CELL+CELL; i++){
  321. if(i == y)
  322. continue;
  323. rowPos.add(i);
  324. }
  325. return rowPos;
  326. }
  327.  
  328. private Set<Integer> getNextColumnPos(int x, int y){
  329. int cellNumb[] = getCellNumb(x, y);
  330. Set<Integer> columnPos = new HashSet<Integer>();
  331. for(int i = cellNumb[0]*CELL; i < cellNumb[0]*CELL+CELL; i++){
  332. if(i == x)
  333. continue;
  334. columnPos.add(i);
  335. }
  336. return columnPos;
  337. }
  338.  
  339. private int[] getCellNumb(int x, int y){
  340. int cell[] = {x,y};
  341. if(cell[0] < 3)
  342. cell[0] = 0;
  343. else if(cell[0] < 6)
  344. cell[0] = 1;
  345. else
  346. cell[0] = 2;
  347. if(cell[1] < 3)
  348. cell[1] = 0;
  349. else if(cell[1] < 6)
  350. cell[1] = 1;
  351. else
  352. cell[1] = 2;
  353. return cell;
  354. }
  355.  
  356. private boolean isSolved(){
  357. for(int y = 0; y < SIZE; y++)
  358. for(int x = 0; x < SIZE; x++)
  359. if(sudoku[y][x] == 0)
  360. return false;
  361. return true;
  362. }
  363.  
  364. private void print(Set<Integer> set){
  365. for(Iterator<Integer> i = set.iterator(); i.hasNext();){
  366. System.out.print(i.next() + " ");
  367. }
  368. System.out.println();
  369. }
  370.  
  371. public static void main(String args[]){
  372. Sudoku sud = new Sudoku();
  373. long stop, start = System.currentTimeMillis();
  374. sud.solveSudoku();
  375. sud.printSudoku();
  376. stop = System.currentTimeMillis();
  377. System.out.printf("Doba riesenia: %dms\n", stop-start);
  378. // sud.printSudoku();
  379. // sud.print(sud.getCell(3, 0));
  380. System.out.println(sud.solveRowColum(8, 7));
  381. }
  382. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!