Lechler’s Website:

START:               
pfeilw
                  

Status 10.1.16

   Ratz Fatz: Inhalt / Content:

 

 

Sudoku mit logischer Algebra lösen.

Das Lösen eines Sudokurätsels ist oft eine rechte Bastelei, wenn man endlich fertig ist, passt schließlich die letzt Zahl nicht, und man muss noch mal von vorne anfangen. Im folgenden Text, wird eine Lösungsmethode beschrieben, die auf logischem Vergleich basiert und ohne komplizierte Formelrechnung immer zur Lösung führt. Diese Methode stammt aus der Digitalelektronik.

1: Das Rätsel

Bild1 zeigt das Rätsel, es hat 9 Zeilen (A-J) und 9 Spalten (1-9). Jede Zeile hat neun Felder und jede Spalte hat neun Felder, also insgesamt 81 Felder. Je 3Zeilen und 3 Spalten bilden ein Quadrat mit ebenfalls 9 Feldern. Jede Spalte, jede Zeile und das zugehörige Quadrat bilden eine Einheit SZQ.

                                  Bild 1 Leeres Suduko zum Berechnen der Lösung

 Ein SZQ - Beispiel in Bild 1 ist grün gezeichnet. Im gelösten Rätsel, können in jeder Zeile, in jeder Spalte und jedem Quadrat alle Ziffern von 1-9 stehen. Diese Soll-zahlen der ODER - Bedingung ist in Bild 1 mit kleinen Zahlen in jedem Feld angedeutet. Zu Beginn des Rätsels steht in manchen Feldern davon schon eine Zahl, in anderen nicht. In solchen Feldern, gelten die klein geschriebenen Zahlen natürlich nicht mehr. Das Rätsel, ist dann gelöst, wenn in jeder Zeile und jeder Spalte und in den Quadraten eine der  Zahlen 1-9 stehen. Dann entfallen alle klein geschriebenen Zahlen. Im echten Rätsel sind diese Zahlen gar  nicht vorhanden , denn diese Tatsache ist ja bekannt. Aber zum Verständnis des Lösungsweges , ist es praktisch, wenn diese Hilfsziffern vorhanden sind.  Das Berechnungsziel ist nicht die direkte Berechnung der Lösung, sondern wir bauen durch logischen Vergleich die kleinen Soll-zahlen ab, bis sich die Lösung von selbst ergibt.

2: Die Lösungsmethode

Wir lösen das Rätsel mit vier logischen Vergleichen: JA / NEIN, WAHR / FALSCH und ODER.

In Bild 2 befindet sich ein SZQ mit vorgegeben Zahlen. In diesen bekannten Feldern gelten natürlich die kleinen Soll-zahlen nicht, wir streichen sie deshalb aus, sie sind abgebaut, das Feld ist fertig. Nun wollen wir das Feld B 2 abbauen. Wir fragen  für dieses Feld das SZQ mit ja /nein, ab und finden: 1 nicht ( nicht heißt auch durchstreichen), 2 nicht, 3 nicht, 4 nicht, 5 nicht, 6 nicht, 7 nicht, 9 nicht. 

Bild2 SZQ / Der Vergleich JA / NEIN

Jetzt sind alle Zahlen bis auf die 8 durchgestriche n, ergo die Lösung kann nur 8 heißen. Falls sich die Lösung noch nicht ergibt, weil z. B: die 6 auch nicht vorhanden ist, so haben wir doch eine Menge Soll-zahlen abgebaut. Die Lösung ergibt sich dann irgendwann im weiteren Verlauf des Abbaus. Und der geht sofort weiter, den die gefundene 8

                           Bild 3 Abbau von Soll-zahlen nach gefundener Lösung

 baut alle noch vorhandenen 8 im SZQ ab. Diese sind im Bild 3 gelb durchgestrichen. In Bild 4 finden im SZQ eine ganz andere Situation vor. Wie schon geübt, streichen wir die 6er und 1er in der Zeile , die 3er und die 4er in der Spalte ebenso die 1er, 3er und 7bener im Quadrat. Nun fragen wir alle übriggeblieb enen Ziffern im Quadrat, ob sie WAHR oder FALSCH sind. Falsch sind sie    dann,wenn sie mindestens 2mal im Quadrat vorkommen. Wahr sind sie, wenn sie

