API tools faq
paste
Advertisement
cd62131

Sudoku ( Number Place ) Solver 数独 ナンバープレイス 自動解答

cd62131
Nov 19th, 2013
238
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 12.54 KB | None | 0 0
raw download clone embed print report
  1. package qa6515385;
  2.  
  3. import java.util.*;
  4. import java.util.Map.Entry;
  5.  
  6. public class Main {
  7.   @SuppressWarnings("resource")
  8.   public static void main(String[] args) {
  9.     Solver s = new Solver();
  10.     StringBuilder sb = new StringBuilder();
  11.     // http://ja.wikipedia.org/wiki/数独
  12.     sb.append("5,3,0,0,7,0,0,0,0,");
  13.     sb.append("6,0,0,1,9,5,0,0,0,");
  14.     sb.append("0,9,8,0,0,0,0,6,0,");
  15.     sb.append("8,0,0,0,6,0,0,0,3,");
  16.     sb.append("4,0,0,8,0,3,0,0,1,");
  17.     sb.append("7,0,0,0,2,0,0,0,6,");
  18.     sb.append("0,6,0,0,0,0,2,8,0,");
  19.     sb.append("0,0,0,4,1,9,0,0,5,");
  20.     sb.append("0,0,0,0,8,0,0,7,9");
  21.     Scanner in = new Scanner(sb.toString()).useDelimiter("\\s*,\\s*|\\s+");
  22.     s.parse(in);
  23.     in.close();
  24.     s.solve();
  25.     System.out.println(s);
  26.     s = new Solver();
  27.     sb = new StringBuilder();
  28.     sb.append("0,0,6,0,0,1,9,0,0,");
  29.     sb.append("0,0,2,0,0,3,0,1,0,");
  30.     sb.append("0,1,5,0,9,0,0,0,0,");
  31.     sb.append("0,0,4,0,7,2,0,9,0,");
  32.     sb.append("0,9,1,0,0,0,5,2,0,");
  33.     sb.append("0,2,0,5,1,0,3,0,0,");
  34.     sb.append("0,0,0,0,2,0,6,4,0,");
  35.     sb.append("0,4,0,7,0,0,2,0,0,");
  36.     sb.append("0,0,8,9,0,0,1,0,0");
  37.     in = new Scanner(sb.toString()).useDelimiter("\\s*,\\s*|\\s+");
  38.     s.parse(in);
  39.     in.close();
  40.     s.solve();
  41.     System.out.println(s);
  42.     s = new Solver();
  43.     sb = new StringBuilder();
  44.     sb.append("5,0,0,1,0,9,4,0,0,");
  45.     sb.append("2,0,4,7,0,0,9,0,0,");
  46.     sb.append("0,8,3,0,0,2,0,7,0,");
  47.     sb.append("0,4,0,0,0,0,3,0,0,");
  48.     sb.append("0,0,0,8,0,4,0,0,0,");
  49.     sb.append("0,0,6,0,0,0,0,8,0,");
  50.     sb.append("0,9,0,3,0,0,7,2,0,");
  51.     sb.append("0,0,1,0,0,8,6,0,9,");
  52.     sb.append("0,0,2,9,0,6,0,0,3");
  53.     in = new Scanner(sb.toString()).useDelimiter("\\s*,\\s*|\\s+");
  54.     s.parse(in);
  55.     in.close();
  56.     s.solve();
  57.     System.out.println(s);
  58.   }
  59. }
  60.  
  61. class Solver {
  62.   private final Map<Coord, Cell> problem;
  63.  
  64.   public Solver() {
  65.     problem = initCell();
  66.   }
  67.  
  68.   public void parse(Scanner in) {
  69.     for (int i = 1; i <= 9; i++)
  70.       for (int j = 1; j <= 9; j++) {
  71.         int k = new Integer(in.next());
  72.         if (k == 0) continue;
  73.         Coord coord = new Coord(Numeric.toNumeric(i), Numeric.toNumeric(j));
  74.         problem().get(coord).number(Numeric.toNumeric(k));
  75.       }
  76.   }
  77.  
  78.   public Status solve() {
  79.     while (fill8())
  80.       ;
  81.     Cell c = findMin();
  82.     if (c == null) return checkConflict();
  83.     switch (checkConflict()) {
  84.       case False:
  85.         for (Numeric n: c.candidate()) {
  86.           Solver save = save();
  87.           c.number(n);
  88.           switch (solve()) {
  89.             case True:
  90.               return Status.True;
  91.             case Conflict:
  92.               reset(save);
  93.               c.remove(n);
  94.               return solve();
  95.             default:
  96.               break;
  97.           }
  98.         }
  99.       default:
  100.         return checkConflict();
  101.     }
  102.   }
  103.  
  104.   @Override
  105.   public String toString() {
  106.     StringBuilder sb = new StringBuilder();
  107.     int i = 0;
  108.     for (Entry<Coord, Cell> e: problem().entrySet()) {
  109.       Cell c = e.getValue();
  110.       if (c.hasNumber()) sb.append(c.number());
  111.       else sb.append(" ");
  112.       i++;
  113.       if (i > 9 - 1) {
  114.         sb.append("\n");
  115.         i = 0;
  116.       }
  117.     }
  118.     return sb.toString();
  119.   }
  120.  
  121.   protected Map<Coord, Cell> problem() {
  122.     return problem;
  123.   }
  124.  
  125.   static private Map<Coord, Cell> initCell() {
  126.     Map<Coord, Cell> problem = new TreeMap<Coord, Cell>();
  127.     for (Numeric i: Numeric.values())
  128.       for (Numeric j: Numeric.values()) {
  129.         Coord coord = new Coord(i, j);
  130.         Cell cell = new Cell(coord);
  131.         problem.put(coord, cell);
  132.       }
  133.     initEffect(problem);
  134.     return problem;
  135.   }
  136.  
  137.   static void initEffect(Map<Coord, Cell> problem) {
  138.     for (Entry<Coord, Cell> a: problem.entrySet())
  139.       for (Entry<Coord, Cell> b: problem.entrySet()) {
  140.         if (a.getKey().equals(b.getKey())) continue;
  141.         if (a.getKey().getRow() == b.getKey().getRow()) {
  142.           a.getValue().effect(b.getValue());
  143.           b.getValue().effect(a.getValue());
  144.         }
  145.         if (a.getKey().getColumn() == b.getKey().getColumn()) {
  146.           a.getValue().effect(b.getValue());
  147.           b.getValue().effect(a.getValue());
  148.         }
  149.         if (a.getKey().getBox() == b.getKey().getBox()) {
  150.           a.getValue().effect(b.getValue());
  151.           b.getValue().effect(a.getValue());
  152.         }
  153.       }
  154.   }
  155.  
  156.   private Status checkConflict() {
  157.     if (checkRow() == Status.Conflict) return Status.Conflict;
  158.     if (checkColumn() == Status.Conflict) return Status.Conflict;
  159.     if (checkBox() == Status.Conflict) return Status.Conflict;
  160.     for (Entry<Coord, Cell> e: problem().entrySet()) {
  161.       Cell c = e.getValue();
  162.       if (!c.hasNumber()) return Status.False;
  163.     }
  164.     return Status.True;
  165.   }
  166.  
  167.   private Status checkRow() {
  168.     for (Numeric row: Numeric.values()) {
  169.       Set<Numeric> all = EnumSet.noneOf(Numeric.class);
  170.       for (Numeric column: Numeric.values()) {
  171.         Coord coord = new Coord(row, column);
  172.         Cell c = problem().get(coord);
  173.         if (!c.hasNumber()) continue;
  174.         if (all.contains(c.number())) return Status.Conflict;
  175.         all.add(c.number());
  176.       }
  177.       Set<Numeric> rest = EnumSet.allOf(Numeric.class);
  178.       rest.removeAll(all);
  179.       for (Numeric column: Numeric.values()) {
  180.         Coord coord = new Coord(row, column);
  181.         Cell c = problem().get(coord);
  182.         if (c.hasNumber()) continue;
  183.         rest.removeAll(c.candidate());
  184.       }
  185.       if (!rest.isEmpty()) return Status.Conflict;
  186.     }
  187.     return Status.True;
  188.   }
  189.  
  190.   private Status checkColumn() {
  191.     for (Numeric column: Numeric.values()) {
  192.       Set<Numeric> all = EnumSet.noneOf(Numeric.class);
  193.       for (Numeric row: Numeric.values()) {
  194.         Coord coord = new Coord(row, column);
  195.         Cell c = problem().get(coord);
  196.         if (!c.hasNumber()) continue;
  197.         if (all.contains(c.number())) return Status.Conflict;
  198.         all.add(c.number());
  199.       }
  200.       Set<Numeric> rest = EnumSet.allOf(Numeric.class);
  201.       rest.removeAll(all);
  202.       for (Numeric row: Numeric.values()) {
  203.         Coord coord = new Coord(row, column);
  204.         Cell c = problem().get(coord);
  205.         if (c.hasNumber()) continue;
  206.         rest.removeAll(c.candidate());
  207.       }
  208.       if (!rest.isEmpty()) return Status.Conflict;
  209.     }
  210.     return Status.True;
  211.   }
  212.  
  213.   private Status checkBox() {
  214.     for (Numeric box: Numeric.values()) {
  215.       Set<Numeric> all = EnumSet.noneOf(Numeric.class);
  216.       for (Numeric row: Numeric.values()) {
  217.         for (Numeric column: Numeric.values()) {
  218.           Coord coord = new Coord(row, column);
  219.           if (coord.getBox() != box) continue;
  220.           Cell c = problem().get(coord);
  221.           if (!c.hasNumber()) continue;
  222.           if (all.contains(c.number())) return Status.Conflict;
  223.           all.add(c.number());
  224.         }
  225.       }
  226.       Set<Numeric> rest = EnumSet.allOf(Numeric.class);
  227.       rest.removeAll(all);
  228.       for (Numeric row: Numeric.values()) {
  229.         for (Numeric column: Numeric.values()) {
  230.           Coord coord = new Coord(row, column);
  231.           if (coord.getBox() != box) continue;
  232.           Cell c = problem().get(coord);
  233.           if (c.hasNumber()) continue;
  234.           rest.removeAll(c.candidate());
  235.         }
  236.       }
  237.       if (!rest.isEmpty()) return Status.Conflict;
  238.     }
  239.     return Status.True;
  240.   }
  241.  
  242.   private Solver save() {
  243.     Solver save = new Solver();
  244.     for (Entry<Coord, Cell> e: problem().entrySet()) {
  245.       Coord coord = e.getKey();
  246.       Cell cell = e.getValue();
  247.       save.problem().get(coord).candidate().clear();
  248.       save.problem().get(coord).candidate().addAll(cell.candidate());
  249.       save.problem().get(coord).number(cell.number());
  250.     }
  251.     return save;
  252.   }
  253.  
  254.   private void reset(Solver save) {
  255.     for (Entry<Coord, Cell> e: save.problem().entrySet()) {
  256.       Coord coord = e.getKey();
  257.       Cell cell = e.getValue();
  258.       problem().get(coord).candidate().clear();
  259.       problem().get(coord).candidate().addAll(cell.candidate());
  260.       problem().get(coord).number(cell.number());
  261.     }
  262.   }
  263.  
  264.   private Cell find8() {
  265.     for (Entry<Coord, Cell> e: problem().entrySet()) {
  266.       Cell c = e.getValue();
  267.       if (c.hasNumber()) continue;
  268.       if (c.candidate().size() == 1) return c;
  269.     }
  270.     return null;
  271.   }
  272.  
  273.   private boolean fill8() {
  274.     boolean ret = false;
  275.     for (Cell c = find8(); c != null; c = find8()) {
  276.       c.number(c.candidate().iterator().next());
  277.       ret = true;
  278.     }
  279.     return ret;
  280.   }
  281.  
  282.   private Cell findMin() {
  283.     Cell min = null;
  284.     int min_size = Integer.MIN_VALUE;
  285.     for (Entry<Coord, Cell> e: problem().entrySet()) {
  286.       Cell c = e.getValue();
  287.       if (c.hasNumber()) continue;
  288.       if (min == null) {
  289.         min = c;
  290.         min_size = min.candidate().size();
  291.         continue;
  292.       }
  293.       int c_size = c.candidate().size();
  294.       if (c_size >= min_size) continue;
  295.       min = c;
  296.       min_size = min.candidate().size();
  297.     }
  298.     return min;
  299.   }
  300. }
  301.  
  302. class Cell implements Comparable<Cell> {
  303.   private final Set<Cell> effect;
  304.   private final Set<Numeric> candidate;
  305.   private final Coord coord;
  306.   private Numeric number;
  307.  
  308.   public Cell(Coord coord) {
  309.     this.coord = coord;
  310.     candidate = EnumSet.allOf(Numeric.class);
  311.     effect = new TreeSet<Cell>();
  312.   }
  313.  
  314.   public int compareTo(Cell o) {
  315.     return coord().compareTo(o.coord());
  316.   }
  317.  
  318.   public boolean effect(Cell c) {
  319.     return effect.add(c);
  320.   }
  321.  
  322.   public Coord coord() {
  323.     return coord;
  324.   }
  325.  
  326.   public Set<Numeric> candidate() {
  327.     return candidate;
  328.   }
  329.  
  330.   public Set<Cell> effect() {
  331.     return effect;
  332.   }
  333.  
  334.   public Numeric number() {
  335.     return number;
  336.   }
  337.  
  338.   public void number(Numeric n) {
  339.     if (n == null) {
  340.       number = null;
  341.       return;
  342.     }
  343.     number = n;
  344.     candidate().clear();
  345.     candidate().add(n);
  346.     for (Cell c: effect())
  347.       c.remove(n);
  348.   }
  349.  
  350.   protected void remove(Numeric n) {
  351.     candidate().remove(n);
  352.   }
  353.  
  354.   public boolean hasNumber() {
  355.     return (number() != null) ? true : false;
  356.   }
  357.  
  358.   @Override
  359.   public String toString() {
  360.     StringBuilder sb = new StringBuilder();
  361.     sb.append("[" + coord());
  362.     sb.append(", n = " + number());
  363.     sb.append(", cand = " + candidate());
  364.     sb.append("]");
  365.     return sb.toString();
  366.   }
  367. }
  368.  
  369. class Coord implements Comparable<Coord> {
  370.   private final Numeric row;
  371.   private final Numeric column;
  372.   private final Numeric box;
  373.  
  374.   public Coord(Numeric row, Numeric column) {
  375.     this.row = row;
  376.     this.column = column;
  377.     box = decideBox(row.getVal(), column.getVal());
  378.   }
  379.  
  380.   private Numeric decideBox(int row, int column) {
  381.     if (row <= 3) {
  382.       if (column <= 3) return Numeric.One;
  383.       else if (column <= 6) return Numeric.Two;
  384.       else return Numeric.Three;
  385.     }
  386.     else if (row <= 6) {
  387.       if (column <= 3) return Numeric.Four;
  388.       else if (column <= 6) return Numeric.Five;
  389.       else return Numeric.Six;
  390.     }
  391.     else if (column <= 3) return Numeric.Seven;
  392.     else if (column <= 6) return Numeric.Eight;
  393.     else return Numeric.Nine;
  394.   }
  395.  
  396.   public Numeric getBox() {
  397.     return box;
  398.   }
  399.  
  400.   public Numeric getColumn() {
  401.     return column;
  402.   }
  403.  
  404.   public Numeric getRow() {
  405.     return row;
  406.   }
  407.  
  408.   public boolean equals(Coord o) {
  409.     if (this.box != o.box) return false;
  410.     if (this.column != o.column) return false;
  411.     if (this.row != o.row) return false;
  412.     return true;
  413.   }
  414.  
  415.   @Override
  416.   public String toString() {
  417.     StringBuilder sb = new StringBuilder();
  418.     sb.append("[" + row);
  419.     sb.append(", " + column);
  420.     sb.append(", " + box);
  421.     sb.append("]");
  422.     return sb.toString();
  423.   }
  424.  
  425.   public int compareTo(Coord o) {
  426.     if (row.getVal() < o.row.getVal()) return -1;
  427.     else if (row.getVal() > o.row.getVal()) return 1;
  428.     else if (column.getVal() < o.column.getVal()) return -1;
  429.     else if (column.getVal() > o.column.getVal()) return 1;
  430.     else return 0;
  431.   }
  432. }
  433.  
  434. enum Numeric {
  435.   One(1), Two(2), Three(3), Four(4), Five(5), Six(6), Seven(7), Eight(8), Nine(
  436.     9);
  437.   private int val;
  438.  
  439.   private Numeric(int val) {
  440.     this.val = val;
  441.   }
  442.  
  443.   public int getVal() {
  444.     return this.val;
  445.   }
  446.  
  447.   @Override
  448.   public String toString() {
  449.     return Integer.toString(this.getVal());
  450.   }
  451.  
  452.   public static Numeric toNumeric(int i) {
  453.     Numeric ret = null;
  454.     for (Numeric n: Numeric.values()) {
  455.       if (n.getVal() == i) {
  456.         ret = n;
  457.         break;
  458.       }
  459.     }
  460.     return ret;
  461.   }
  462. }
  463.  
  464. enum Status {
  465.   True, False, Conflict
  466. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!