<ignorer> Enkle Sudoku solver vha constraints

[Mr.Garibaldi]

Vennligst ignorer denne tråden. tok feil utgangspunkt, men når det ble oppklart (annet sted), så forsvant grunnlaget for tråden.

(Sudoku er NP komplett, og kan dermed ikke greie seg med kun en constraintsbasert løsning uten mye backtracking)

 

Klikk for å se/fjerne innholdet nedenfor

Hei

 

Har fått i oppgave å lage en sudoku solver med constraints, og har satt meg helt fast. Gruppen vår har allerede fått ordnet en dancing links (dlx) solver og en enkel backtracking, så vi mangler bare denne.

 

Jeg forsøker å løse sudoku ved hjelp av bitset som inneholder kun de gyldige tallene for cellen, rekken, kolonnen og feltet.

Den greier fint å sett med kun ett tall, og så oppdatere rekke/rad/felt, og på den måten finne flere tall, men den vil av en eller annen grunn ikke lete seg riktig gjennom et felt og se hvilke tall som kun går i en celle.

 

Men nok prat, mer kode:

 

Her hvor den ikke finner eneste mulige i feltet:

[EDIT] Og forsøker fjerne par fra andre celler [/EDIT]

Klikk for å se/fjerne innholdet nedenfor

private void solverField(int field){
       BitSet s = new BitSet(1); //init just to please compiler
       boolean findCell = true;
       int a = 0, b = 0; //used to store which cell is being edited at any given time
       int pairs = 0;
       HashMap hm = new HashMap();
       
       int startI = 0, endI = 0, startJ = 0, endJ = 0, cSpace = 0;
       if(field == 1){ startI = 0; endI = 3; startJ = 0; endJ = 3;} else if(field == 2) { startI = 0; endI = 3; startJ = 3; endJ = 6;} else if(field == 3) { startI = 0; endI = 3; startJ = 6; endJ = 9;} else if(field == 4) { startI = 3; endI = 6; startJ = 0; endJ = 3;} else if(field == 5) { startI = 3; endI = 6; startJ = 3; endJ = 6;} else if(field == 6) { startI = 3; endI = 6; startJ = 6; endJ = 9;} else if(field == 7) { startI = 6; endI = 9; startJ = 0; endJ = 3;} else if(field == 7) { startI = 6; endI = 9; startJ = 3; endJ = 6;} else if(field == 8) { startI = 6; endI = 9; startJ = 6; endJ = 9;}
       
       //run through each cell once.
       for(int cell = 0; cell < size; cell++){
           //run through the field to find the correct set to manipulate.
           for(int i = startI; i < endI; i++){
               for(int j = startJ; j < endJ; j++){
                   //only do something if there isn't placed anything on the board.
                   if(board[i][j] ==0){
                       //calculate which "space" I'm in...
                       if((i%3) == 0){
                           if(j < 3){ cSpace = j;} else if (j < 6){ cSpace = j - 3;} else{ cSpace = j - 6;}
                       } else if((i%3) == 1){
                           if(j < 3){ cSpace = j + 3;} else if (j < 6){ cSpace = j;} else{ cSpace = j - 3;}
                       } else{
                           if(j < 3){ cSpace = j + 6;} else if (j < 6){ cSpace = j + 3;} else{ cSpace = j;}
                       }
                       if(findCell && cSpace == cell){
                           //clone bitset of the cell
                           //System.err.println("found cell: " + i + " " + j + "");
                           s = (BitSet) spaces[i][j].clone();
                           a = i; b = j;
                           i = endI; j = endJ;
                           findCell = false;
                           if(s.cardinality() == 2){
                               hm.put(pairs, new Point(i, j));
                               pairs++;
                           }
                       }
                   }
               }
           }
           //reset findCell.
           findCell = true;
           for(int i = startI; i < endI; i++){
               for(int j = startJ; j < endJ; j++){
                   //only do something if there isn't placed anything on the board.
                   if(board[i][j] ==0){
                       //remove values which can be placed elsewhere in the field
                       if(i != a && j != b){
                           s.andNot(spaces[i][j]);
                           if(s.cardinality() ==0){
                               i = endI; j = endJ;//escape loop, set is empty
                           }
                       }
                   }
               }
           }
           //System.out.println("s.cardinality: " + s.cardinality());

           if(s.cardinality() ==1){
               //fill in the cell
               int cTemp = s.nextSetBit(0);
               board[a][b] = cTemp +1;
               spaces[a][b].clear();
               fields[field].set(cTemp, false);
               row[a].set(cTemp, false);
               col[b].set(cTemp, false);
               
               System.out.println("4Added " + board[a][b] + " in spaces["+(a+1)+"]["+(b+1)+"]");
           }
       }
       
       //remove any pairs from other cells
       if(pairs > 1){
           Point pa, pb;
           for(int i = 0; i < pairs; i++){
               //get first pair.
               pa = (Point) hm.get(i);
               //remove it from hashmap, as it is no longer needed.
               hm.remove(i);
               //run through all the other double spaces.
               for(int j = i+1; j < pairs; j++){
                   //get next point.
                   pb = (Point) hm.get(j);
                   //compare it with the first space's point.
                   if(spaces[pa.i][pa.j].equals(spaces[pb.i][pb.j])){
                       //if it has the same bits flipped, remove those bits from the other sets
                       for(int ii = startI; ii < endI; ii++){
                           for(int jj = startJ; jj < endJ; jj++){
                               if((pa.i != ii && pa.j != jj)||(pb.i != i && pb.j != jj))
                                   spaces[ii][jj].andNot(spaces[pa.i][pa.j]);
                           }
                       }
                       
                   }
               }
           }
       }//end of pair check
   }

 