Bild 4 Sollzahlenabbau durch wahr und falsch

nur einmal im Quadrat vorhanden sind. Aus anderem Abbau, ist die 6 in allen Feldern schon gelöscht, nur in C2 nicht. Sofort löschen wir alle zugehörigen 6er in der Spalte 2. Das gleiche Fragespiel kann man sowohl für die Zeile als  auch für die Spalte durchführen. Schließlich kann man die Abfrage der Sollzahlen über alle Felder und SZQ’s durchführen. Jede neu gefundene Lösung ergibt neue Abbaumöglichkeiten bis alle Soll-zahlen gelöscht sind .Wenn aber nicht alle Zahlen abgebaut werden können, was dann? Dann hilft der ODER Versuch. Bei zwei Restziffern, kann nur eine die Lösung sein. Führt der Versuch zu keiner richtigen Lösung ,kann es nur die andere Ziffer sein. In der Praxis, ist der ODER Versuch  meistens gar nicht notwendig .

Viel Spaß.flaggebrd

 

 

 

Solving of  Sudoku puzzles with  logical  Algebra.

Solving a Sudoku puzzle is often a right Baste lei. If you finally have finished , eventually the last number will not fit, and you have to start all over again. In the following text, a solution method is described who is based on logical comparison. This method will without complicated formula calculation always lead to the solution.This method comes from  digital electronics.

 

1. The puzzle.

Fig.1 shows the puzzle, it has 9 rows (A-J)  and 9 columns. (1-9) Each row has nine fields, and each column has nine fields, for a total of 81 fields.The 3 rows and 3 columns forming a square, also with 9 fields. Each column, each row, and the corresponding square form a unit SZQ.

 

 

                                                Fig.1 Empty Sudoku for computing the solution

A SZQ - example in Figure 1 is drawn in green. In the solved puzzles, all numbers from 1-9 can be in every row, every column, and every square.These target numbers of the OR - condition is indicated in Figure 1, with small numbers in each field. At the beginning of the puzzle is already in some fields one of this numbers, not in others. In such fields, the small letters numbers no longer apply, of course.The puzzle is solved if there are in each row and each column and in the squares one of the numbers 1-9.Then account for all numbers the small letters. In a real puzzle, these figures are not available, because this fact is well known. But to understand the solution path, it is convenient if these auxiliary digits are available.The calculation goal is not the direct computation of the solution, but we reduce by means of logical comparison the small target figures, until there comes a solution by itself.

 

2.The solution method

We solve the puzzle using four logical comparisons: YES / NO, TRUE / FALSE and OR.

In Figure 2 there is a SZQ with specified numbers. Of course, in these known fields, the small target numbers are no longer valid, this field is completed. Now let's break down the field B 2. We ask yes /no , for this field from the SZQ and find: 1  not ( cross out this number ), 2 not, 3 not, 4 not ,5 not, 6 not, 7 not, 9 not.

 

 

 

                                             Fig.2 SZQ The Comparison Yes/No

Now all the numbers are crossed out except for the 8, ergo the solution can mean only 8. If the solution is not obtained, because for example, the 6 would not exist, yet we have reduced a lot of target figures. The solution is then obtained sometime in the course of degradation. And the degradation  proceeds immediately because the found 8 builds away all remaining 8 from the SZQ.These are streaked yellow in Figure 3.

 

                                     Fig. 3 Degradation of target figures found by solution

Figure 4 shows the  SZQ with a very different situation. As we had practised in the last example, we cross out the 6  and the 1  in the line, and the 3 and the 4 in column as well as the 1, 3 and 7 in the  square. Now we ask all remaining numbers in the square, whether they are TRUE or FALSE. Wrong they are when they occur in the square at least 2 times.True they are, if they are present only once in the square.

 

 

                                      Fig. 4 Target number degradation by true and false

From other degradation, the number 6 has been already deleted in all fields, but not in C2. We immediately delete the  6 in column 2. The same question game you can carry out  for the row and the column. Finally, one can perform this query, for all the target numbers on all fields and SZQ's. Every new solution found yields new  deleting opportunities until all desired numbers are deleted. But if all the numbers can not be broken, then what? Then helps the OR test. With two remaining digits, only one can be the solution. Does the attempt to no solution, it may be just the other digit. In practice, the OR test is usually not necessary.

Have fun.

 

 

 

Ein praktisches Beispiel

