Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Backtracking Problem


Audrey - Do 05.06.08 08:57
Titel: Backtracking Problem
Hallihallo,

bin neu hier.

Wir haben in einer Gruppe vor kurzem unseren ersten Backtracking Algorithmus in C# geschrieben. Leider ist das Programm noch nicht ganz fertig. Das Programm ist ein Sudoku-Prüf-Programm. Ich komm absolut nicht weiter. Kann mir jemand helfen?

Hier ist erstmal der gesamte Code. Als erstes die Programmierung die sich auf den gesamten Ablauf bezieht:


C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
using System;
using System.Windows.Forms;

namespace WindowsApplication1
{
  /// <summary>
  /// Zusammendfassende Beschreibung für classSudoku.
  /// </summary>
  public class classSudoku
  {
    public TextBox[,] sudoku = new TextBox[9,9];

    public classSudoku()
    {
    }
      //variable zum überprüfen, ob alles fertig ist!!
      private bool boFinish = false;

      //prüffunktion!!!
      public bool passtDieZahl(int x, int y) 
      {
        bool boCheck = true;
      
        if(!checkString(x, y))boCheck = false;
                if(!checkBox(x, y))  boCheck = false;
        if(!checkCol(x, y))  boCheck = false;
        if(!checkRow(x, y))  boCheck = false;

        if(checkAll()) boFinish = true;
      
        return boCheck;
      }
        
      //eingabe auf gültigkeit überprüfen!!!
      private bool checkString(int x, int y)
      {
        bool boString = true;
        string[] check = {" ","1","2","3","4","5","6","7","8","9"};

        for (int i=0; i< check.Length; i++) 
        {
          if (sudoku[x,y].Text == check[i]) 
          {
            boString = true;
            break;
          }
          else boString = false;
        }
        return boString;
      }

      //überprüfe 3x3 feld!!!
      private bool checkBox(int x, int y)
      {
        bool boBox = true;
        int r=0, c=0;
        int rows=0, cols=0;

        if(x >= 0 && x <= 2) r = 0;
        else if(x >= 3 && x <= 5) r = 3;
        else if(x >= 6 && x <= 8) r = 6;
      
        if(y >= 0 && y <= 2) c = 0;
        else if(y >= 3 && y <= 5) c = 3;
        else if(y >= 6 && y <= 8) c = 6;
      
        rows=1; cols=c;
        while(rows != r+3)
        {
          while(cols != c+3)
          {
            if(r != x && y != c) //überprüfen mit sich selbst verhinden!!!
            {
              if(sudoku[x, y].Text == sudoku[r, c].Text) //wenn die zahl in Box existiert!!!
              {
                boBox = false;
                break;
              }
            }
            cols++;
          }
          if(!boBox) break;
          rows++;
        }

        return boBox;
      }

      //spalte überprüfen!!!
      private bool checkCol(int x,int y)
      {
        bool boCol = true;
        for(int i=0; i <= 8; i++)
        {
          if(i != y) //überprüfen mit sich selbst verhinden!!!
          {
            if(sudoku[x, y].Text == sudoku[i, y].Text) //wenn die zahl in spalte existiert!!!
            {
              boCol = false;
              break;
            }
          }
        }
        return boCol;
      }
  
      //zeile überprüfen!!!
      private bool checkRow(int x,int y)
      {
        bool boRow = true;
        for(int i=0; i <= 8; i++)
        {
          if(i != x) //überprüfen mit sich selbst verhinden!!!
          {
            if(sudoku[x, y].Text == sudoku[x, i].Text) //wenn die zahl in zeile existiert!!!
            {
              boRow = false;
              break;
            }
          }
        }
        return boRow;
      }

      //überprüfe gesamtes feld!!!
      private bool checkAll()
      {
        bool boAll = true;
        for(int i=0; i <= 8; i++)
        {
          for(int j=0; j <= 8; j++)
          {
            if(sudoku[i,j].Text == " "
            {
              boAll = false;
              break;
            }
          }
          if(!boAll) break;
        }
        return boAll;
      }

    private bool findeFreiesFeld(out int i,out int j)
    {
      i=0;
      j=0;
      // Eine "for"-Schleife, die die Koordinate der X-Achse hochzählt.
      for(i = 0; i < 9; i++)
      {
        for(j = 0; j < 9; j++)
        {
          if(sudoku[i,j].Text == " ")
          {
            return true;
          }
        }
      }
      return false;
     
    }
    
    
    // Methode "macheZug" wird ausgeführt.
    public bool macheZug() 
    {
      int x,y;

      string[] werte = new string[] {"1","2","3","4","5","6","7","8","9"};
      // Die Methode "findeFreiesFeld" wird aufgerufen.
      if(findeFreiesFeld(out x,out y))
      {
        foreach(string Z in werte) 
        {
          sudoku[x,y].Text=Z;
          if(passtDieZahl(x,y) && macheZug())
            return true;
        }
      }
      return false;
    }
    }
  }



Danke schonmal im voraus :)

lg Audrey

PS: Hab noch die grafische Oberfläche als Zip angehängt


BenBE - Do 05.06.08 15:07

Wo ist das Problem?