Ja, er dessverre ikke verdens peneste kode, men den skulle være forståelig. Forslag til optimalisering mottaes med takk.

 

Resten av den relevante koden ligger vedlagt.

 

På forhånd takk for alle innspill, tips og hjelp, jeg setter stor pris på det.

 

[EDIT]Får ikke lagt til koden i .zip, så den får heller kopieres herfra:

Klikk for å se/fjerne innholdet nedenfor

import java.lang.Math;
/**
*
* @author Erik W. Bjoennes
*/
public class Main {
   public static void main(String[] args) {

       int[][] b;
       b = new int[9][9];
       for(int i = 0; i < 9; i++){
           for(int j = 0; j< 9; j++){
               b[i][j] = 0;
           }
       }
       b[0][1] = 2; b[0][8] = 4;
       b[1][0] = 1; b[1][6] = 3; b[1][7] = 5; b[1][8] = 7;
       b[2][1] = 7; b[2][5] = 4; b[2][7] = 2;
       b[3][4] = 1; b[3][5] = 6; b[3][8] = 3;
       b[4][1] = 3; b[4][3] = 4; b[4][5] = 7; b[4][7] = 6;
       b[5][0] = 9; b[5][3] = 2; b[5][4] = 3;
       b[6][1] = 8; b[6][3] = 5; b[6][7] = 3;
       b[7][0] = 5; b[7][1] = 1; b[7][2] = 4; b[7][8] = 8;
       b[8][0] = 6; b[8][7] = 7;
       /* Original
       b[0][5] = 7;
       b[1][3] = 8; b[1][4] = 9; b[1][6] = 3;
       b[2][1] = 3; b[2][2] = 4; b[2][6] = 5;
       b[3][0] = 1; b[3][5] = 8; b[3][7] = 6;
       b[4][1] = 7; b[4][4] = 1; b[4][7] = 4;
       b[5][1] = 8; b[5][3] = 7; b[5][8] = 2;
       b[6][2] = 5; b[6][6] = 8; b[6][7] = 2;
       b[7][2] = 9; b[7][4] = 2; b[7][5] = 4;
       b[8][3] = 6;
        **/
       
       Registeret reg = new Registeret(9, b);
       for(int i = 0; i < 9; i++){
           for(int j = 0; j < 9; j++)
               System.out.print(b[i][j] + " ");
           System.out.println();
       }
   }
   
}

Endret 1. november 2006 av Mr.Garibaldi

[Mr.Garibaldi]

Og her, siden det ble for mye for en post...

