הפעם בחרתי ללכת על משהו פשוט, שכולם יוכלו להשתתף ולהראות את הידע שצברו בתכנות.
כל!!! שפת תכנות מתאימה לבעיה זו, בעיה זו היא אלגוריתמית בעיקרה - ולכן בעיני זהו אתגר ראוי בהחלט.

אין צורך בממשקים גרפיים (מי שרוצה, שיתכבד...) - ניתן בהחלט להשתמש ב-console כדי להזין את הקלט ולהוציא את הפלט.

ועכשיו לאתגר:
אני מאמין שכולכם שמעתם את השם סודוקו, כתבו עליו כתבות, דיברו עליו בחדשות והוא מציף אתרים בתקופה האחרונה.
מטרת האתגרון, לבנות תכנית שהקלט שלה יהיה לוח סודוקו, והפלט יהיה הפתרון...
להסבר על סודוקו, על החוקים וכו...הנה האתר שיתן לכם את כל התשובות (בעברית):
http://www.sudoku.name/index-hb.php

עוד לא נקבע תאריך יעד לסיום האתגרון, מצפה להשתתפות מרובה הפעם, כי זו לא עבודה קשה...(:
בהצלחה לכולם...

[ זיו ]
[ fat fish ]

הקלט יכול להיות מערך דו מימדי (אם בא לכם להשתמש בכל מבנה נתונים אחר, בבקשה) כזה:


כשהפתרון זה הלוח הזה (או המערך וכו וכו) פתור במלואו...

תהנו,

[ זיו ]
[ fat fish ]

היום הוא המחר שאתמול כל כך דאגת בגללו

אני ינסה לשחק בזה עכשיו אולי נקלוט כמה דברים שיובילו לאלגוריתם לפתרון.

האלגוריתם פשוט :
1. חפש משבצת פנויה ראשונה.
2. חשב את כל האפשרויות לשבץ בה מספר.
3. עבור כל אפשרות,שלח את הלוח לרקורסיה.
4. אם הגענו למצב שאין אפשרות לשבץ מספר במשבצת ריקה,אזי אחד מהניחושים שלנו בשלב הקודם הוא שגוי. במקרה כזה,הרקורסיה נסוגה לאחור לאפשרות הבאה.
5. כשאין עוד משבצות ריקות,הפאזל נגמר.

האלגוריתם שלי פתר בינתיים פאזל אחד ברמת מדיום. הוא לא הכי יעיל,ויש בו עדיין באגים. לשמחתי,זמן הריצה הוא זניח. מי עושה לי QA?

הנה היישום בdotnet.

קוד:

<%@ Page Language="VB" Debug="true" %>
<script runat="server">
	function Check_for_moves(board(,) as integer,m as integer,n as integer) as integer()
		dim i as integer,j as integer
		dim legal_moves(9) as integer
		for i=1 to 9
			legal_moves(i)=0
		next
		for i=1 to 9
		if(board(m,i)<>0) then
			legal_moves(board(m,i))=1
		end if
		next
		for i=1 to 9
		if(board(i,n)<>0) then
			 legal_moves(board(i,n))=1
		end if
		next
		'3 first cubs
		if (m<=3) and (n<=3) then
			for i= 1 to 3
				for j=1 to 3
					if board(i,j)<>0 then
						legal_moves(board(i,j))=1
					end if
				next
			next
		end if
		if (m<=3) and (n>=4 and n<=6) then
			for i= 1 to 3
				for j=4 to 6
					if board(i,j)<>0 then
						legal_moves(board(i,j))=1
					end if
				next
			next
		end if
		if (m<=3) and (n>=7) then
			for i= 1 to 3
				for j=7 to 9
					if board(i,j)<>0 then
						legal_moves(board(i,j))=1
					end if
				next
			next
		end if
		'3 more cubes
		if (m>=4 and m<=6) and (n<=3) then
			for i= 4 to 6
				for j=1 to 3
					if board(i,j)<>0 then
						legal_moves(board(i,j))=1
					end if
				next
			next
		end if
		if (m>=4 and m<=6) and (n>=4 and n<=6) then
			for i= 4 to 6
				for j=4 to 6
					if board(i,j)<>0 then
						legal_moves(board(i,j))=1
					end if
				next
			next
		end if
		if (m>=4 and m<=6) and (n>=7) then
			for i= 4 to 6
				for j=7 to 9
					if board(i,j)<>0 then
						legal_moves(board(i,j))=1
					end if
				next
			next
		end if
		'3 last cubs
		if (m>=7) and (n<=3) then
			for i= 7 to 9
				for j=1 to 3
					if board(i,j)<>0 then
						legal_moves(board(i,j))=1
					end if
				next
			next
		end if
		if (m>=7) and (n>=4 and n<=6) then
			for i= 7 to 9
				for j=4 to 6
					if board(i,j)<>0 then
						legal_moves(board(i,j))=1
					end if
				next
			next
		end if
		if (m>=7) and (n>=7) then
			for i= 7 to 9
				for j=7 to 9
					if board(i,j)<>0 then
						legal_moves(board(i,j))=1
					end if
				next
			next
		end if

		return(legal_moves)
	end function

	function solve(board as integer(,),level as integer)
		if level>80 then return(0)
		dim m as integer,n as integer,i as integer,save as integer,k as integer,l as integer,found_empty as boolean
		found_empty=false
		for m=1 to 9
			for n=1 to 9
				if board(m,n)=0
					found_empty=true
					exit for
				end if
			next
			if found_empty then
			 exit for
			end if
		next
		'response.write(m)
	 ' response.write(" ")
	 ' response.write(n)
		'response.write(found_empty)
	 ' response.write("<br>")
		if not found_empty then
		 response.write("found borad!!!!!")
		 response.write("<br>")
		 for k=1 to 9
					for l=1 to 9
						if l=4 or l=7 then
						response.write("|")
						end if
						response.write(board(k,l))
						response.write ("	 ")
					next
					if k=3 or k=6 then
						response.write("<br>")
						response.write("------------------------")
					end if
					response.write("<br>")
				next
		 return(0)
		end if
			'if m>=9 then
			 ' for k=1 to 9
				 ' for l=1 to 9
				 '	 if l=4 or l=7 then
				 ''	 response.write("|")
					'	end if
					'	response.write(board(k,l))
					'	response.write ("	 ")
				 ' next
				 ' if k=3 or k=6 then
				 '	 response.write("<br>")
				 '	 response.write("------------------------")
				'	end if
				'	response.write("<br>")
			 ' next
		 ' end if
 
		dim temp as integer()=Check_for_moves(board,m,n)
		for i=1 to 9
			if temp(i)=0 then
				save=board(m,n)
				board(m,n)=i
				solve(board,level+1)
				board(m,n)=save
			end if
	 next
	end function
 
	Sub Page_Load(Sender As Object, E As EventArgs)
		 dim board(9,9) as integer
		 board(1,1)=0
		 board(1,2)=7
		 board(1,3)=0
		 board(1,4)=4
		 board(1,5)=0
		 board(1,6)=0
		 board(1,7)=0
		 board(1,8)=9
		 board(1,9)=0
		 board(2,1)=6
		 board(2,2)=0
		 board(2,3)=0
		 board(2,4)=0
		 board(2,5)=0
		 board(2,6)=9
		 board(2,7)=0
		 board(2,8)=2
		 board(2,9)=0
		 board(3,1)=5
		 board(3,2)=0
		 board(3,3)=0
		 board(3,4)=8
		 board(3,5)=0
		 board(3,6)=0
		 board(3,7)=7
		 board(3,8)=0
		 board(3,9)=0
		 board(4,1)=4
		 board(4,2)=0
		 board(4,3)=0
		 board(4,4)=0
		 board(4,5)=3
		 board(4,6)=0
		 board(4,7)=0
		 board(4,8)=6
		 board(4,9)=2
		 board(5,1)=0
		 board(5,2)=0
		 board(5,3)=0
		 board(5,4)=9
		 board(5,5)=0
		 board(5,6)=5
		 board(5,7)=0
		 board(5,8)=0
		 board(5,9)=0
		 board(6,1)=2
		 board(6,2)=9
		 board(6,3)=0
		 board(6,4)=0
		 board(6,5)=4
		 board(6,6)=0
		 board(6,7)=0
		 board(6,8)=0
		 board(6,9)=7
		 board(7,1)=0
		 board(7,2)=0
		 board(7,3)=4
		 board(7,4)=0
		 board(7,5)=0
		 board(7,6)=7
		 board(7,7)=0
		 board(7,8)=0
		 board(7,9)=6
		 board(8,1)=0
		 board(8,2)=5
		 board(8,3)=0
		 board(8,4)=1
		 board(8,5)=0
		 board(8,6)=0
		 board(8,7)=0
		 board(8,8)=0
		 board(8,9)=3
		 board(9,1)=0
		 board(9,2)=6
		 board(9,3)=0
		 board(9,4)=0
		 board(9,5)=0
		 board(9,6)=3
		 board(9,7)=0
		 board(9,8)=5
		 board(9,9)=0
		 dim board2 (9,9) as integer
		 board2(1,1)=1
		 board2(1,2)=1
		 board2(1,3)=0
		 board2(1,4)=3
		 board2(1,5)=2
		 board2(1,6)=1
		 board2(1,7)=1
		 board2(1,8)=1
		 board2(1,9)=7
		 board2(2,1)=4
		 board2(2,2)=9
		 board2(2,3)=7
		 board2(2,4)=1
		 board2(2,5)=6
		 board2(2,6)=2
		 board2(2,7)=5
		 board2(2,8)=1
		 board2(2,9)=1
		 board2(3,1)=2
		 board2(3,2)=1
		 board2(3,3)=4
		 board2(3,4)=1
		 board2(3,5)=1
		 board2(3,6)=7
		 board2(3,7)=9
		 board2(3,8)=2
		 board2(3,9)=1
		 board2(4,1)=1
		 board2(4,2)=4
		 board2(4,3)=1
		 board2(4,4)=1
		 board2(4,5)=7
		 board2(4,6)=2
		 board2(4,7)=1
		 board2(4,8)=2
		 board2(4,9)=3
		 board2(5,1)=1
		 board2(5,2)=7
		 board2(5,3)=1
		 board2(5,4)=1
		 board2(5,5)=1
		 board2(5,6)=5
		 board2(5,7)=1
		 board2(5,8)=4
		 board2(5,9)=1
		 board2(6,1)=9
		 board2(6,2)=6
		 board2(6,3)=1
		 board2(6,4)=1
		 board2(6,5)=3
		 board2(6,6)=1
		 board2(6,7)=1
		 board2(6,8)=7
		 board2(6,9)=1
		 board2(7,1)=1
		 board2(7,2)=1
		 board2(7,3)=9
		 board2(7,4)=6
		 board2(7,5)=1
		 board2(7,6)=1
		 board2(7,7)=1
		 board2(7,8)=1
		 board2(7,9)=5
		 board2(8,1)=1
		 board2(8,2)=2
		 board2(8,3)=1
		 board2(8,4)=1
		 board2(8,5)=2
		 board2(8,6)=1
		 board2(8,7)=7
		 board2(8,8)=2
		 board2(8,9)=6
		 board2(9,1)=2
		 board2(9,2)=2
		 board2(9,3)=4
		 board2(9,4)=2
		 board2(9,5)=2
		 board2(9,6)=1
		 board2(9,7)=2
		 board2(9,8)=2
		 board2(9,9)=2
		 dim m as integer,n as integer,t as integer
		 for m=1 to 9
			 for n=1 to 9
				 if n=4 or n=7 then
				 response.write("|")
				 end if
				 response.write(board(m,n))
				 response.write ("	 ")
			 next
			 if m=3 or m=6 then
				response.write("<br>")
				response.write("------------------------")
			 end if
			 response.write("<br>")
		 next
		 solve(board,1)
	End Sub
</script>
<html>
	<head>
	</head>
	<body>
		<form runat="server">
			<!-- Insert content here -->
		</form>
	</body>
</html>

 
 

1. למה את חושבת שניתן להתעלם מהיעילות הנמוכה של האלגו'?
2. אפשר לקבל גרסה מקומפלת?

אז בוודאי שאפשר ליעל את מה שאני עושה. הסודוקו הרגיל שמפורסם בעיתונים הוא של 9 על 9,והאלגוריתם שלי פותר אותם בלי בעיות ובזמן ריצה זניח. אם אתה רוצה לפתור לוחות של 900 על 900,אולי תהיה בעיה.
אפשרות אחת לייעול שכבר חשבתי עליה : במקום לחשב את המשבצת הראשונה הריקה,צריך לקחת בכל פעם את המשבצת שיש לה הכי פחות אפשרויות שיבוץ. זה יקטין מאד את עץ הרקורסיה. אולי כדאי לשמור את כל השיבוצים האפשריים בטבלה,ולעדכן אותה בכל מהלך.

בקשר לקימפול,אז הקוד הוא סקריפט של dotnet ולא קוד שעובר קומפילציה. לצערי,לא מותקן לי קומפיילר על המחשב. אם אתה רוצה,אתה יכול להעתיק את הקוד as is לVB ולקמפל,אולי עם כמה שינויים מינוריים.

כל-כך כאב לך לכתוב את אותו קוד כ-Windows Application?

פשוט,על המחשב שלי בבית יש רק web matrix עם .net framework.

SharpDevelop
לי לא הלכה טוב ההתקנה שלו לפני מספר חודשים, אבל אולי משהו השתנה מאז...

SharpDevelop עובד אצלי יופי...

אם משבצים את שלושת אזורים סמוכים(לא באלכסון) לפי חוקי הסודוקו אז הסדר שלהם נכון בהחלט

כמעט כל העולם והחברים החננים שלו עשו את זה. אני חושב שכדאי לעשות אלגוריתם שפותר את זה בעזרת לוגיקה בלבד (או לפחות אם הוא לא נתקע), כלומר לא ניחושים=ריקורסיה. במשחק שמורידים מ sudoku.com יש לוחות מאוד קשים (לי אישית לוקחים שעות), והם טוענים שאת כל הלוחות שלהם אפשר לפתור בעזרת לוגיקה

[התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://sfx-images.mozilla.org/affiliates/Buttons/180x60/take.gif]

יש נוסחה לגלות על פי הסדר וזה לא קשור לפעולות החשבון אך אף אחד לא יודע מהיא (טיפ:תסתקלו פעם על לוח סודוקו מלא ותיראו שהמספרים האפורים רומזים משהוא)
ואפילו קים כבר תוכנה שפותרת סודוקו אבל כדי לא להרוס,אני לא אגלה

תסתכלו על המספרים האפורים... איזה קשקוש. אם אף אחד לא יודע את זה אז איך אתה שזה בכלל קיים? ומה ההוכחה?

[התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://sfx-images.mozilla.org/affiliates/Buttons/180x60/take.gif]

אם אתה רוצה תגיד לי בפרטי

מה זה "פיתרון פשוט". או עד כמה פשוט זה פשוט

[התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://sfx-images.mozilla.org/affiliates/Buttons/180x60/take.gif]

אשמח אם תשלח לי את השיטה שלך לפתרון טבלאות סודקו בפרטי

התכנה שלי (בסי פלוס פלוס) כבר מסוגלת לפתור סודוקו ברמה קלה מהעיתון. אני עכשיו בפיתוח הלוגריתמים הנוספים על מנת לפתור רמות יותר קשות. האלגוריתם שלי די פשוט לכן אני לא בטוח אם זה יפתור את הקשים ממש אבל נראה.

שאלה כדרך אגב, מה זה QA? (שהוזכר קודם)

ושיהיה לפחות שבועיים ככה נראה לי למרות שאני יכול לגמור בפחות...שלא יתחיל להימרח לנצח.

[התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://sfx-images.mozilla.org/affiliates/Buttons/180x60/take.gif]

אבל גמרתי את התוכנית (כלומר היא פותרת סודוקו, זה לא אומר שלא צריך לעבוד עליה עדיין)
ביזבזתי מלא מלא שעות על באג טיפשי ביותר מאוד מאוד (סה"כ הייתי צריך להוריד שורה מסוימת ולהוציא אותה מחוץ לסוגריים-המסולסלים)
זה פותר סודוקו מהר וחכם.

צפו לפרטים בהמשך

[התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://sfx-images.mozilla.org/affiliates/Buttons/180x60/take.gif]

אני אסביר בקצרה: בהתחלה התוכנה מנסה לפתור את לוח הסודוקו ע"י בדיקות של לוגיקה פשוטה (בדיקה האם משבצת יכולה להיות רק מספר אחד, בדיקה האם יש מספר שרק משבצת אחת בריבוע יכולה להכיל אותו וכו') - הבדיקות האלו פותרות את לוחות הסודוקו הקלים ובזה נגמר העניין. ללוחות היותר קשים, התוכנה ממשיכה עם בדיקה של רקורסיה - היא מוצאת את המשבצת הפנויה הראשונה ומשבצת בה את המספר המוך ביותר שאין לו סתירות לוגיות (כלומר שאין אותו בטור, בשורה או בריבוע של המשבצת). הפונקציה קוראת לעצמה וכך ממשיכה עד שמגיעה למשבצת פנויה שאי אפשר להכיל בה אף מספר (בגין סתירות) - במקרה כזה היא חוזרת למשבצת הקודמת ומשנה את מספרה למספר הנמוך הבא שאין לו סתירות. במידה וכעת אין מספרים שהמשבצת יכולה להכיל, חוזרים למשבצת הקודמת וכו' וכו'...
הסיבה שהתוכנה מבצעת קודם את הבדיקות הרגילות, למרות שהיא יכול הלפתור הכל בעזרת הרקורסיה, היא כדי לחסוך זמן - הבדיוקת האלה הרבה יותר מהירות ופחות זוללות זכרון.
אולי ראוי לציין שזו הפעם הראשונה שבה התנסיתי בתכנות מונחה עצמים (תכנתתי בC ואף פעם לא ב C++) וגם הפעם הראשונה שפתרתי בעיה בעזרת רקורסיה. אני שמח לדעת שזו הייתה הצלחה

קוד:

// Solve Soduku! //

#include <iostream.h>
#include <conio.h>
#include <stdlib.h>

class Soduko
{
	private:
		int S[9][9];
	public:
		void SetSoduko();
		int AScan();
		int BScan();
		int CScan();
		int DScan();
		int EScan();
		void Solve(int Try);
		void ShowSoduko();
};
void Soduko::SetSoduko()
{
	
	cout << endl;
	int J;
	for(int I=0; I<9; I++)
		for(J=0; J<9; J++)
		{
			cout << "S[" << I << "][" << J << "]: ";
			cin >> S[I][J];
			if(S[I][J]==0)
				S[I][J]=-1;

		}
}
void Soduko::ShowSoduko()
{
	cout << endl;
	int J;
	cout << "--------------------------------------" << endl;
	for(int I=0; I<9; I++)
	{
		for(J=0; J<9; J++)
		{
			if(J==8)
			{
				if(S[I][J] != -1)
		 		cout << " " << S[I][J];
				else
					cout << " ";
			}
			else
				if(((J+1)%3)==0)
				{
					if(S[I][J] != -1)
		 			cout << " " << S[I][J] << " ||";
					else
		 			cout << " ||";
				}
				else
					if(S[I][J] != -1)
		 			cout << " " << S[I][J] << " |";
					else
		 			cout << " |";
		}
		cout << endl;
		if(((I+1)%3)==0)
			cout << "--------------------------------------" << endl;
	}
}
int Soduko::AScan()
{
	int I,J,Loop,Count,Mispar,Num,Shu,Amu,Tmp1,Tmp2,RET=0;  
	for(I=0; I<9; I++)
		for(J=0; J<9; J++)
		{
			if(S[I][J] != -1)
				continue;
			Count = 0;
			Num = -1;
			for(Mispar=1; Mispar<10; Mispar++)
			{
				for(Loop=0; Loop<9; Loop++)
					if(S[Loop][J] == Mispar)
						break;
				if(Loop<9)
					continue;
				for(Loop=0; Loop<9; Loop++)
					if(S[I][Loop] == Mispar)
						break;
				if(Loop<9)
					continue;
				if((I%3)==0)
					Shu = I;
				else
					if(((I+1)%3)==0)
						Shu = (I-2);
					else
		    		    if(((I+2)%3)==0)
		 		 	Shu = (I-1);
				if((J%3)==0)
					Amu = J;
				else
					if(((J+1)%3)==0)
						Amu = (J-2);
					else
		    		    if(((J+2)%3)==0)
		 		 	Amu = (J-1);
				for(Tmp1=0;Tmp1<3;Tmp1++)
				{
					for(Tmp2=0;Tmp2<3;Tmp2++)
		 		 if(S[Tmp1+Shu][Tmp2+Amu] == Mispar)
					  break;
					if(Tmp2<3)
						break;
				}
				if(Tmp1<3)
					continue;
				else
				{
					Count++;
					if(Count>1)
						break;
					Num = Mispar;
				}
			}
			if(Mispar<10)
				continue;
			else
			{
				S[I][J] = Num;
				RET=1;
			}

		}
	return(RET);
}
int Soduko::BScan()	   //Square
{
	int I,J,Mispar,Count=0,Loop,Num,J2,I2,Shu,Amu,Tmp1,Tmp  2,Tmp3,Tmp4,Sq,RET=0;
	for(Sq=0;Sq<9;Sq++)
	{
		if(Sq<3)
				Tmp3=Sq*3;
			else
				if(Sq>5)
					Tmp3=(Sq-3)*3;
				else
					Tmp3=(Sq-6)*3;
		Tmp4=(Sq/3)*3;
		for(Mispar=1; Mispar<10; Mispar++)
		{
			Count = 0;
			Num = -1;
			J = Tmp4+3;
			for(I=Tmp3;I<(3+Tmp3);I++)
			{
				if(J<(Tmp4+3))
					break;
				for(J=Tmp4;J<(3+Tmp4);J++)
				{
					if(S[I][J]!=-1)
						continue;
					for(Loop=0; Loop<9; Loop++)
		 			if(S[Loop][J] == Mispar)
					  break;
					if(Loop<9)
						continue;
					for(Loop=0; Loop<9; Loop++)
		 			if(S[I][Loop] == Mispar)
					  break;
					if(Loop<9)
						continue;
					if((I%3)==0)
						Shu = I;
					else
		    		    if(((I+1)%3)==0)
		 		 	Shu = (I-2);
						else
		 		 	if(((I+2)%3)==0)
		 		 		Shu = (I-1);
					if((J%3)==0)
						Amu = J;
					else
		    		    if(((J+1)%3)==0)
		 		 	Amu = (J-2);
		 		 else		 			
		 		 	if(((J+2)%3)==0)
		 		 		Amu = (J-1);
					for(Tmp1=0;Tmp1<3;Tmp1++)
					{
						
				  for(Tmp2=0;Tmp2<3;Tmp2++)
		 		 	if(S[Tmp1+Shu][Tmp2+Amu] == Mispar)
		 		 		break;
						if(Tmp2<3)
					  break;
					}
					if(Tmp1<3)
						continue;
					else
					{
						Count++;
						if(Count>1)
					  break;
						Num = Mispar;
						J2=J;
						I2=I;
					}

				}
			}
			if(Count==1)
			{
				S[I2][J2] = Num;
				RET=1;
			}
		}
	}
	return(RET);
}

int Soduko::CScan()	   //Shura
{
	int I,J,Mispar,Count=0,Loop,Num,J2,I2,Shu,Amu,Tmp1,Tmp  2,RET=0;
	for(I=0;I<9;I++)
	{
		for(Mispar=1; Mispar<10; Mispar++)
		{
			Count = 0;
			Num=-1;
			for(J=0;J<9;J++)
			{
				for(Loop=0; Loop<9; Loop++)
					if(S[Loop][J] == Mispar)
						break;
				if(Loop<9)
					continue;
				for(Loop=0; Loop<9; Loop++)
					if(S[I][Loop] == Mispar)
						break;
				if(Loop<9)
					continue;
				if((I%3)==0)
					Shu = I;
				else
					if(((I+1)%3)==0)
						Shu = (I-2);
					else
		    		    if(((I+2)%3)==0)
		 		 	Shu = (I-1);
				if((J%3)==0)
					Amu = J;
				else
					if(((J+1)%3)==0)
						Amu = (J-2);
		 		else 		 		
		    		    if(((J+2)%3)==0)
		 		 	Amu = (J-1);
					for(Tmp1=0;Tmp1<3;Tmp1++)
					{
						
				  for(Tmp2=0;Tmp2<3;Tmp2++)
		 		 	if(S[Tmp1+Shu][Tmp2+Amu] == Mispar)
		 		 		break;
						if(Tmp2<3)
					  break;
					}
					if(Tmp1<3)
						continue;
					else
					{
						Count++;
						if(Count>1)
					  break;
						Num = Mispar;
						J2=J;
						I2=I;
					}

			}
			if(Count==1)
			{
				S[I2][J2] = Num;
				RET=1;
			}
		}
	}
	return(RET);
}
int Soduko::DScan()	   //Amuda
{
	int I,J,Mispar,Count=0,Loop,Num,J2,I2,Shu,Amu,Tmp1,Tmp  2,RET=0;
	for(J=0;J<9;J++)
	{
		for(Mispar=1; Mispar<10; Mispar++)
		{
			Count = 0;
			Num=-1;
			for(I=0;I<9;I++)
			{
				for(Loop=0; Loop<9; Loop++)
					if(S[Loop][J] == Mispar)
						break;
				if(Loop<9)
					continue;
				for(Loop=0; Loop<9; Loop++)
					if(S[I][Loop] == Mispar)
						break;
				if(Loop<9)
					continue;
				if((I%3)==0)
					Shu = I;
				else
					if(((I+1)%3)==0)
						Shu = (I-2);
					else
		    		    if(((I+2)%3)==0)
		 		 	Shu = (I-1);
				if((J%3)==0)
					Amu = J;
				else
					if(((J+1)%3)==0)
						Amu = (J-2);
		 		else 		 		
		    		    if(((J+2)%3)==0)
		 		 	Amu = (J-1);
					for(Tmp1=0;Tmp1<3;Tmp1++)
					{
						
				  for(Tmp2=0;Tmp2<3;Tmp2++)
		 		 	if(S[Tmp1+Shu][Tmp2+Amu] == Mispar)
		 		 		break;
						if(Tmp2<3)
					  break;
					}
					if(Tmp1<3)
						continue;
					else
					{
						Count++;
						if(Count>1)
					  break;
						Num = Mispar;
						J2=J;
						I2=I;
					}

			}
			if(Count==1)
				S[J2][I2] = Num;
		}
	}
	return(RET);
}

int Soduko::EScan()
{
	int I,J,Mispar,Loop,Shu,Amu,Tmp1,Tmp2,Jan;
	for(I=0;I<9;I++)
	{
		for(J=0;J<9;J++)
			if(S[I][J]==-1)
				break;
		if(J<9)
			break;
	}
	if(I==9)
		return(1);
	for(Mispar=1;Mispar<10;Mispar++)
	{
		//Now, Find Stira
		for(Loop=0; Loop<9; Loop++)
			if(S[Loop][J] == Mispar)
					break;
		if(Loop<9)
			continue;
		for(Loop=0; Loop<9; Loop++)
			if(S[I][Loop] == Mispar)
				break;
		if(Loop<9)
			continue;
		if((I%3)==0)
			Shu = I;
		else
			if(((I+1)%3)==0)
				Shu = (I-2);
			else
				if(((I+2)%3)==0)
					Shu = (I-1);
		if((J%3)==0)
			Amu = J;
		else
			if(((J+1)%3)==0)
				Amu = (J-2);
			else
				if(((J+2)%3)==0)
					Amu = (J-1);
		for(Tmp1=0;Tmp1<3;Tmp1++)
		{
			for(Tmp2=0;Tmp2<3;Tmp2++)
				if(S[Tmp1+Shu][Tmp2+Amu] == Mispar)
					break;
			if(Tmp2<3)
				break;
		}
		if(Tmp1<3)
			continue;
		else
		{
			S[I][J] = Mispar;
			Jan = EScan();
			if(Jan==0)
			{
				S[I][J] = -1;
				continue;
			}
			else
				return(1);
		}
	}
	return(0);
		

		
}
void Soduko::Solve(int Try)
{
	for(int I=0;I<Try;I++)
	{
		AScan();
		BScan();
		CScan();
		DScan();
	}
}	
void main()
{
	Soduko So;
	So.SetSoduko();
	So.ShowSoduko();
	getch();
	cout << endl << endl << endl;
	So.Solve(10);
	So.EScan();
	So.ShowSoduko();
	getch();
}

גרסה מקומפלת:
https://2005-uploaded.fresh.co.il/2...16/77924380.exe

עריכה: הממשק לא משהו. כדי להקליד משבצת ריקה הקישו 0. הלוח הוא מערך דו מימדי 9 על 9. (ההקלדה היא שורה שורה משמאל לימין).

חתימתכם הוסרה כיוון שלא עמדה בחוקי האתר. לפרטים נוספים לחצו כאן. תוכלו לקבל עזרה להתאמת החתימה לחוקים בפורום חתימות וצלמיות.

תוכנית חביבה.
התוכנית שלי, תגיע בהמשך. אם אתה רוצה לדעת (להתכונן? לשפר?)
התוכנית שלי:
- תפתור כל סודוק בעזרת לוגיקה וללא רקורסיה.
- תהיה בעלת ממשק נחמד יחסית (אני רוצה לעשות גם שהיא תייצר קובץ HTML עם נימוקים למה היא שמה כל מספר.
- אולי תאפשר לשחק סודוקו באופן בסיסי (בלי סימונים, מדידת זמן וכו')
- תטען ותשמור מ/אל קובץ.
מה כבר מוכן:
-היא פותרת כל סודוקו כמו שכתוב למעלה.
- הממשק נמצא באמצע הדרך.
- טעינה מקובץ
מה לא מוכן:
- אני יכול להפיק הודעות דיבוג לתוך קובץ אבל עוד לא מייצר קובץ נימוקים.
- היא לא יודעת אבל לא לשמור

[התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://sfx-images.mozilla.org/affiliates/Buttons/180x60/take.gif]

<לא יכול לחכות לאתגר הבא, משעמם לי >

חתימתכם הוסרה כיוון שלא עמדה בחוקי האתר. לפרטים נוספים לחצו כאן. תוכלו לקבל עזרה להתאמת החתימה לחוקים בפורום חתימות וצלמיות.

אני רוצה לדעת כמה זמן עוד יש לי לעבוד על זה ומתי כל זה ייגמר.

[התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://sfx-images.mozilla.org/affiliates/Buttons/180x60/take.gif]

לכולם. בניגוד לפעמים קודמות, היתה הענות יפה לאתגר, והוצעו מספר דרכים לפתור את הסודוקו.
בקרוב יוצג אתגר חדש, והפעם נושא פרסים...(צל"ש בפורום)

אז בהצלחה לכולם בהמשך...

[ זיו ]
[ fat fish ]

עד מתי אפשר להגיש?

[התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://sfx-images.mozilla.org/affiliates/Buttons/180x60/take.gif]

אין מועד הגשה...אנו לא באוניברסיטה...((:
אם בא לך להעלות את הפתרון שלך גם עוד שנה - אתה מוזמן.
זו לא היתה תחרות - אלא אתגר פתיחה
מזמן לא היו אתגרים בפורום תכנות, וזה היה הפתח לבאות.

האתגרים הבאים יהיו עם מועדים ופרסים.

[ זיו ]
[ fat fish ]

טוב נו אפשר עוד לעבוד על זה הרבה אבל בכל זאת הנה הפותרת סודוקו שלי. קוראים לתוכנית הזאת סולדוקו (SolDoku) שזה Solve+Sudoku.
היא יודעת לטעון ולשמור לוחות.
היא יודעת לפתור בלי רקורסיה גם לוחות קשים במיוחד.
היא מייצרת קובץ HTML לצורך דיבוג. אני לא חושב שתמצאו בו מידע מעניין במיוחד.

מה רציתי לעשות ולא חשוב: שאפשר יהיה לעבור למצב "משחק".
שהיא תייצר קובץ נימוקים.

אם אתם רוצים לטעון לוח סודוקו אז צריך שיהיה sudoku.txt בתיקייה של הexecutable. הפורמט פשוט מאוד. כל משבצת היא פשוט סיפרה או תו אחר אם היא ריקה (מומלץ "-" (מקף)). סוף כל שורה של הלוח - סוף שורה בקובץ.


מה חשוב אבל לא עשיתי בכל זאת: לדבג עוד הרבה. וחוץ מזה יש דברים שהם באמצע למשל הממשק. אל תתיחסו.
הנה התוכנה. הקובץ הראשון מכיל רק את הקובץ שאשכרה פותר (הלוגיקה). הקובץ השני מכיל את כל הפרויקט, כולל קובץ הפעלה בתיקייה Soldoku\Soldoku\bin\Debug אם אתם רוצים להתרשם.
https://2005-uploaded.fresh.co.il/2...24/50185979.rar
https://2005-uploaded.fresh.co.il/2...24/76626895.rar

[התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://sfx-images.mozilla.org/affiliates/Buttons/180x60/take.gif]

הצלחתי לבנות משהו בסי אבל זה פותר רק את הלוחות הקלים והבינוניים בעיתון

עבדתי ע"פ הלוגיקה הפשוטה של הנחת מספרים בטוחים ע"פ החוקים אבל בלוחות הקשים זה נתקע

אני לא הבנתי מה אני אמור להוסיף לקוד שזה יפתור גם את הקשים...
ומה הכוונה ברקורסיה? איך בדיוק היא פותרת את הבעיה?

ולמי שאמר שאפשר בלי ניחושים (או רקורסיה)... איזה פיתרון עוד יש?

תודה מראש
תומר

אוקיי הבנתי

רעיון ממש מגניב עם הרקורסיה סחטיין Avidon
אפשר לפתור ככה לוח מההתחלה אבל אני מניח שזה פחות מהיר

(אם תתהו לאן הוא נעלם)
(:

[ זיו ]
[ fat fish ]