Für die Praxis beim Rätsel lösen, kann man den Abbau noch wesentlich vereinfachen, so das manche Lösungen lawinenartig zustande kommen. Bild 5 zeigt ein Rätselbeispiel.

Wir teilen alle  Felder mit einem Schrägstrich in zwei Teile und Ratz-Fatz geht’s los.

 

 

 

 

 

 [Bild 6] Wir lösen Quadrat um Quadrat und beginnen mit dem Quadrat 9, denn das hat schon 5 Ziffern vorgegeben. Nach der Methode “ NEIN / JA ” , suchen wir die Ziffern, die als Lösung für das Quadrat 9 in Frage kommen.

 

 

 

 

 

 

 

 

Die Lösung sieht dann aus wie Bild 7 . Das gibt gleich 4 Lösungen, ein guter Start.

 

 

 

 

 

 

 

 

 

 

Diese Lösungen werden gleich beim nächsten Quadrat zur NEIN / JA Frage  im Quadrat verwendet. Bild 8

 

 

 

 

 

 

 

 

 

 

Die WAHR / FALSCH Frage ergibt hier nur 1 Lösung. Bild 9.

 

 

 

 

 

 

 

 

 

Aber im nächsten Quadrat schlagen wir zu. Drei auf einem Streich, ganz schnell und die stimmen. Bild 10.   

 

 

 

 

 

 

 

 

 

 

 

 

Nun haben wir drei Quadrate in Reihe, das ergibt drei Zeilen zum überarbeiten. Dazu bauen wir ab , und streichen durch, was schon fertig ist. Dann prüfen wir, ob es in diesen Zeilen  WAHR / FALSCH Lösungen gibt. Leider gibt es keine Lösung, macht aber nichts. Wir kriegen die Lösung schon hin. Bild 11

 

 

 

 

 

 

 

 

 

 

 

Weiter geht es zum nächsten Quadrat Bild 12 und so fort .

 

 

 

 

 

 

 

 

 

 

 

 

Nach Ratz- Fatz Minuten ist das Ding gelöst. Fertig  Bild 13.

 

 

 

 

 

 

Bild 5 Suduko                                                  Fig.5 Sudoku

 

 

 

 

 

 

 

 

 

Bild 6 Lösungsanfang     Fig.6 The Beginning of Solutions

Bild 7 Mit einem Quadrat beginnen Fig.7 The first square

 Bild 8 Nächstes Quadrat       Fig.8 The next square        

 

Bild 9  Schon wieder eine Lösung Fig.9 The next Solution      

 

Bild 10 3Quadrate in Reihe   Fig.10 Two squares in series

 

Bild 11 Fertige Zeile bereinigen  Fig.11 Cleansing of the raw 

 

Bild 12 Das nächste Quadrat  u.s.w.Fig.12 The next Square 

 

Bild 13  Fertig                                                     Fig. 13 Ready

Viel Spass.                                                              Have Fun.

----------Ende Sudoku. Autor: S.Lechler 74 Elektriker-------

Zurück zum Anfang:                         Return to the beginning

 

 

A practical example

In practice, solve the puzzles, you can still simplify the reduction, so that some solutions snowballed come about.Fig.5 shows the example. We share all fields with a slash into two parts and Ratz-Fatz (very fast) we go to Fig.6.

 

 

 

 

 

 

 

 

Fig.6 We solve square to square and start with the square of 9, because that has already given 5 digits. According to the method "NO / YES", we are looking for the numbers that come as a solution for the square 9.

 

 

 

 

 

 

 

The solution now looks like the Fig.7. This is equal to 4 solutions, a good start.

 

 

 

 

 

 

 

 

 

These solutions are used  in the next square of the NO / YES question in the square. Fig.8

 

 

 

 

 

 

 

 

 

 

The TRUE / FALSE question gives only solution. Picture 9

 

 

 

 

 

 

 

 

 

 

But in the next square, we get it.Three at once, very fast and correct. Picture 10.

 

 

 

 

 

 

 

 

 

 

 

Now we have three squares in series, which results to revise three lines. Fig11:

 

 

 

 

 

 

 

 

 

 

 

 

Next it goes on to the next square image 12 and so on.

 

 

 

 

 

 

 

 

 

 

 

 

 

After Ratz-Fatz minutes, the thing is solved. Finished Picture 13.