Klikk for å se/fjerne innholdet nedenfor

import java.util.BitSet;
import java.util.HashMap;
//import java.util.LinkedList;
import java.util.Set;
import java.util.Iterator;

class Registeret{
   private int size = 0;
   private int placed = 0;
   private int stackSize = 0;
   private int[][] board;
   private BitSet[][] spaces;
   private BitSet[] row;
   private BitSet[] col;
   private BitSet[] fields;

   public Registeret(int size, int[][]board){
       this.size = size;
       this.board = board;
       init();
       for(int i = 0; i < size+12; i++)
           solver();
       //while(!done()){
       // solver();
       //}
       
       for(int i = 0; i < size; i ++){
           for(int j = 0; j < size; j++){
               System.out.print("spaces["+i+"]["+j+"]: " + spaces[i][j] + "\t");
               if(j == 2 || j == 5){
                   System.out.print("\t\t");
               }
           }
           if(i == 2 || i == 5){
               System.out.println();
           }
           System.out.println();
       }

   }
   /**
    *  Initialisation method.
    **/
   private void init(){
       fields = new BitSet[size];
       row = new BitSet[size];
       col = new BitSet[size];
       spaces = new BitSet[size][size];
       //initialise the bit sets to true
       for(int i = 0; i < size; i++){
           row[i] = new BitSet(9);
           row[i].set(0, 9);
           col[i] = new BitSet(9);
           col[i].set(0, 9);
           fields[i] = new BitSet(9);
           fields[i].set(0, 9);
           for(int j = 0; j < size; j++){
               spaces[i][j] = new BitSet(size);
               spaces[i][j].set(0, size);
           }
       }
       //run through the board and remove the numbers on it from the sets
       int cField = 0;
       for(int i = 0; i < size; i++){
           for(int j = 0; j < size; j++){
               //if there is a number
               if(board[i][j] > 0){
                   //set the bits to false to show that the number is unavailable
                   //fields[i];
                   spaces[i][j].clear();
                   if(i < 3){
                       cField = (int) ((j)/3);
                   }else if(i < 6){
                       cField = (int) ((j+9)/3);
                   }else if(i < 9){
                       cField = (int) ((j+18)/3);
                   }
                   fields[cField].set(board[i][j]-1, false);
                   row[i].set(board[i][j]-1, false);
                   col[j].set(board[i][j]-1, false);
               }
           }
       }
       //the run through one more time to update each set from the rows and columns
       for(int i = 0; i < size; i++){
           for(int j = 0; j < size; j++){
               if(i < 3){
                   cField = (int) ((j)/3);
               }else if(i < 6){
                   cField = (int) ((j+9)/3);
               }else if(i < 9){
                   cField = (int) ((j+18)/3);
               }
               spaces[i][j].and(fields[cField]);
               spaces[i][j].and(row[i]);
               spaces[i][j].and(col[j]);
               if(spaces[i][j].cardinality() == 1){
                   //since only one fits, place it now!
                   int tempCell = 0;
                   
                   tempCell = spaces[i][j].nextSetBit(0);
                   board[i][j] = tempCell+1;
                   spaces[i][j].clear();
                   fields[cField].set(tempCell, false);
                   row[i].set(tempCell, false);
                   col[j].set(tempCell, false);
                   System.out.println("Added " + (tempCell+1) + " in spaces["+(i+1)+"]["+(j+1)+"]");
               }
           }
       }
       //done initiliasing
   }
   private void solver(){
       BitSet temp;
       int numPair = 0;
       HashMap hm = new HashMap();
       int cField = 0, cTemp =0;
       for(int i = 0; i < size; i++){
           for(int j = 0; j < size; j++){
               if(board[i][j] == 0){
                   if(i < 3){
                       cField = (int) ((j)/3);
                   }else if(i < 6){
                       cField = (int) ((j+9)/3);
                   }else if(i < 9){
                       cField = (int) ((j+18)/3);
                   }
                   temp = (BitSet) spaces[i][j];
                   //update bitset to make sure any changes are reflected
                   //System.out.println("temp = " + temp);
                   temp.and(row[i]);
                   //System.out.println("row = " + temp);
                   temp.and(col[j]);
                   //System.out.println("col = " + col[j);
                   temp.and(fields[cField]);
                   //System.out.println("fie = " + fields[cField]);
                   //check cardinality
                   cTemp = temp.cardinality();
                   if(cTemp == 1){
                       //place it!
                       cTemp = temp.nextSetBit(0);
                       board[i][j] = cTemp+1;
                       spaces[i][j].clear();
                       fields[cField].set(cTemp, false);
                       row[i].set(cTemp, false);
                       col[j].set(cTemp, false);
                       
                       System.out.println("1Added " + board[i][j] + " in spaces["+(i+1)+"]["+(j+1)+"]");
                   }else if (cTemp ==2){
                       //pair handling, add to solverField()
                   }else{
                       //to avoid damaging set, create a clone
                       temp = (BitSet) temp.clone();
                       BitSet temp2 = (BitSet) temp.clone();
                       for(int a = 0; a < size; a++){
                           //remove all
                           if(a != j)
                               temp.andNot(spaces[i][a]);
                           if(a != i)
                               temp2.andNot(spaces[a][j]);
                       }
                       if(temp.cardinality() ==1){
                           //place it, since it can't fit elsewhere in the coloumn
                           cTemp = temp.nextSetBit(0);
                           board[i][j] = cTemp +1;
                           fields[cField].set(cTemp, false);
                           row[i].set(cTemp, false);
                           col[j].set(cTemp, false);
                           spaces[i][j].clear();
                           System.out.println("2Added " + board[i][j] + " in spaces["+(i+1)+"]["+(j+1)+"]");
                       }
                       //needed, since the cell can have been updated by temp already.
                       if(board[i][j] == 0){
                           if(temp2.cardinality() ==1){
                               //place it, since it can't fit elsewhere in the row
                               cTemp = temp2.nextSetBit(0);
                               board[i][j] = cTemp +1;
                               fields[cField].set(cTemp, false);
                               row[i].set(cTemp, false);
                               col[j].set(cTemp, false);
                               spaces[i][j].clear();
                               System.out.println("3Added " + board[i][j] + " in spaces["+(i+1)+"]["+(j+1)+"]");
                           }
                       }
                   }
               }
           }
       }
       for(int i = 0; i < size; i++){
        solverField(1);
       }
       
   }
//kopier inn solverField() her

//checks if there are any numbers still missing from the sets
   private boolean done(){
       BitSet temp = new BitSet(size);
       temp.set(0, size, true);
       for(int i = 0; i < size; i++){
           //System.out.println("fields[" + i +"]: " + fields[i]);
           temp.or((fields[i]));
       }
       if(temp.cardinality() == 0)
           return true;
       return false;
   }
}

Endret 31. oktober 2006 av Mr.Garibaldi

[HV]

Hei

 

Kode for BackTrack?

 

offtopic: Hvordan får du koden inn i en nedtrekksliste?

 

Vennlig hilsen

HV

[pgdx]

Off topic: [ skjul]skjult tekst[ /skjul]

Endret 31. oktober 2006 av drange

[Mr.Garibaldi]

Hei

 

Kode for BackTrack?

 

7192579[/snapback]

 

Hei

 

Sorry, glemte å fjerne BackTrack helt fra koden. Gjort nå. Meningen er nemlig å lage en løsning som egentlig ikke vil bruke backtracking med mindre man må velge mellom to eller flere tall for å komme videre.

 

Så dermed er backtrackingen her veldig naiv, og bare tar ett snapshot av tilstanden til brettet (cloner alle settene, samt brettet) når det ikke er mulig å legge til ett tall noe sted, før den plasserer ett tall i ruten med minst alternativer.

 

Men det skulle ikke være nødvendig for de to test sudokuene som er hardkodet inn i programmet.

 

[EDIT]

Oops, jeg hadde lagt ved feil kode i første post. Den skulle også inneholdt par-fjerning, noe jeg av en eller annen grunn fjernet før jeg postet.

(Sånn går det når man jobber 36+ timer med 3 prosjekter :-/)

[/EDIT]

Endret 1. november 2006 av Mr.Garibaldi